Algorithmus von Hierholzer

Eulergraph mit neun Knoten
C blau = ( 1 , 2 , 3 , 7 , 1 ) {\displaystyle 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 rot = ( 3 , 1 , 8 , 7 , 4 , 3 ) {\displaystyle 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 grün = ( 7 , 6 , 9 , 5 , 4 , 9 , 7 ) {\displaystyle 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 ) {\displaystyle (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 ) {\displaystyle G=(V,E)} ein zusammenhängender Graph, der nur Knoten mit geradem Grad aufweist.

  1. Wähle einen beliebigen Knoten v 0 {\displaystyle v_{0}} des Graphen und konstruiere von v 0 {\displaystyle v_{0}} ausgehend einen Unterkreis K {\displaystyle K} in G {\displaystyle G} , der keine Kante in G {\displaystyle G} zweimal durchläuft.
  2. Wenn K {\displaystyle K} ein Eulerkreis ist, breche ab. Andernfalls:
  3. Vernachlässige nun alle Kanten des Unterkreises K {\displaystyle K} .
  4. Am ersten Eckpunkt von K {\displaystyle K} , dessen Grad größer 0 ist, lässt man nun einen weiteren Unterkreis K ′ {\displaystyle K'} entstehen, der keine Kante in K {\displaystyle K} durchläuft und keine Kante in G {\displaystyle G} zweimal enthält.
  5. Füge in K {\displaystyle K} den zweiten Kreis K ′ {\displaystyle K'} ein, indem der Startpunkt von K ′ {\displaystyle K'} durch alle Punkte von K ′ {\displaystyle K'} in der richtigen Reihenfolge ersetzt wird.
  6. Nenne jetzt den so erhaltenen Kreis K {\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 C blau = ( 1 , 2 , 3 , 7 , 1 ) {\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 C rot = ( 3 , 1 , 8 , 7 , 4 , 3 ) {\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 C grün = ( 7 , 6 , 9 , 5 , 4 , 9 , 7 ) {\displaystyle C_{\text{grün}}=(7,6,9,5,4,9,7)} bilden. Setzt man jetzt C grün {\displaystyle C_{\text{grün}}} in C rot {\displaystyle 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 ) {\displaystyle (3,1,8,7,6,9,5,4,9,7,4,3)} . Setzt man diesen in C blau {\displaystyle 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 ) {\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. [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