Algorithmus von Hierholzer

Eulergraph mit neun Knoten

$C_{\text{blau}}=(1,2,3,7,1)$

Nach Entfernen der blauen Kanten kann man den nächsten Zykel von den Knoten 1, 3 oder 7 startend bilden, hier vom dritten Knoten: $C_{\text{rot}}=(3,1,8,7,4,3)$

Nach Entfernen der roten Kanten kann man den nächsten Zykel von den Knoten 4 und 7 bilden, hier vom siebten Knoten: $C_{\text{grün}}=(7,6,9,5,4,9,7)$

Die so ermittelte Eulertour in alphabetischer Reihenfolge, bzw. mit der Knotenfolge $(1,2,3,1,8,7,6,9,5,4,9,7,4,3,7,1)$

Der Algorithmus von Hierholzer ist ein Algorithmus aus dem Gebiet der Graphentheorie, mit dem man in einem ungerichteten Graphen Eulerkreise bestimmt. Er geht auf Ideen von Carl Hierholzer zurück.

Voraussetzung: Sei $G=(V,E)$ ein zusammenhängender Graph, der nur Knoten mit geradem Grad aufweist.

1. Wähle einen beliebigen Knoten $v_{0}$ des Graphen und konstruiere von $v_{0}$ ausgehend einen Unterkreis $K$ in $G$, der keine Kante in $G$ zweimal durchläuft.
2. Wenn $K$ ein Eulerkreis ist, breche ab. Andernfalls:
3. Vernachlässige nun alle Kanten des Unterkreises $K$.
4. Am ersten Eckpunkt von $K$, dessen Grad größer 0 ist, lässt man nun einen weiteren Unterkreis $K'$ entstehen, der keine Kante in $K$ durchläuft und keine Kante in $G$ zweimal enthält.
5. Füge in $K$ den zweiten Kreis $K'$ ein, indem der Startpunkt von $K'$ durch alle Punkte von $K'$ in der richtigen Reihenfolge ersetzt wird.
6. Nenne jetzt den so erhaltenen Kreis $K$ und fahre bei Schritt 2 fort.

Die Komplexität des Algorithmus ist linear in der Anzahl der Kanten.

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 $C_{\text{blau}}=(1,2,3,7,1)$. Nach Entfernen dieser Kanten haben die Knoten 1, 3 und 7 der bisher gebildeten Zykel 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 $C_{\text{rot}}=(3,1,8,7,4,3)$ bilden (in der dritten Abbildung rot). Wählt man nun als Startknoten den Knoten 7, kann man von den übrig gebliebenen Kanten den Zykel $C_{\text{grün}}=(7,6,9,5,4,9,7)$ bilden. Setzt man jetzt $C_{\text{grün}}$ in $C_{\text{rot}}$ an Stelle des Knoten 7 ein, erhält man den Zykel $(3,1,8,7,6,9,5,4,9,7,4,3)$. Setzt man diesen in $C_{\text{blau}}$ an Stelle des Knoten 3 ein, erhält man die mögliche Eulertour $(1,2,3,1,8,7,6,9,5,4,9,7,4,3,7,1)$ wie in der letzten Abbildung gezeigt.

Literatur

• Carl Hierholzer: Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren. Mathematische Annalen VI (1873), 30–32. [1]
• Sven Oliver Krumke, Hartmut Noltemeier: Graphentheoretische Konzepte und Algorithmen. Teubner, Wiesbaden 2005, ISBN 3-519-00526-3, S. 45–48

Weblinks

• Applet zur Visualisierung