Zeven bruggen van Koningsbergen

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Naar zoeken springen

De zeven bruggen van Koningsbergen is een wiskundig vraagstuk. Het geldt als een van de eerste problemen uit de grafentheorie. Het probleem werd voor het eerst in 1736 opgelost door Leonhard Euler.

Het vraagstuk[bewerken | brontekst bewerken]

De stad Koningsbergen (het tegenwoordige Kaliningrad) lag in het oosten van Pruisen aan de rivier de Pregel, waarin twee eilanden lagen die door zeven bruggen met elkaar en met de vaste wal verbonden waren, hieronder schematisch afgebeeld. De vraag was nu of het mogelijk is om zó te lopen dat je precies één keer over elke brug komt. In sommige versies van het vraagstuk werd ook geëist dat men weer bij het startpunt eindigt.

In 1736 heeft Euler op ogenschijnlijk eenvoudige wijze aangetoond dat dit onmogelijk is.[1] Eulers werkwijze was echter revolutionair en vormde de bakermat van een geheel nieuwe wiskundige discipline, de topologie. Hij beschouwde de bruggen van Koningsbergen als een stelsel van knoopunten en verbindingslijnen (later een graaf genoemd), zoals hieronder geïllustreerd:

Kaart van Koningsbergen uit Eulers tijd, met de locatie van de zeven bruggen
Vereenvoudigde kaart
Gereduceerd tot een graaf

In de graaf (rechter afbeelding) wordt elke brug voorgesteld door een lijn, en de eilanden en oevers door een blauw knooppunt. Het aantal lijnen dat een punt met andere punten verbindt, heet de graad van dat punt. Speciaal van belang is het onderscheid tussen een even en een oneven graad: de punten die door een oneven aantal lijnen verbonden worden noemen we oneven knooppunten. Verbindt een even aantal lijnen een punt met andere punten, dan noemen we het een even knooppunt.

De vraag of het mogelijk is om zó te lopen dat je precies één keer over elke brug komt, is nu vertaald naar de vraag naar een mogelijke route waarbij je precies één keer over elke lijn loopt. Zo'n route noemen we een Eulerwandeling. Een bijzonder geval daarvan is een wandeling waarvan het begin- en eindpunt met elkaar samenvallen. Zo'n wandeling heet een Eulertour.

Voor de oplossing hiervan is het van wezenlijk belang naar de graad van de knooppunten te kijken. Deze bepaalt namelijk de mogelijke rol die het knooppunt kan spelen in een route. Een knooppunt met precies 1 verbindingslijn kan alleen maar het begin- of eindpunt van een route zijn. Een knooppunt met precies 2 verbindingen kan het beginpunt of eindpunt van een route zijn, of kan in plaats daarvan een tussenstation op een doorgaande route zijn. Deze redenering is door te trekken naar hogere graden. Een oneven knooppunt moet hetzij beginpunt hetzij eindpunt zijn van een gezochte route.

Bekijken we nu eerst, voor een willekeurige configuratie, de mogelijkheid van een Eulerwandeling waarbij begin- en eindpunt verschillen. In zowel begin- als eindpunt moet het knooppunt dan oneven zijn. Een extra oneven knooppunt gooit roet in het eten. Immers, men kan een wandeling maar precies 1 keer beginnen en 1 keer eindigen. Kijken we vervolgens naar de mogelijkheid van een Eulertour, waarbij begin- en eindpunt samenvallen. Die kan alleen bestaan als de graaf geen enkel oneven knooppunt bevat. Zo blijkt dat voor een willekeurige configuratie een Eulerwandeling alleen dan kan bestaan als de graaf precies 0 of 2 oneven knooppunten bevat. In Koningsbergen zijn er echter vier oneven knooppunten. Een Eulerwandeling is daar dus niet mogelijk.

Het verschil tussen de geografische (topografische) ligging en de schematische weergave van hierboven laat mooi zien hoe topografie van topologie verschilt. Topologie gaat over de onderlinge verbindingen van de beschouwde objecten, terwijl topografie ook de relatie met andere dingen laat zien (zoals afstanden en richtingen naar geheel andere objecten).

Euler geldt als een van de grootste wiskundigen, die veel ingewikkelde problemen heeft opgelost. Het probleem van de zeven bruggen lijkt achteraf kinderlijk eenvoudig, maar is niet op te lossen zonder deze geniale wisseling van perspectief.

Variaties op het probleem komt men dikwijls tegen op puzzelpagina's, waarbij wordt gevraagd een figuur te tekenen zonder het potlood van het papier te nemen en zonder een lijn twee keer te tekenen. Sinds de analyse van Euler is dat eenvoudig: als er twee oneven knooppunten zijn, moet men bij één van de twee beginnen. Zijn er meer dan twee punten van oneven graad, of is er precies één, dan is er geen oplossing.

De huidige staat van de bruggen[bewerken | brontekst bewerken]

Twee van de zeven oorspronkelijke bruggen werden vernietigd door het bombardement op Koningsbergen in de Tweede Wereldoorlog. Twee andere werden later door de Russen verwijderd en vervangen door een snelweg. Een vierde brug is in 1935 vervangen. Slechts twee bruggen dateren nog uit de tijd van Euler.[2]

In termen van de grafentheorie zijn er nu twee punten waar een even aantal lijnen samenkomt (namelijk twee). Bij twee andere punten komen in de huidige situatie drie lijnen samen. Daarmee is op dit moment een Eulerwandeling wel degelijk mogelijk, hoewel het voor toeristen een onpraktische route zou zijn.[3] Voor toeristen met een wiskundeknobbel geen bezwaar, natuurlijk.

Bronnen[bewerken | brontekst bewerken]

  1. Euler, Leonhard (1736). "Solutio problematis ad geometriam situs pertinentis". Comment. Acad. Sci. U. Petrop 8, 128–40.
  2. Taylor, Peter, What Ever Happened to Those Bridges?. Australian Mathematics Trust (December 2000). Gearchiveerd op 19 maart 2012.
  3. Stallmann, Matthias, The 7/5 Bridges of Koenigsberg/Kaliningrad (Juli 2006). Gearchiveerd op 1 december 2008.
Zie de categorie Seven Bridges of Königsberg van Wikimedia Commons voor mediabestanden over dit onderwerp.