Königsberger Brückenproblem
Das Königsberger Brückenproblem ist eine mathematische Fragestellung des frühen 18. Jahrhunderts, die anhand der sieben Königsberger Pregelbrücken illustriert wurde. In der Graphentheorie entspricht es dem Eulerkreisproblem.
Brückenverbindungen
Königsberg wird durch den Pregel und seine beiden Inseln geteilt. Die beiden Stadthälften waren durch je drei Brücken mit den Inseln verbunden, die untereinander durch eine weitere Brücke verbunden waren.
Datei:Konigsberg bridges.png →
→
Datei:Königsberg graph.svg
Fragestellung
Die Frage war, ob es einen Weg gibt, bei dem man alle sieben Brücken genau einmal überquert, und wenn ja, ob auch ein Rundweg möglich ist, bei dem man wieder zum Ausgangspunkt gelangt.
Leonhard Euler bewies 1736, dass ein solcher Weg bzw. „Eulerscher Weg“ in Königsberg nicht möglich war, da zu allen vier Ufergebieten bzw. Inseln eine ungerade Zahl von Brücken führte. Es dürfte maximal zwei Ufer (Knoten) mit einer ungeraden Zahl von angeschlossenen Brücken (Kanten) geben. Diese zwei Ufer könnten Ausgangs- bzw. Endpunkt sein. Die restlichen Ufer müssten eine gerade Anzahl von Brücken haben, um sie auch wieder auf einem neuen Weg verlassen zu können.
Das Brückenproblem ist kein klassisches geometrisches Problem, da es nicht auf die präzise Lage der Brücken ankommt, sondern nur darauf, welche Brücke welche Inseln miteinander verbindet. Es handelt sich deshalb um ein topologisches Problem, das Euler mit Methoden löste, die heute der Graphentheorie zugerechnet werden. Das Problem lässt sich auf beliebige Graphen verallgemeinern, und auf die Frage, ob es darin einen Zyklus gibt, der alle Kanten genau einmal benutzt. Ein solcher Zyklus wird als Eulerkreis bezeichnet und ein Graph, der einen Eulerkreis besitzt, als eulersch. Die Frage, ob ein Graph eulersch ist, lässt sich relativ einfach beantworten und ist auch in gerichteten Graphen und Graphen mit Mehrfachkanten möglich.
Durch Kriegseinwirkung und Umbauten nach 1945 ist die ursprüngliche Situation im heutigen Kaliningrad nicht mehr gegeben. Zwei der zur Insel Kneiphof führenden Brücken existieren nicht mehr; am nördlichen und südlichen Ufer enden nur noch jeweils zwei anstatt drei Brücken. Nun ist zwar ein Eulerweg möglich, jedoch noch immer kein Eulerkreis.
Literatur
- Gustav Theodor Hoffheinz: Die sieben Brücken in Königsberg. Altpreußische Monatsschrift, N. F. 18 (1881), S. 282 ff.
- Wladimir Velminski: Leonhard Euler. Die Geburt der Graphentheorie. Kulturverlag Kadmos, Berlin 2008, ISBN 978-3-86599-056-3.
- Rudolf Fritsch, Jewgeni Peregud, Sergei Matsejewski: Ausgewählte Kapitel der Graphentheorie (in Russisch), Verlag der Staatlichen Immanuel Kant Universität, Kaliningrad 2008.
Weblinks
- John J. O’Connor, Edmund F. Robertson: Königsberg bridges. In:
- Das Königsberger Brückenproblem – Didaktisch gelungene Bearbeitung bei MathePrisma.
- Spaziergänge und Buslinien – knappere anschauliche und theoretische Darstellung mit Hilfe von Kantenzügen von Franz Embacher, Univ. Wien.
