Algorithmus von Hierholzer
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 ein zusammenhängender Graph, der nur Knoten mit geradem Grad aufweist.
- Wähle einen beliebigen Knoten des Graphen und konstruiere von ausgehend einen Unterkreis in , der keine Kante in zweimal durchläuft.
- Wenn ein Eulerkreis ist, breche ab. Andernfalls:
- Vernachlässige nun alle Kanten des Unterkreises .
- Am ersten Eckpunkt von , dessen Grad größer 0 ist, lässt man nun einen weiteren Unterkreis entstehen, der keine Kante in durchläuft und keine Kante in zweimal enthält.
- Füge in den zweiten Kreis ein, indem der Startpunkt von durch alle Punkte von in der richtigen Reihenfolge ersetzt wird.
- Nenne jetzt den so erhaltenen Kreis 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 . 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 bilden (in der dritten Abbildung rot). Wählt man nun als Startknoten den Knoten 7, kann man von den übrig gebliebenen Kanten den Zykel bilden. Setzt man jetzt in an Stelle des Knoten 7 ein, erhält man den Zykel . Setzt man diesen in an Stelle des Knoten 3 ein, erhält man die mögliche Eulertour wie in der letzten Abbildung gezeigt.