Zeven bruggen van Koningsbergen
De zeven bruggen van Konigsbergen is een wiskundig vraagstuk.
In de grafentheorie is het probleem van de zeven bruggen van Königsberg (Koningsbergen in het Nederlands) voor het eerst opgelost door Leonhard Euler. In de geschiedenis van de wiskunde is het één van de eerste grafentheoretische problemen. Omdat de grafentheorie als een deelveld van de topologie kan worden beschouwd vormt dit vraagstuk ook een van de eerste problemen binnen de topologie die formeel geanalyseerd zijn. (De combinatoriek maakt ook wel aanspraak op de grafentheorie, maar combinatorische problemen werden al veel eerder beschouwd.)
De stad Koningsbergen (heden ten dage Kaliningrad) lag aan de rivier de Pregel, waarin twee eilanden lagen die door zeven bruggen met elkaar en met de vaste wal verbonden waren; dit staat hieronder schematisch afgebeeld.
De vraag was nu of het mogelijk is om zó te wandelen dat je precies één maal over elke brug liep en weer op het startpunt eindigde. In 1736 heeft Euler aangetoond dat dit onmogelijk is. Tevens heeft hij laten zien dat het probleem beschouwd kan worden als een probleem op een graaf, waarin de bruggen van Koningsbergen als volgt gemodelleerd zijn:
Euler toonde aan dat zo'n wandeling dan en slechts dan mogelijk is als er geen punten zijn (met blauw aangegeven in de afbeelding) die grenzen aan een oneven aantal lijnen. Zo'n wandeling heet een Eulertoer. Omdat de graaf van Koningsbergen vier punten heeft die aan een oneven aantal lijnen grenzen, is de wandeling onmogelijk.
Als het startpunt niet gelijk hoeft te zijn aan het eindpunt, kunnen er hoogstens twee punten zijn die aan een oneven aantal lijnen grenzen. Zo'n wandeling wordt een Eulerwandeling genoemd. In een knoop met een oneven aantal aansluitende lijnen, móet de wandeling ófwel starten ófwel stoppen; wanneer de knoop gewoon gepasseerd wordt kunnen immers twee wegen niet meer gebruikt worden. Op het einde blijft dan één weg achter, die enkel gebruikt kan worden als in de knoop gestopt wordt.
Momenteel (juni 2003) is er een kaart die de werkelijke ligging van de zeven bruggen ten tijde van Euler afbeeldt; deze staat op de externe pagina http://www-gap.dcs.st-and.ac.uk/~history/Miscellaneous/Konigsberg.html
Het verschil tussen de echte ligging en de schematische weergave van hierboven is een goed voorbeeld van het kenmerk dat topologie zich niet bezighoudt met de exacte weergave van zaken, maar meer met hun relatieve vorm.
