Zeven bruggen van Koningsbergen: verschil tussen versies

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 punten van oneven graadknooppunten. Verbindt een even aantal lijnen een punt met andere punten, dan noemen we het een punt van even graadknooppunt.

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. HeeftEen eenoneven knooppunt een oneven graad, dan moet het dus hetzij beginpunt hetzij eindpunt zijn van deeen gezochte route.

Bekijken we denu graaf als geheeleerst, dan blijkt dat als ervoor een onevenwillekeurige knooppuntconfiguratie, isde (waarmogelijkheid menvan een Eulerwandeling moetwaarbij beginnenbegin- ofen eindigen),eindpunt erverschillen. ookIn eenzowel tweedebegin- onevenals knooppunteindpunt moet zijnhet (omknooppunt daardan preciesoneven het tegenovergestelde te doen)zijn. Een extra oneven knooppunt gooit roet in het eten. Immers, men kan een wandeling maar precies 1 keer beginnen. Zoen blijkt1 datkeer ereindigen. voorKijken eenwe bepaaldevervolgens configuratienaar eende Eulerwandelingmogelijkheid bestaatvan indieneen deEulertour, graafwaarbij preciesbegin- 0en ofeindpunt 2samenvallen. onevenDie knooppuntenkan bevat.alleen Inbestaan Koningsbergenals zijnde ergraaf echtergeen vier knooppunten vanenkel oneven graad.knooppunt Daarom is daar een Eulerwandeling niet mogelijkbevat. EenZo bijzondereblijkt variantdat vanvoor heteen probleemwillekeurige zoekt naarconfiguratie een Eulerwandeling waarvanalleen hetdan begin-kan enbestaan eindpuntals metde elkaargraaf samenvallen.precies Zo'n0 wandelingof heet2 eenoneven Eulertourknooppunten bevat. DieIn bestaatKoningsbergen alleenzijn maarer alsechter de graaf geen enkelvier oneven knooppunt bevatknooppunten. Een EulertourEulerwandeling is bijdaar de zeven bruggen van Koningsbergen al helemaaldus niet mogelijk,. aangezien een Eulertour een bijzondere Eulerwandeling is.