Eulerkreisproblem

Ein Eulerkreis (auch geschlossener Eulerzug, Eulertour) ist in der Graphentheorie ein Zyklus, der alle Kanten eines Graphen genau einmal enthält.

Ein offener Eulerzug (auch Eulerpfad oder Eulerweg) ist gegeben, wenn Start- und Endknoten nicht gleich sein müssen, wenn also statt eines Zyklus lediglich eine Kantenfolge verlangt wird, welche jede Kante des Graphen genau einmal enthält. Ein bekanntes Beispiel ist das „Haus vom Nikolaus“.

Ein zusammenhängender Graph, der einen Eulerkreis besitzt, heißt eulerscher Graph. Enthält ein Graph lediglich einen Eulerweg und keinen Eulerkreis, so heißt er semi-eulerscher Graph. Die Aufgabe, zu einem gegebenen Graph zu bestimmen, ob dieser eulersch ist oder nicht, wird als Eulerkreisproblem bezeichnet. Es geht auf das 1736 von Leonhard Euler gelöste Königsberger Brückenproblem zurück. Das Problem existiert auch für gerichtete Graphen und Graphen mit Mehrfachkanten.

Entgegen seinem Namen ist der Eulerkreis kein Kreis, zumindest wenn der häufigen Definition gefolgt wird, nach der sich in einem Kreis kein Knoten wiederholen darf.

Geschichte 
Leonhard Euler fragte in seiner Arbeit 1736 zum Königsberger Brückenproblem – übersetzt in die heutige Fachsprache –, ob der durch die Brücken der Stadt gegebene Graph ein semi-eulerscher Graph ist, das heißt, ob ein Eulerweg existiert, und verneinte dies, da der Graph mehr als zwei Knoten mit ungeradem Grad hatte. Euler bewies, dass ein semi-eulerscher Graph höchstens zwei Knoten ungeraden Grades haben kann. Er vermutete und gab ohne Beweis an, dass dies eine hinreichende Bedingung sei: Ein zusammenhängender Graph, in dem jeder Knoten geraden Grad hat, ist ein Eulergraph. Ein Beweis des Satzes wurde zuerst von Carl Hierholzer 1873 veröffentlicht. Auf dem Beweis basiert der Algorithmus von Hierholzer zum Auffinden eines Eulerwegs.

Charakterisierung 
Nach dem Satz von Euler-Hierholzer sind eulersche Graphen leicht zu charakterisieren.

Sei G ein Graph, bei dem höchstens eine Zusammenhangskomponente Kanten enthält. Dann sind folgende Aussagen äquivalent:
 G ist eulersch,
 jeder Knoten in G hat geraden Grad.
 die Kantenmenge von G ist die Vereinigungsmenge aller Kanten von paarweise disjunkten Kreisen.

Analog sind für einen gerichteten Graphen G, bei dem höchstens eine starke Zusammenhangskomponente Kanten enthält, folgende Aussagen äquivalent:
 G ist eulersch,
 für jeden Knoten in G sind Eingangsgrad und Ausgangsgrad gleich.
 die Kantenmenge von G ist die Vereinigungsmenge aller Kanten von paarweise disjunkten gerichteten Kreisen.

Verallgemeinerung: Eulerweg 
Ein ungerichteter zusammenhängender Graph enthält genau dann einen Eulerweg, wenn zwei oder keiner seiner Knoten von ungeradem Grad sind. Hat kein Knoten ungeraden Grad, handelt es sich bei dem Eulerweg um einen Eulerkreis.

Entscheidungsproblem 
Die Frage, ob für einen gegebenen Graph ein Eulerkreis existiert, lässt sich algorithmisch relativ leicht lösen, da ein Graph genau dann eulersch ist, wenn er zusammenhängend ist und jeder Knoten geraden Grad besitzt. Mittels Tiefensuche lässt sich dies leicht in linearer Zeit feststellen.

Auffinden eines Eulerkreises 
Zum Auffinden eines Eulerkreises existieren mehrere Verfahren. Der Algorithmus von Fleury stammt aus dem Jahr 1883 und verfolgt einen sehr einfachen Ansatz, weshalb er eine Laufzeit von der Größenordnung  hat. Effizienter ist der Algorithmus von Hierholzer, der einen Eulerkreis in Linearzeit berechnet. Er basiert darauf, dass sich ein eulerscher Graph in paarweise kantendisjunkte Kreise zerlegen lässt.

