Über 7 Brücken sollst du gehen
In der Stadtmitte von Königsberg (heute Kaliningrad, Russland) ist die Insel Kneiphof (A) von zwei Flussarmen mit insgesamt sieben Brücken umgeben. Leonhard Euler stellte die Frage, ob man auf einem Weg nacheinander über alle sieben Brücken gehen kann, ohne eine mehrfach zu überqueren. Was denken Sie?
In der Tat gibt es keinen solchen Weg.
Euler begründete mit dieser Frage die Graphentheorie. Der gesuchte Weg wird in der Mathematik als Euler-Weg bezeichnet.
In der Graphentheorie entsprechen die vier Ufer (die Insel mitgezählt) den Knoten eines Graphen und die Brücken bilden die Kanten. Euler zeigte 1736, dass es keinen Weg gibt, bei dem jede Brücke genau einmal überquert wird, weil mehr als zwei Knoten (Ufer) eine ungerade Zahl von Kanten (Brücken) haben.
Warum? Wenn der Wanderer einen Knoten über eine Kante betritt, muss er ihn über eine andere Kante wieder verlassen, so dass insgesamt die Anzahl der noch verfügbaren Kanten um zwei sinkt – es sei denn, der Weg beginnt oder endet in diesem Knoten. Das heißt: Mit Ausnahme von Anfang und Ende des Wegs muss jeder Knoten eine gerade Anzahl von Kanten haben, damit es einen Euler-Weg gibt.
Bei zwei ungeraden Knoten (oder Ufern) wäre also ein Euler-Weg zwischen diesen beiden möglich; bei gar keinem Knoten sogar ein Euler-Rundweg.
Schreiben Sie uns!
Beitrag schreiben