Der Algorithmus von Hierholzer
Aus dem Beweis der hinreichenden Bedingung von Euler und Hierholzer lässt sich folgender Algorithmus zur Konstruktion eines Euler-Zugs gewinnen.
Algorithmus von Hierholzer
Sei G = (E, K), E = { 1, …, n }, ein zusammenhängender gerader Graph. Weiter sei a ∈ E beliebig (die sog. Startecke). Wir konstruieren rekursiv eine Folge Z0, …, Zk von einfachen geschlossenen Kantenzügen wie folgt.
Zu Beginn sei Z0 = a (Länge 0).
Ist Zi konstruiert und hat Zi die Länge |K|, so stoppen wir mit Ergebnis Zi. Andernfalls sei b die erste auf Zi besuchte Ecke, von der eine noch nicht besuchte Kante wegführt. Nun konstruieren wir einen einfachen geschlossenen Kantenzug
Wi = b, …, b,
indem wir unbesuchte Kanten durchlaufen, bis wir wieder bei b ankommen; dabei wählen wir an jeder Stelle die kleinstmögliche Ecke. Nun setzen wir
Zi + 1 = Zi + Wi(Einfügen von Wi in Zi beim ersten Besuch von b)
und wiederholen das Verfahren.
Bevor wir Beispiele betrachten, einige Bemerkungen.
Bemerkung
(1) | Nach dem obigen Beweis ist der Algorithmus korrekt, d. h., es wird ein Euler-Zug gefunden. Das Verfahren ist zudem sehr effizient. Die Laufzeit ist linear in der Größe |K| des Graphen. |
(2) | Die Wahl der kleinstmöglichen Ecke in der Definition von Wi stellt sicher, dass das Verfahren deterministisch verläuft: Jeder Anwender erzeugt denselben Euler-Zug, wenn er dem Algorithmus mit der gleichen Startecke folgt. Prinzipiell ist jeder Kantenzug Wi, der nur unbesuchte Kanten durchläuft, geeignet. |
(3) | Wir können den Algorithmus auch mit einem beliebigen Graphen mit der Eckenmenge { 1, …, n } durchführen (ohne Forderung des Zusammenhangs und gerader Grade). Ist Z0 = a, so versucht der Algorithmus, einen Euler-Zug für die Zusammenhangskomponente von a zu finden. Dies gelingt genau dann, wenn alle Ecken in dieser Zusammenhangskomponente einen geraden Grad besitzen. Andernfalls laufen wir irgendwann in eine Ecke hinein, von der keine unbesuchte Kante mehr wegführt. |
Beispiel
Sei G = (E, K) mit E = { 1, …, 7 } und
K = { 12, 13, 14, 16, 23, 24, 26, 34, 35, 45, 46, 47, 56, 57 }
Der Graph ist zusammenhängend und gerade:
a | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
d(a) | 4 | 4 | 4 | 6 | 4 | 4 | 2 |
Der Algorithmus von Hierholzer verläuft wie folgt:
| Z0 = 1 | W0 = 1, 2, 3, 1 |
| Z1 = Z0 + W0 = 1, 2, 3, 1 | W1 = 1, 4, 2, 6, 1 |
| Z2 = Z1 + W1 = 1, 4, 2, 6, 1, 2, 3, 1 | W2 = 4, 3, 5, 4 |
| Z3 = Z2 + W2 = 1, 4, 3, 5, 4, 2, 6, 1, 2, 3, 1 | W3 = 4, 6, 5, 7, 4 |
| Z4 = Z3 + W3 = 1, 4, 6, 5, 7, 4, 3, 5, 4, 2, 6, 1, 2, 3, 1 | Euler-Zug in G |
Das folgende Diagramm zeigt die konstruierten geschlossenen Kantenzüge W0, …, W3, aus denen der Euler-Zug Z4 durch Einfügen erzeugt wird: