Das Königsberger Brückenproblem

Zur Zeit von Leonard Euler floß in Königsberg der Fluß Pregel zusammen, wie in der Abbildung 5.links gezeigt wird. Es führten zur Insel A und zu den Festlandsseiten B und C sowie zur Landzunge D genau sieben Brücken.

Euler stellte sich die folgende Frage: Ist es möglich, alle Brücken nacheinander zu passieren, ohne eine auszulassen oder mehr als einmal zu überschreiten?

Das Problem ist nicht gerade ein Optimierungsproblem, man könnte es zur Not vielleicht in die Kategorie Problem des kürzesten Weges pressen. Es gibt eine Spezialbezeichnung für die Klasse solcher Probleme: Zeichnen eines Bildes in einem Zug. Tiefgehender beschäftigt sich die Topologie mit derartigen Aufgaben.

Euler zeigte, dass das vorliegende Problem nicht lösbar ist, er formulierte sogar eine allgemeine notwendige und hinreichende Bedingung: Ein Bild ist in einem Zug zeichenbar, wenn es entweder genau zwei oder keinen Knotenpunkt ungeraden Grades besitzt.

Als Knotenpunkte ungeraden Grades sind all jene Knoten eines ungerichteten Graphen zu verstehen, die eine ungerade Anzahl benachbarter Kanten besitzen. Betrachten wir den Graphen des vorliegenden Problems in der Abbildung 5.rechts, ist leicht zu erkennen, dass tatsächlich die notwendige Bedingung nicht erfüllt ist.