Hierholzer-Algorithmus

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₀ des Graphen und konstruiere von v₀ ausgehend einen Unterkreis K in G, der alle Eigenschaften eines Eulerkreises besitzt.
2. Vernachlässige nun alle Kanten dieses Unterkreises.
3. Am ersten Eckpunkt des ersten Unterkreises, dessen Grad größer 0 ist, lässt man nun einen weiteren Unterkreis entstehen, der wiederum ein Eulerkreis ist.
4. Erstelle so viele Unterkreise, bis alle Kanten von einem Unterkreis durchlaufen wurden.
5. Nun erhält man den Eulerkreis, indem man mit dem ersten Unterkreis beginnt und bei jedem Schnittpunkt mit einem anderen Unterkreis, den letzteren einfügt, und danach den ersten Unterkreis wieder bis zu einem weiteren Schnittpunkt oder dem Endpunkt fortsetzt.

Eulergraph mit neun Knoten

Beispiel

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: 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: C_gruen = (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)

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_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_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_gruen = (7,6,9,5,4,9,7) bilden. Setzt man jetzt C_gruen in C_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_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

• Sven Oliver Krumke, Hartmut Noltemeier: Graphentheoretische Konzepte und Algorithmen. Teubner, Wiesbaden 2005, ISBN 3-519-00526-3, S. 45−48

Weblinks

• Applet zur Visualisierung