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 G = (V,E) ein zusammenhängender Graph, der nur Knoten mit geradem Grad aufweist.

  1. Wähle einen beliebigen Knoten v0 des Graphen und konstruiere von v0 ausgehend einen Unterkreis K in G, der keine Kante in G zweimal durchläuft.
  2. Wenn K ein Eulerkreis ist, breche ab. Andernfalls:
  3. Vernachlässige nun alle Kanten des Unterkreises K.
  4. Am ersten Eckpunkt von K, dessen Grad größer 0 ist, lässt man nun einen weiteren Unterkreis K' entstehen, der keine Kante in K durchläuft und keine Kante in G zweimal.
  5. Füge in K den zweiten Kreis K' ein, indem der Startpunkt von K' durch alle Punkte von K' in der richtigen Reihenfolge ersetzt wird.
  6. Nenne jetzt den so erhaltenen Kreis K und fahre bei Schritt 2 fort.
Eulergraph mit neun Knoten

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

Beispiel

Cblau = (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: Crot = (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: Cgruen = (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 Cblau = (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 Crot = (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 Cgruen = (7,6,9,5,4,9,7) bilden. Setzt man jetzt Cgruen in Crot 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 Cblau 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


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Hierholzer — ist der Name von Carl Hierholzer (1840 1871), deutscher Mathematiker Klaus Hierholzer (1929−2007), deutscher Arzt und Physiologe Siehe auch: Algorithmus von Hierholzer Diese Seite ist eine …   Deutsch Wikipedia

  • 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 …   Deutsch Wikipedia

  • Carl Hierholzer — (* 2. Oktober 1840 in Freiburg im Breisgau; † 13. September 1871 in Karlsruhe) war ein deutscher Mathematiker. Inhaltsverzeichnis 1 Leben 2 Schriften 3 Einzelnachweise …   Deutsch Wikipedia

  • Euler-Hierholzer-Satz — Der Euler Hierholzer Satz besagt, dass ein Graph genau dann ein Euler’scher Graph ist, wenn er zusammenhängend ist und nur gerade Ecken hat.[1] Ein Eulerscher Graph ist dabei ein Graph, für den ein Eulerkreis existiert, eine Rundtour, die jede… …   Deutsch Wikipedia

  • Euler-Pfad — In kantendisjunkte Kreise zerlegter Eulergraph. Eine Eulertour der Knotenfolge (1,2,3,1,8,7,6,9,5,4,9,7,4,3,7,1) ist in alphabetischer Reihenfolge angegeben. Ein Eulerkreis oder (geschlossener) Eulerzug (auch Eulertour oder Eulersche Linie) ist… …   Deutsch Wikipedia

  • Euler-Zug — In kantendisjunkte Kreise zerlegter Eulergraph. Eine Eulertour der Knotenfolge (1,2,3,1,8,7,6,9,5,4,9,7,4,3,7,1) ist in alphabetischer Reihenfolge angegeben. Ein Eulerkreis oder (geschlossener) Eulerzug (auch Eulertour oder Eulersche Linie) ist… …   Deutsch Wikipedia

  • Eulerkreis — In kantendisjunkte Kreise zerlegter Eulergraph. Eine Eulertour der Knotenfolge (1,2,3,1,8,7,6,9,5,4,9,7,4,3,7,1) ist in alphabetischer Reihenfolge angegeben. Ein Eulerkreis oder (geschlossener) Eulerzug (auch Eulertour oder Eulersche Linie) ist… …   Deutsch Wikipedia

  • Eulerkreis-Problem — In kantendisjunkte Kreise zerlegter Eulergraph. Eine Eulertour der Knotenfolge (1,2,3,1,8,7,6,9,5,4,9,7,4,3,7,1) ist in alphabetischer Reihenfolge angegeben. Ein Eulerkreis oder (geschlossener) Eulerzug (auch Eulertour oder Eulersche Linie) ist… …   Deutsch Wikipedia

  • Eulerpfad — In kantendisjunkte Kreise zerlegter Eulergraph. Eine Eulertour der Knotenfolge (1,2,3,1,8,7,6,9,5,4,9,7,4,3,7,1) ist in alphabetischer Reihenfolge angegeben. Ein Eulerkreis oder (geschlossener) Eulerzug (auch Eulertour oder Eulersche Linie) ist… …   Deutsch Wikipedia

  • Eulersch — In kantendisjunkte Kreise zerlegter Eulergraph. Eine Eulertour der Knotenfolge (1,2,3,1,8,7,6,9,5,4,9,7,4,3,7,1) ist in alphabetischer Reihenfolge angegeben. Ein Eulerkreis oder (geschlossener) Eulerzug (auch Eulertour oder Eulersche Linie) ist… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”