WisFaq!

Het probleem van Koningsbergen

Hallo
Wij moeten voor school een onderzoek doen naar Grafen en hun nut in de praktijk. We zijn begonnen met een kleine inleiding en we hebben daarin even wat info gegeven over het bekende probleem van Koningsbergen. We zouden graag weten of onze oplossing compleet is.



Een zeer bekend probleem is het vraagstuk van Koningsbergen. Het is de bekende Leonhard Euler die uiteindelijk heeft kunnen bewijzen met behulp van grafen dat het probleem niet oplosbaar is. Koningsbergen (nu: Kaliningrad) ligt aan een rivier (nu: Pregola) in Oost-Pruisen waarin 2 eilanden lagen die verbonden waren met 7 bruggen.

Probleemstelling:
De bewoners van de stad vroegen zich af of het mogelijk was om een parcours af te leggen. De voorwaarde was echter dat elke brug 1 keer moest worden overgestoken en dat men op elk punt A, B, C en D is geweest.
Oplossing:

• De graad van een knoop is gelijk aan de hoeveelheid lijnen waaraan de knoop grenst. Deze kan even of oneven zijn.
• Elk punt A, B, C, D heeft een oneven graad.
• Elke brug moet 1 keer worden overgestoken. Aangezien elke knoop oneven is, is er niet voor elke heenweg een terugweg. Elke knoop moet een graad hebben die een veelvoud is van 2. Met andere woorden de graad moet even zijn.
• Vermits al deze knopen een oneven graad hebben is het probleem onoplosbaar.

Alvast bedankt
6de jaar Latijn-Wiskunde uit Maaseik

Yasmine Claes
7-1-2008

Antwoord

Dag Yasmine,

Jullie oplossing is bijna goed. Je merkt terecht op dat je even graden nodig hebt. Echter, het is toegestaan dat twee punten een oneven graad hebben: stel dat A en B oneven graad hebben, en C en D even graad, dan zou je wel een wandeling kunnen maken die in A vertrekt en in B eindigt. Want als je in A vertrekt heb je dus één lijn nodig die in A begint; als je later op je wandeling nog eens door A gaat heb je een lijn nodig om daar aan te komen, en een lijn om er weer weg te geraken. Dus als A graad 3 heeft (of 5, of 7, of ... als je vaker via A passeert), dan kan het nog wel. Denk in dat verband aan dat bekende puzzeltje waarbij je in één pennentrek een huis met een kruisje erin moet tekenen, dat werkt ook alleen als je links- of rechtsonder begint...

Conclusie: een wandeling die aan de voorwaarden voldoet (men noemt dat ook een Euleriaanse wandeling) kan hier niet omdat je vier punten met oneven graad hebt, en je mag er maximaal twee hebben. Overigens, het is zelfs zo dat, als je een graaf hebt met 0 of 2 oneven toppen, je altijd zo een wandeling kan vinden. Voorwaarde is natuurlijk wel dat je graaf samenhangend is, dus uit één stuk bestaat.

Groeten,
Christophe.

Christophe
7-1-2008