|
De '''zeven bruggen van Koningsbergen''' is een [[wiskunde|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==
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.<ref>Leonhard Euler (1736). [https://archive.org/details/commentariiacade08impe/page/128/mode/2up "Solutio problematis ad geometriam situs pertinentis"]. ''Comment. Acad. Sci. U. Petrop'' 8, 128–40.</ref> 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 knooppunten en verbindingslijnen (later een [[grafentheorie|graaf]] genoemd), zoals hieronder geïllustreerd:
YO MAMA
{|
|[[Bestand:Konigsberg bridges.png|180px|thumb|Kaart van Koningsbergen uit Eulers tijd, met de locatie van de zeven bruggen]]
|[[Bestand:7 bridges.svg|180px|thumb|Vereenvoudigde kaart]]
|[[Bestand:Königsberg_graph.svg|180px|thumb|Gereduceerd tot een graaf]]
|}
In de [[Grafentheorie|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 of eulercykel.
Van een eulerwandeling kan een oneven knooppunt alleen maar het begin- of eindpunt zijn. Er zijn hier vier oneven knooppunten. Een eulerwandeling is dus niet mogelijk, en een eulertour dus ook niet.
Twee stellingen (zie [[Grafentheorie#Euler_en_Hamilton|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.
==De huidige staat van de bruggen==
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.<ref>{{Citeer web |url=http://www.amt.canberra.edu.au/koenigs.html |title=What ''Ever'' Happened to Those Bridges? |last=Taylor |first=Peter |date=December 2000 |publisher=Australian Mathematics Trust |deadurl=yes |archiveurl=https://web.archive.org/web/20120319074335/http://www.amt.canberra.edu.au/koenigs.html |archivedate=2012-03-19 }}</ref>
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.<ref>{{Citeer web |url=http://www.csc.ncsu.edu/faculty/stallmann/SevenBridges/ |title=The 7/5 Bridges of Koenigsberg/Kaliningrad|last=Stallmann |first=Matthias |date=Juli 2006 |archiefurl=https://web.archive.org/web/20081201162535/http://www.csc.ncsu.edu/faculty/stallmann/SevenBridges/|archiefdatum=2008-12-01|dodeurl=nee}}</ref> Voor toeristen met een wiskundeknobbel geen bezwaar, natuurlijk.
==Bronnen==
| 