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 ${\displaystyle G=(V,E)}$ ein zusammenhängender Graph, der nur Knoten mit geradem Grad aufweist.

1. Wähle einen beliebigen Knoten ${\displaystyle v_{0}}$ des Graphen und konstruiere von ${\displaystyle v_{0}}$ ausgehend einen Unterkreis ${\displaystyle K}$ in ${\displaystyle G}$, der keine Kante in ${\displaystyle G}$ zweimal durchläuft.
2. Wenn ${\displaystyle K}$ ein Eulerkreis ist, breche ab. Andernfalls:
3. Vernachlässige nun alle Kanten des Unterkreises ${\displaystyle K}$.
4. Am ersten Eckpunkt von ${\displaystyle K}$, dessen Grad größer 0 ist, lässt man nun einen weiteren Unterkreis ${\displaystyle K'}$ entstehen, der keine Kante in ${\displaystyle K}$ durchläuft und keine Kante in ${\displaystyle G}$ zweimal enthält.
5. Füge in ${\displaystyle K}$ den zweiten Kreis ${\displaystyle K'}$ ein, indem der Startpunkt von ${\displaystyle K'}$ durch alle Punkte von ${\displaystyle K'}$ in der richtigen Reihenfolge ersetzt wird.
6. Nenne jetzt den so erhaltenen Kreis ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle C_{\text{grün}}=(7,6,9,5,4,9,7)}$ bilden. Setzt man jetzt ${\displaystyle C_{\text{grün}}}$ in ${\displaystyle C_{\text{rot}}}$ an Stelle des Knoten 7 ein, erhält man den Zykel ${\displaystyle (3,1,8,7,6,9,5,4,9,7,4,3)}$. Setzt man diesen in ${\displaystyle C_{\text{blau}}}$ an Stelle des Knoten 3 ein, erhält man die mögliche Eulertour ${\displaystyle (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.
• Sven Oliver Krumke, Hartmut Noltemeier: Graphentheoretische Konzepte und Algorithmen. Teubner, Wiesbaden 2005, ISBN 3-519-00526-3, S. 45–48

Weblinks

• Applet zur Visualisierung