Königsberger Brückenproblem
aus Wikipedia, der freien Enzyklopädie
Das Königsberger Brückenproblem ist ein 1736 von Leonhard Euler gelöstes mathematisches Problem. Am konkreten Beispiel bezieht es sich auf die Brücken der Stadt Königsberg – heute Kaliningrad – und die Frage, ob es einen Rundweg gibt, bei dem man alle sieben Brücken der Stadt über den Pregel genau einmal überquert und wieder zum Ausgangspunkt gelangt. Die Grundaufgabe lautete, „nur“ einen wie oben beschriebenen Weg zu finden, ohne aber zum Ausgangspunkt zurückzukehren. Euler bewies, dass es keinen solchen Rundweg, nach ihm deshalb auch als „Eulerscher Weg“ bezeichnet, geben kann.
Das Brückenproblem ist kein klassisches geometrisches Problem, da es nicht auf die genaue 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 wir heute der Graphentheorie zurechnen.
Um die Nichtexistenz einer Lösung zu zeigen, benutzte Euler ein heute als klassisch geltendes Paritäts-Argument: Er zeigte, dass ein Rundweg der gesuchten Art nur dann möglich ist, wenn sich an keinem der Ufer (Knoten) eine ungerade Zahl von Brücken (Kanten) befindet. Da nämlich jede Brücke genau einmal überquert werden soll, muss jedes Ufer, das über eine Brücke erreicht wird, über eine andere Brücke wieder verlassen werden. Da aber zu allen vier Gebieten von Königsberg eine ungerade Zahl von Brücken führte, war der gesuchte Rundweg nicht möglich.
Das Problem lässt sich auf beliebige Graphen und die Frage, ob es darin einen Zyklus gibt, der alle Kanten genau einmal benutzt, verallgemeinern. 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.
Im heutigen Kaliningrad wurde durch Kriegseinwirkung und Umbauten die ursprüngliche Situation zerstört. Dadurch existiert mittlerweile zwar ein Eulerweg, jedoch noch immer kein Eulerkreis.
[Bearbeiten] Die 7 Brücken mit Namen
[Bearbeiten] Weblinks
- Königsberger Karten, teilweise historisch (engl. Erläuterungen)
- Das Königsberger Brückenproblem – Didaktisch gelungene Bearbeitung bei MathePrisma.
