mathematik - physik - informatik Seite zurück   Seite vor  

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

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.



  Bert Xylander - 30. Dezember 2015
  'Optimierung in der Schule'
Seite zurück   Seite vor