Das Kefk Network Wiki befindet sich im Testbetrieb.

---

Aus Kefk.

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 v₀ des Graphen und konstruiere von v₀ ausgehend einen Unterkreis K in G, der alle Eigenschaften eines Eulerkreises besitzt.
2. Vernachlässige nun alle Kanten dieses Unterkreises.
3. Am ersten Eckpunkt des ersten Unterkreises, dessen Grad größer 0 ist, lässt man nun einen weiteren Unterkreis entstehen, der wiederum ein Eulerkreis ist.
4. Erstelle so viele Unterkreise, bis alle Kanten von einem Unterkreis durchlaufen wurden.
5. Nun erhält man den Eulerkreis, indem man mit dem ersten Unterkreis beginnt und bei jedem Schnittpunkt mit einem anderen Unterkreis, den letzteren einfügt, und danach den ersten Unterkreis wieder bis zu einem weiteren Schnittpunkt oder dem Endpunkt fortsetzt.

Literatur

• Hartmut Noltemeier: Graphentheoretische Konzepte und Algorithmen. Teubner, Wiesbaden 2005, ISBN 3-519-00526-3, S. 45−48

Weblinks

• Applet zur Visualisierung

Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Algorithmus_von_Hierholzer, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.