Königsberg-Brücken
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 einzelnen Stadtteile. 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 1735 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 zu keinem Gebiet eine ungerade Zahl von Brücken führt, wenn ein Rundweg der gesuchten Art möglich ist. Ferner vermutet er, dass ein solcher Rundweg existiert, wenn zu jedem Gebiet eine gerade Zahl von Brücken führtGibt 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. Der umfassende Beweis von Eulers Aussagen zum Brückenproblem wird mit Hilfe der graphentheoretischen Sprache vom deutschen Mathematiker Carl Hierholzer im Jahre 1871 geliefert.
Eine Variante des Problems ist die Frage, ob man eine Figur in einem einzigen Zug zeichnen kann, ohne dabei den Bleistift vom Papier abzusetzen.