Bridges of Königsberg

Im Zentrum der preussischen Stadt Königsberg (heute Kaliningrad) bildet der Fluss Pregel beim Zusammenfluss zweier Arme eine Insel. Im 18. Jahrhundert verbinden 7 Brücken die Flussufer mit der Insel. Es stellt sich die Frage, ob es einen Rundweg gibt, bei dem man alle 7 Brücken genau einmal überquert und wieder zum Ausgangspunkt zurück gelangt.

Geschichte

Das Problem der Königsberger Brücken stammt von Leonhard Euler. Im Jahre 1736 beweist er, dass es keinen solchen Rundweg geben kann. Er betrachtet den allgemeinen Fall mit einer beliebigen Anzahl Inseln und Brücken und zeigt, dass ein Rundweg der gesuchten Art genau dann möglich ist, wenn sich an keinem der Ufer eine ungerade Zahl von Brücken befindet. Gibt es an genau zwei Ufern eine ungerade Anzahl Brücken, dann existiert ein Weg, der bei diesen beiden Ufern beginnt und endet und dabei alle Brücken genau einmal überquert. Gibt es, wie in Königsberg, mehr als zwei Gebiete, zu denen eine ungerade Zahl von Brücken führt, dann kann kein Weg existieren, der genau einmal alle Brücken überquert.

Mathematik

Das Brückenproblem ist ein topologisches Problem, das Euler mit einer Methode löst, die man heute der Graphentheorie zuordnen würde. Betrachtet wird ein Graph, dessen Knoten die einzelnen Gebiete der Stadt und dessen Kanten die Brücken sind. Es geht darum, einen Zyklus zu finden, der alle Kanten genau einmal durchläuft. In der Sprache der Graphentheorie sagt man, dass ein Euler-Kreis genau dann existiert, wenn es keinen Knoten mit einer ungeraden Anzahl Kanten gibt. Stimmen Anfangs- und Endpunkt nicht überein, spricht man von einem Euler-Weg. Die von Euler bewiesenen Aussagen können auf die entsprechenden Aussagen für Graphen übertragen werden.

Eine Variante des Problems ist die Frage, ob man eine Figur in einem einzigen Zug zeichnen kann, ohne dabei den Bleistift vom Papier abzusetzen.