Algorithmus von Hierholzer 

 Wähle einen beliebigen Knoten  des Graphen und konstruiere von  ausgehend einen Kreis  in , der keine Kante in  zweimal durchläuft.
 Wenn  ein Eulerkreis ist, brich ab. Andernfalls:
 Vernachlässige nun alle Kanten des Kreises .
 Am ersten Knoten von , dessen Grad größer 0 ist, wird nun ein weiterer Kreis  gebildet, der keine Kante in  durchläuft und keine Kante in  zweimal enthält.
 Füge in  den zweiten Kreis  ein, indem der Startknoten von  durch alle Knoten von  in der richtigen Reihenfolge ersetzt wird.
 Nenne jetzt den so erhaltenen Kreis  und fahre bei Schritt 2 fort.

Die Laufzeit des Algorithmus ist linear in der Anzahl der Kanten, ist also von der Größenordnung .

Beispiel 

Gegeben sei ein Eulergraph mit neun Knoten (siehe erste Abbildung). Ein Zyklus vom Startknoten 1 wäre beispielsweise die in der zweiten Abbildung blau dargestellte Knotenfolge . Nach Entfernen dieser Kanten haben die Knoten 1, 3 und 7 der bisher gebildeten Zyklus noch einen Knotengrad größer Null, welche als Startknoten für den nächsten Zyklus in Frage kommen. Vom Startknoten 3 aus kann man den Kreis  bilden (siehe dritte Abbildung). Wählt man nun als Startknoten den Knoten 7, kann man von den übrig gebliebenen Kanten den Zyklus  bilden. Setzt man jetzt  in  an Stelle des Knoten 7 ein, erhält man den Zyklus . Setzt man diesen in  an Stelle des Knoten 3 ein, erhält man die mögliche Eulertour  wie in der letzten Abbildung gezeigt.

Die Abbildung rechts zeigt eine Animation für dieses Beispiel.

Programmierung 
Das folgende Beispiel in der Programmiersprache C# zeigt die Implementierung des Algorithmus von Hierholzer für einen ungerichteten Graphen. Bei der Ausführung des Programms wird die Methode Main verwendet, die den Eulerkreis auf der Konsole ausgibt.

Hinweise: In der Methode GetEulerCircuitByHierholzer werden die Knoten des Eulerkreises in einer Liste gespeichert. Die Knoten des aktuell durchlaufenen Kreises werden in einem Stack (Stapelspeicher) gespeichert. Wenn kein Nachbarknoten des aktuell durchlaufenen Knoten erreichbar ist, weil alle Kanten dieses Knotens gelöscht wurden, wird der zuletzt durchlaufene Knoten vom Stack genommen und am Anfang der Liste eingefügt. Dabei wird Backtracking ohne rekursive Programmierung verwendet.

Im Programmbeispiel wird nur einer der möglichen Eulerkreise bestimmt und ausgegeben.

Algorithmus von Fleury 
Im Algorithmus von Fleury spielen Brückenkanten eine wichtige Rolle. Das sind Kanten, ohne die der Graph in zwei Komponenten zerfallen würde.

Der Algorithmus fügt einer anfangs leeren Kantenfolge alle Kanten eines Graphen hinzu, sodass ein Eulerkreis entsteht.
 Wähle einen beliebigen Knoten als aktuellen Knoten.
 Wähle unter den unmarkierten, mit dem aktuellen Knoten inzidenten Kanten eine beliebige Kante aus. Dabei sind zuerst Kanten zu wählen, die im unmarkierten Graphen keine Brückenkanten sind.
 Markiere die gewählte Kante und füge sie der Kantenfolge hinzu.
 Wähle den anderen Knoten der gewählten Kante als neuen aktuellen Knoten.
 Wenn noch unmarkierte Kanten existieren, dann gehe zu Schritt 2.

Ob eine Kante eine Brückenkante ist, kann mittels Tiefensuche in Laufzeit  überprüft werden. Da pro Schritt eine Kante entfernt wird, werden  Iterationen benötigt. Die Anzahl der pro Iteration geprüften Kanten entspricht dem Grad des aktuellen Knotens. Insgesamt kann die gesamte Anzahl überprüfter Kanten durch  beschränkt werden. Die gesamte Laufzeit ist damit von der Größenordnung .

Programmierung 
Das folgende Beispiel in der Programmiersprache C# zeigt die Implementierung des Algorithmus von Fleury für einen ungerichteten Graphen. Der ungerichtete Graph wird als Klasse UndirectedGraph deklariert. Bei der Ausführung des Programms wird die Methode Main verwendet, die den Eulerkreis oder Eulerpfad auf der Konsole ausgibt.

