Königsberger Brückenproblem

Im preußischen Königsberg gibt es eine Flussinsel, genannt der Kneiphof. Sie ist von zwei Flussarmen umgeben. Über die Arme dieses Flusses führen sieben Brücken. Es galt die Frage zu lösen, ob man einen Spazierweg so einrichten könne, dass man jede dieser Brücken einmal und nicht mehr als einmal überschreite.
– Leonhard Euler, 1707–1783

Gibt es einen Rundweg, der erlaubt, dass man

1. jede Brücke einmal überquert, und
2. am Ende wieder an den Ausgangspunkt zurückkommt?

Beobachtungen:

• Absolute Entfernungen und Positionen sind unwichtig!
• Lagen und relative Beziehungen wichtig!
• Euler lässt irrelevante Informationen weg und vereinfacht das Problem

notwendige Bedingung:

1. Graph muß zusammenhängend sein
2. jeder Knoten muß gerade Anzahl von Kanten haben, muß geraden Grad haben
3. wenn genau 2 Knoten ungeraden Grad haben, hat der Graph einen Eulerpfad aber keinen Eulerkreis

Lösung:
Nein, ein solcher Rundweg existiert nicht. Der Graph der sieben Brücken ist zwar zusammenhängend, aber alle vier Knoten haben eine ungerade Anzahl von Kanten. Da mehr als zwei Knoten ungeraden Grad haben, erfüllt der Graph nicht die notwendige Bedingung für einen Eulerkreis. Somit ist es unmöglich, einen Spazierweg zu finden, der jede Brücke genau einmal überschreitet und am Ausgangspunkt endet.