Zeven bruggen van Koningsbergen

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.

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 eenvoudige wijze aangetoond dat dit onmogelijk is.^[1] Eulers werkwijze was eenvoudig maar revolutionair en vormde de bakermat van een geheel nieuwe wiskundige discipline, de topologie. Hij beschouwde de bruggen van Koningsbergen als een stelsel van knooppunten en verbindingslijnen (later een graaf genoemd), zoals hieronder geïllustreerd:

In de graaf (rechter afbeelding) wordt elke brug voorgesteld door een lijn, en de eilanden en oevers door een groen 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 of eulercykel.

Van een eulerwandeling kan een oneven knooppunt alleen maar het begin- of eindpunt zijn. Er zijn in Koningsbergen vier oneven knooppunten. Een eulerwandeling is dus niet mogelijk, en een eulertour ook niet.

Twee stellingen (zie de bewijzen):

• Een samenhangende graaf bevat een eulerwandeling dan en slechts dan als het aantal oneven knopen nul of twee is.
• Een samenhangende graaf bevat een eulercykel dan en slechts dan als de graad van alle knopen even is.

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 een samenhangende graaf gepresenteerd wordt en gevraagd wordt deze te tekenen zonder het potlood van het papier te nemen en zonder een lijn twee keer te tekenen. Het kan als het aantal oneven knooppunten nul of twee is. Als het er twee zijn, is het vaak gemakkelijk als men zich realiseert dat men bij één van de twee moet beginnen. Als er geen oneven knooppunten zijn kan men bij een willekeurig punt beginnen en is het vaak ook gemakkelijk.

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.

Zie de categorie Seven Bridges of Königsberg van Wikimedia Commons voor mediabestanden over dit onderwerp.