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 einen Eulerkreis 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 ∈ V {\displaystyle v_{0}\in V} 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 von G ist, also alle Kanten von G enthält, 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'} in G entstehen, der keine Kante in K {\displaystyle K} – also keine schon besuchte Kante – 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 in K der Startknoten von K ′ {\displaystyle K'} durch alle Knoten 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
  • Applet zur Visualisierung
  • Eulerscher Graph. In: Springer Lexikon der Mathematik. (mit einer Darstellung des nach Hierholzer benannten Algorithmus)
  • Oliver Deiser: Der Algorithmus von Hierholzer. In: Einführung in die Mathematik 2.1 – Elementare Zahlentheorie und Graphentheorie. 6. Oktober 2022.