Hinweise: Sowohl für das Referenzieren der Knoten des ungerichteten Graphen als auch für das Referenzieren der Nachbarknoten jedes Knoten wird ein HashSet (Menge) als Datentyp verwendet und mit foreach-Schleifen durchlaufen. Der Vorteil des HashSet für die Nachbarknoten im Vergleich zu einer Liste ist, dass dann meist viel schneller, nämlich mit konstanter Laufzeit, geprüft werden kann, ob ein bestimmter Knoten Nachbarknoten eines anderen Knoten ist (siehe Hashtabelle – Vorteile). Ein Nachteil ist, dass dann die Reihenfolge der durchlaufenen Knoten in den foreach-Schleifen und damit auch die Reihenfolge der ausgegebenen Knoten des Eulerpfads nicht eindeutig oder teilweise zufällig ist.

Im Programmbeispiel wird nur einer der möglichen Eulerpfade bestimmt und ausgegeben, falls einer existiert.

Statt dem HashSet (Menge) visitedNodes kann auch eine Liste oder ein Array vom Typ bool (Boolesche Variable) verwendet werden, wie im Einzelnachweis gezeigt.

Vermutung von Hajos 
Nach der im Allgemeinen ungelösten Zyklenvermutung von György Hajós über Kreiszerlegung von Eulergraphen von 1968 können Eulergraphen mit  Knoten in höchstens  Kreise zerlegt werden. Die Vermutung wurde für kleine Graphen () 2017 bewiesen und für Pfadweite kleiner oder gleich 6.

Anwendungsbeispiele

Das Königsberger Brückenproblem 
Das Königsberger Brückenproblem lässt sich in folgendem Graphen ausdrücken:

Die Kreise (Knoten) sind die jeweiligen Stadtteile bzw. Standpunkte. Die Linien (Kanten) sind die Brücken. Durch Probieren wird herausgefunden, dass es nicht möglich ist, einen Rundgang durch die Stadt zu finden, bei dem jede Brücke genau ein einziges Mal benutzt wird. Es gibt also keinen Eulerweg und demzufolge auch keinen Eulerkreis. Warum ist das so?

Euler hat die folgende Gesetzmäßigkeit entdeckt: Wenn in einem Graphen G ein Eulerweg existiert, dann haben maximal 2 Knoten ungeraden Grad. Beim Königsberger Brückengraphen gibt es vier Knoten mit ungeradem Grad. Die Zahlen neben den Knoten geben in der Abbildung deren Grad an. Deshalb ist der Stadtrundgang mit dem nur einmaligen Benutzen jeder Brücke unmöglich.

Ein ungerader Knoten ist entweder Anfang oder Ende des Weges über die Brücken: null ungerade Knoten würde bedeuten, dass Anfang und Ende des Weges in Königsberg identisch sind. Ein Weg mit Anfang und Ende hätte maximal zwei ungerade Knoten. Ergo ist es in Königsberg nicht möglich gewesen, alle Brücken in einem Wege nur jeweils einmal zu begehen.

Das Haus vom Nikolaus 

Das beliebte Kinderrätsel „Das ist das Haus vom Nikolaus“ hingegen enthält einen Eulerweg, aber keinen Eulerkreis, da sein Graph zwei Knoten vom Grad 3 enthält.

Solch ein Eulerweg ist 1-2-4-3-1-4-5-3-2. Knoten 1 und 2 haben jeweils 3 Nachbarn, ihr Grad ist also ungerade. Um das Haus in einem Zug zeichnen zu können muss daher an einem dieser beiden Punkte begonnen werden. Ein Quadrat mit Diagonalen enthält keinen Eulerweg, da alle seine Knoten den Grad 3 haben. Im Bild sind das nur die Punkte 1, 2, 3, 4 mit den verbindenden Kanten.

Siehe auch 
 Hamiltonkreisproblem

Literatur 
 Wladimir Velminski: Leonhard Euler. Die Geburt der Graphentheorie. Kulturverlag Kadmos, Berlin 2008, ISBN 978-3-86599-056-3.
 Reinhard Diestel: Graphentheorie. 3. Auflage. Springer, 2006, ISBN 3-540-21391-0, S. 23–24

Einzelnachweise 

Problem (Graphentheorie)
Leonhard Euler als Namensgeber