Springen naar inhoud

Bruggen probleem


  • Log in om te kunnen reageren

#1

Melissa

    Melissa


  • >100 berichten
  • 169 berichten
  • Ervaren gebruiker

Geplaatst op 14 januari 2006 - 20:43

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

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

zijtjeszotjes

    zijtjeszotjes


  • >100 berichten
  • 171 berichten
  • Ervaren gebruiker

Geplaatst op 14 januari 2006 - 20:51

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!

#3

zijtjeszotjes

    zijtjeszotjes


  • >100 berichten
  • 171 berichten
  • Ervaren gebruiker

Geplaatst op 14 januari 2006 - 20:56

kan jij dat bewijzen?
ik op dit moment.. heb at niet geprobeerd

#4

Melissa

    Melissa


  • >100 berichten
  • 169 berichten
  • Ervaren gebruiker

Geplaatst op 14 januari 2006 - 21:07

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





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures