Ein Eulerscher Weg ist ein geschlossener Kantenzug, in dem jede Kante genau einmal vorkommt. |
Gehen wir dabei von sinnvollen Grundbedingungen aus, nämlich dass der Graph überhaupt zusammenhängend ist, es zu jedem Knoten also mindestens eine Kante geben muss, dann ist damit auch die realistische Forderung mit erfüllt, dass jeder Knoten mindestens einmal im Weg autauchen muss.
Für Eulersche Wege in Graphen gibt es relativ einsichtige allgemeine Forderungen, deren Erfülltsein kein Suchproblem darstellt. Es ist beispielsweise trivialerweise festzustellen, dass ein Graph, bei dem ein Knoten nur zu einer Kante gehört, kein Eulerscher Graph sein kann: Wie soll man von diesem Knoten wegkommen, wenn man zu ihm gekommen ist?
Dies läßt sich nun zu einer allgemeineren Forderung erweitern: Ein Graph kann nur dann Eulerscher Graph sein, wenn der Grad (=Zahl der zugehörigen Kanten) jedes Knotens gerade ist. Es gilt sogar folgender Satz:
Ein zusammenhängender ungerichteter Graph ist genau dann ein Eulerscher Graph, wenn die Zahl der zugehörigen Kanten jedes Knotens gerade ist. |
Volker Turau in "Algorithmische Graphentheorie" verwendet seinen Beweis dafür zur Beschreibung eines Algorithmus zur Lösung des Problems, einen Eulerschen Weg anzugeben.
Obwohl dies Problem also eigentlich nicht in den Kontext dieses Textes gehört, da es ein direktes Verfahren gibt, wäre es eine sinnvolle Übung rekursiver Techniken, ein Programm zu seiner Lösung zu schreiben. Siehe dazu auch Ziegenbalk.
Die Formulierung ist so wenig unterschiedlich, ersetzt man aber in der o.a. Definition die Forderung in dem jede Kante genau einmal vorkommt durch die Forderung in dem jeder Knoten genau einmal vorkommt, dann kommt man nicht zu einem Eulerschen Graphen, sondern zu einem Hamiltonschen Graphen
Anmerkung: Leonhar Euler (1707 - 1783)
Die Definition eines Eulerscher Weges weicht bei Ziegenbalk von der eigentlichen Eulerschen Problemstellung und der sonst üblichen Definition ab. Ziegenbalk spricht zwar von einem geschlossenen Kantenzug, geht dann aber in der Analyse von einem Kantenzug aus, bei dem Start- und Zielknoten nicht identisch sein müssen. Nur dann ist es möglich, dass es zwei Knoten ungerader Ordnung gibt.