Bruggen probleem
Forumregels
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
-
- Berichten: 169
Bruggen probleem
Iedereen kent wel het bekende Koningsberger bruggen probleem.
Het was Euler die zich afvroeg of men een wandeling kon maken door Koningsbergen, zodanig dat je elke brug precies een keer passeert.
Mijn vraag is: kun je een gemakkelijke manier vinden om, als je een aantal punten hebt en een aantal bruggen die deze punten verbindt, heel snel kunt zeggen of het mogelijk is of niet om een wandeling te maken zodanig dat je over alle bruggen bent geweest en over elke brug juist één keer bent geweest?
Ik heb al een oplossing
Melissa
Het was Euler die zich afvroeg of men een wandeling kon maken door Koningsbergen, zodanig dat je elke brug precies een keer passeert.
Mijn vraag is: kun je een gemakkelijke manier vinden om, als je een aantal punten hebt en een aantal bruggen die deze punten verbindt, heel snel kunt zeggen of het mogelijk is of niet om een wandeling te maken zodanig dat je over alle bruggen bent geweest en over elke brug juist één keer bent geweest?
Ik heb al een oplossing
Melissa
-
- Berichten: 171
Re: Bruggen probleem
je kunt die graag graaf alleen doorlopen als het aantal oneven punten (punten met oneven aantal routes) gelijk is aan 0 of aan 2.!Melissa schreef:Iedereen kent wel het bekende Koningsberger bruggen probleem.
Het was Euler die zich afvroeg of men een wandeling kon maken door Koningsbergen, zodanig dat je elke brug precies een keer passeert.
Mijn vraag is: kun je een gemakkelijke manier vinden om, als je een aantal punten hebt en een aantal bruggen die deze punten verbindt, heel snel kunt zeggen of het mogelijk is of niet om een wandeling te maken zodanig dat je over alle bruggen bent geweest en over elke brug juist één keer bent geweest?
Ik heb al een oplossing
Melissa
leuk onderwerp.. we hadden een keertje een presentatie van gekregen!
-
- Berichten: 171
Re: Bruggen probleem
kan jij dat bewijzen?
ik op dit moment.. heb at niet geprobeerd
ik op dit moment.. heb at niet geprobeerd
-
- Berichten: 169
Re: Bruggen probleem
inderdaad!
Een wiskundig bewijs heb ik nog niet direct, maar ik zag het als volgt:
bekijk het als een touw dat je van punt tot punt verbindt. Je kan dus een route volgen als het ofwel een gesloten touw is (een lus) of een gewoon touw met twee uiteindes! Dus als je enkele punten hebt waar een oneven aantal bruggen toekomen, dan mogen dit maar 2 punten zijn (de 2 uiteindes van je touw!) ofwel natuurlijk geen oneven punten. Van zodra je 3 of meer punten ziet waar een oneven aantal routes samenkomen, is het al onmogelijk. (ook als er maar één oneven punt is, een touw met slechts één uiteinde bestaat namelijk niet! )
Melissa
Een wiskundig bewijs heb ik nog niet direct, maar ik zag het als volgt:
bekijk het als een touw dat je van punt tot punt verbindt. Je kan dus een route volgen als het ofwel een gesloten touw is (een lus) of een gewoon touw met twee uiteindes! Dus als je enkele punten hebt waar een oneven aantal bruggen toekomen, dan mogen dit maar 2 punten zijn (de 2 uiteindes van je touw!) ofwel natuurlijk geen oneven punten. Van zodra je 3 of meer punten ziet waar een oneven aantal routes samenkomen, is het al onmogelijk. (ook als er maar één oneven punt is, een touw met slechts één uiteinde bestaat namelijk niet! )
Melissa