Bruggen probleem

Moderators: dirkwb, Xilvo

Forumregels
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
Reageer
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 :roll:

Melissa

Berichten: 171

Re: Bruggen probleem

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   :roll:  

Melissa
je kunt die graag graaf alleen doorlopen als het aantal oneven punten (punten met oneven aantal routes) gelijk is aan 0 of aan 2.!

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

Berichten: 169

Re: Bruggen probleem

inderdaad! :wink:

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! :roll: )

Melissa

Reageer