Das Königsberger Brückenproblem
Zur Zeit von Leonard Euler floss in Königsberg der Fluss
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.
Abbildung 5: Das Königsberger Brückenproblem.
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.
|