Nieuwe pagina 1

© h.hofstede (h.hofstede@hogeland.nl)

De bruggen van Königsberg.

Laten we lekker een stukje gaan wandelen in Königsberg.
Köningsberg (Kaliningrad) was een stadje in Duitsland waar de rivier de Pregel doorheen stroomt.
Zo midden in de 18e eeuw waren er in het stadje 7 bruggen die de verschillende delen met elkaar verbonden. Hier is een plattegrond:

De inwoners van Königsberg vroegen zich af of het mogelijk was een wandeling te maken waarbij alle stadsdelen werden bezocht en waarbij elke brug precies één keer werd overgestoken. Alle pogingen waren vergeefs.

Gelukkig woonde er in Königsberg een zeker Leonard Euler!
Euler kwam vrij snel met het bewijs dat zo'n wandeling onmogelijk is. Dat bewees hij als volgt:
Schematisch, als we alleen letten op de landdelen en de bruggen, is de situatie als volgt:

En nóg schematischer als hiernaast. Daarin is elk landdeel door een stip voorgesteld en elke brug door een lijn.

De vraag is eigenlijk geworden of we de figuur hiernaast in één keer kunnen tekenen zonder ons potlood van het papier te halen en elke lijn maar één keer te volgen.

Euler bedacht het volgende: elke keer als we op onze route een knooppunt passeren komen we er via de ene verbindingslijn aan, en vertrekken we weer via een andere verbindingslijn. Dus elke passage komt overeen met twee verbindingslijnen bij een knooppunt.

De punten die we alleen maar passeren zullen daarom in totaal een even aantal lijnen hebben.
Alleen als we in één punt beginnen en in een ander punt eindigen hebben dat begin- en eindpunt een oneven aantal verbindingslijnen. (één voor begin/eind plus 2 voor elke keer onderweg passeren)

Een wandeling met verschillend begin- en eindpunt (sindsdien heel toepasselijk een EULER-route genoemd) is dus alleen mogelijk als alle knooppunten een even aantal verbindingslijnen hebben, op twee na, die een oneven aantal hebben.

Omdat de knooppunten van de graaf van Königsberg allemaal een oneven graad hebben zal een wandeling dus nooit mogelijk zijn.