imported>SaschaWolff: /* Literatur */

2026-04-16T09:25:38Z

Literatur

Neue Seite

[[Datei:Hierholzer(1).svg|miniatur|Eulergraph mit neun Knoten]]
[[Datei:Hierholzer(2).svg|miniatur|<math>C_\text{blau}=(1,2,3,7,1) </math>]]
[[Datei:Hierholzer(3).svg|miniatur|Nach Entfernen der blauen Kanten kann man den nächsten Zykel von den Knoten 1, 3 oder 7 startend bilden, hier vom dritten Knoten: <math>C_\text{rot}=(3,1,8,7,4,3)</math>]]
[[Datei:Hierholzer(4).svg|miniatur|Nach Entfernen der roten Kanten kann man den nächsten Zykel von den Knoten 4 und 7 bilden, hier vom siebten Knoten: <math>C_\text{grün}=(7,6,9,5,4,9,7)</math>]]
[[Datei:Hierholzer (5).svg|miniatur|Die so ermittelte Eulertour in alphabetischer Reihenfolge, bzw. mit der Knotenfolge <math>(1,2,3,1,8,7,6,9,5,4,9,7,4,3,7,1)</math>]]

Der '''Algorithmus von Hierholzer''' ist ein [[Algorithmus]] aus dem Gebiet der [[Graphentheorie]], mit dem man in einem [[Graph (Graphentheorie)|ungerichteten Graphen]] einen [[Eulerkreisproblem|Eulerkreis]] bestimmt. Er geht auf Ideen von [[Carl Hierholzer]] zurück.

Voraussetzung: Sei <math>G=(V,E)</math> ein [[zusammenhängender Graph]], der nur [[Knoten (Graphentheorie)|Knoten]] mit geradem [[Grad (Graphentheorie)|Grad]] aufweist.

# Wähle einen beliebigen Knoten <math>v_0 \in V</math> des Graphen und konstruiere von <math>v_0</math> ausgehend einen [[Kreisgraph |Unterkreis]] <math>K</math> in <math>G</math>, der keine Kante in <math>G</math> zweimal durchläuft.
# Wenn <math>K</math> ein Eulerkreis von G ist, also alle Kanten von G enthält, breche ab. Andernfalls:
# Vernachlässige nun alle [[Kante (Graphentheorie)|Kanten]] des Unterkreises <math>K</math>.
# Am ersten Eckpunkt von <math>K</math>, dessen Grad größer 0 ist, lässt man nun einen weiteren Unterkreis <math>K'</math> in G entstehen, der keine Kante in <math>K</math> – also keine schon besuchte Kante – durchläuft und keine Kante in <math>G</math> zweimal enthält.
# Füge in <math>K</math> den zweiten Kreis <math>K'</math> ein, indem in <math>K</math> der Startknoten von <math>K'</math> durch alle Knoten von <math>K'</math> in der richtigen Reihenfolge ersetzt wird.
# Nenne jetzt den so erhaltenen Kreis <math>K</math> und fahre bei Schritt 2 fort.
Die [[Komplexität (Informatik)|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 <math>C_\text{blau}=(1,2,3,7,1) </math>. 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 <math>C_\text{rot}=(3,1,8,7,4,3)</math> bilden (in der dritten Abbildung rot). Wählt man nun als Startknoten den Knoten 7, kann man von den übrig gebliebenen Kanten den Zykel <math>C_\text{grün}=(7,6,9,5,4,9,7)</math> bilden. Setzt man jetzt <math> C_\text{grün}</math> in <math> C_\text{rot}</math> an Stelle des Knoten 7 ein, erhält man den Zykel <math>(3,1,8,7,6,9,5,4,9,7,4,3)</math>. Setzt man diesen in <math>C_\text{blau}</math> an Stelle des Knoten 3 ein, erhält man die mögliche Eulertour <math>(1,2,3,1,8,7,6,9,5,4,9,7,4,3,7,1)</math> 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. [https://eudml.org/doc/156599]
* Sven Oliver Krumke, Hartmut Noltemeier: ''Graphentheoretische Konzepte und Algorithmen.'' Teubner, Wiesbaden 2005, ISBN 3-519-00526-3, S. 45–48

== Weblinks ==
* [https://algorithms.discrete.ma.tum.de/graph-algorithms/hierholzer/index_de.html Applet zur Visualisierung]
* [https://www.spektrum.de/lexikon/mathematik/eulerscher-graph/2843 ''Eulerscher Graph.''] In: ''Springer Lexikon der Mathematik.'' (mit einer Darstellung des nach Hierholzer benannten Algorithmus)
* [[Oliver Deiser]]: [https://www.aleph1.info/?call=Puc&permalink=ema21_2_4_Z2 ''Der Algorithmus von Hierholzer.''] In: ''Einführung in die Mathematik 2.1 – Elementare Zahlentheorie und Graphentheorie.'' 6. Oktober 2022.

[[Kategorie:Algorithmus (Graphentheorie)|Hierholzer]]

Algorithmus von Hierholzer - Versionsgeschichte

imported>SaschaWolff: /* Literatur */