Zeven bruggen van Koningsbergen
Van Wikipedia
De zeven bruggen van Konigsbergen (heden ten dage zeven bruggen van Kaliningrad) is een wiskundig vraagstuk.
In de grafentheorie is het probleem van de zeven bruggen van Koningsbergen 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.)
[bewerk] Het vraagstuk
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. Soms werd ook geëist dat men 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 het vraagstuk over de bruggen van Koningsbergen als volgt geabstraheerd is:
→ 
→ 
Euler toonde aan dat zo'n wandeling slechts mogelijk is als er geen punten zijn (met blauw aangegeven in de afbeelding) die grenzen aan een oneven aantal lijnen. Immers, voor elke brug die je passeert naar een punt, moet ook een tweede brug zijn om dat punt weer te verlaten. Een wandeling waarbij dat wel mogelijk is heet een Eulertoer. Omdat bij de graaf van Koningsbergen elk van de vier punten aan een oneven aantal lijnen grenst, 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 punt met een oneven aantal aansluitende lijnen, móet de wandeling ófwel starten ófwel stoppen; wanneer het punt 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. Ook deze vorm is in dit geval echter niet mogelijk omdat alle punten grenzen aan een oneven aantal lijnen.
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.
Een bekend puzzeltje is om een bepaalde figuur te tekenen zonder het potlood van het papier te nemen. Dat puzzeltje is oplosbaar als er hoogstens twee punten zijn waarin een oneven aantal lijnen samenkomt. Men moet dan in een van die punten beginnen. Natuurlijk moet de figuur ook samenhangend zijn.
[bewerk] De huidige staat van de bruggen
Twee van de zeven oorspronkelijke bruggen werden vernietigd door het bombardement op Koningsbergen ten tijde van de Tweede Wereldoorlog. Twee andere werden later door de Russen verwijderd en vervangen door een snelweg. De overige drie bruggen bestaan nog, waarbij opgemerkt dat er slechts twee dateren uit de tijd van Euler, en dat er één werd herbouwd door de Duitsers in 1935.[1]
In termen van de grafentheorie, zijn er nu twee punten waar een even aantal lijnen samenkomen (namelijk twee). Bij twee andere punten komen in de huidige situatie drie lijnen samen. Daarmee is op dit moment een Eulerwandeling wel degelijk mogelijk, alhoewel het voor toeristen een onpraktische route zou zijn.[2]
[bewerk] Bronnen
- ↑ Taylor, Peter (December 2000). What Ever Happened to Those Bridges?. Australian Mathematics Trust.
- ↑ Stallmann, Matthias (Juli 2006). The 7/5 Bridges of Koenigsberg/Kaliningrad.
