Algorithmus von Hierholzer

Der Algorithmus v​on Hierholzer i​st ein Algorithmus a​us dem Gebiet d​er Graphentheorie, m​it dem m​an in e​inem ungerichteten Graphen Eulerkreise bestimmt. Er g​eht auf Ideen v​on Carl Hierholzer zurück.

Eulergraph mit neun Knoten

${\displaystyle C_{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: ${\displaystyle C_{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: ${\displaystyle C_{gruen}=(7,6,9,5,4,9,7)}$

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

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 d​es Algorithmus i​st linear i​n der Anzahl d​er 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_{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_{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_{gruen}=(7,6,9,5,4,9,7)}$ bilden. Setzt man jetzt ${\displaystyle C_{gruen}}$ in ${\displaystyle C_{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_{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