Algorithmus - Hierholzer-Algorithmus

• Involvierte Definitionen:
  • Eulertour
  • Eulerscher Graph
  • Graph
  • Valenz
• Veranstaltung: AlMa
• Referenz: @herzogWiSe22

⠀

Algorithmus: Hierholzer-Algorithmus

Sei ein ungerichteter, eulerscher Graph.

Der Hierholzer-Algorithmus hilft uns bei der Bestimmung von Eulertouren in .

1. Wähle einen beliebigen Knoten . Konstruiere von ausgehend einen Unterkreis in , der keine Kante in zweimal durchläuft.
2. Ist bereits eine Eulertour, breche ab. Andernfalls:
3. Ignoriere alle Kanten des Unterkreises für die Valenzbestimmung der Knoten.
4. Am ersten Knoten von , dessen Valenz größer als ist, lasse einen weiteren Unterkreis entstehen, der keine Kante in durchläuft und keine Kante in zweimal enthält.
5. Füge in den zweiten Kreis ein, indem der Startpunkt von durch alle Punkte von in der richtigen Reihenfolge ersetzt wird.
6. Nenne den so erhaltenen Kreis und fahre bei Schritt 2 fort.

Anmerkung

Komplexität

Die Komplexität des Algorithmus ist linear zu der Anzahl der Kanten von .