Eulerscher Pfad

Ein Eulerscher Pfad ist ein Pfad in einem Graphen, der über jede Kante genau einmal führt. Obwohl sich die Aufgabe mit der kleinen Abwandlung von Knoten zu Kanten identisch mit der Aufgabe für den Hamiltonschen Pfad ist, ist die Lösung dafür völlig anders.

Man sagt, der schweizer Mathematiker Euler bewies, daß das Königsberger Brückenproblem nicht zu lösen sei. In diesem Problem ging es um den Versuch, alle Brücken (Kanten eines Graphen) in Königsberg auf einer Tour genau einmal zu überqueren.

Euler konnte 1736 nachweisen, daß es einen Eulerschen Pfad unter genau zwei Bedingungen gibt:

1. Der Pfad muß zusammenhängend sein.
2. Die Anzahl der Kanten, die sich an einem Knoten treffen muß gerade sein. Eine Ausnahme bilden dabei Start und Zielpunkt, an denen die Anzahl auch ungerade sein kann.

In dem folgenden Bild 1 ist ein Graph zu sehen, der keinen Eulerschen Pfad besitzt, es sei denn, man fügt die zusätzliche, gepunktete Kante ein. Wie der Eulersche Pfad dann verläuft wird in Bild 2 verdeutlicht.

Bild 1	Bild 2

Copyright 1996 by Matthias Hoffmann
letzte Änderung: 1-11-1996