Eulerzüge

Wir wenden uns nun der Frage zu, ob wir einen Graphen „in einem Zug“ zeichnen können. Zusätzlich sollen Start- und Endpunkt übereinstimmen:

Definition (Eulerzug)

Ein Eulerzug in einem Graphen G = (E, K) ist ein geschlossener Kantenzug a₀, …, a_n = a₀ in G derart, dass jede Kante von G genau einmal besucht wird.

Ein Graph heißt Eulersch, wenn ein Eulerzug existiert.

Ist a₀, …, a_n = a₀ ein Eulerzug in G, so ist n die Größe von G und für die Kantenmenge K gilt K = { a_ia_i + 1 | i < n }. Jeder Kreis C_n, n ≥ 3, ist offenbar Eulersch. Weiter sind z. B. die vollständigen Graphen K₃ und K₅ sowie die vollständigen bipartiten Graphen K_{2, 2} und K_{2, 4} Eulersch, nicht aber die Graphen K₂, K₄ und K_{1, 3}. Hiervon kann man sich leicht überzeugen.

Erstaunlicherweise gibt es ein einfaches Kriterium für die Existenz eines Eulerzuges. Zudem existiert ein schneller und durchsichtiger Algorithmus, mit dessen Hilfe wir Eulerzüge finden können.

Wir beginnen mit folgender Beobachtung:

Satz (notwendiges Kriterium für die Existenz von Eulerzügen)

Sei G = (E, K) Eulersch. Dann haben alle Ecken einen geraden Grad.

Beweis

Sei a₀, a₁, …, a_n = a₀ ein Eulerzug. Sei e eine von a₀ verschiedene Ecke. Besuchen wir die Ecke e insgesamt n-mal auf dem Eulerzug, so werden dabei genau 2n verschiedene Kanten mit der Ecke e besucht, denn wir laufen in die Ecke bei jedem Besuch hinein und wieder hinaus, und keine Kante wird mehrfach besucht. Da alle Kanten des Graphen besucht werden, gilt also d(e) = 2n. Da nun aber auch a₁, …, a_n, a₀, a₁ ein Eulerzug ist, zeigt das Argument auch, dass d(a₀) gerade ist.

Existiert ein Eulerzug in G, so ist G zusammenhängend, wobei wir Ecken vom Grad 0 stillschweigend streichen. Damit haben wir zwei notwendige Bedingungen für die Existenz eines Eulerzuges gefunden. Wir wollen nun zeigen, dass diese beiden Bedingungen auch hinreichend sind. Hierzu ist folgendes Lemma hilfreich:

Satz (Rückkehrlemma)

Sei G = (E, K) ein Graph, und jede Ecke in G habe einen geraden Grad.

Sei a  ∈  E mit d(a) > 0. Dann existiert ein einfacher geschlossener Kantenzug positiver Länge in G, der die Ecke a besucht.

Beweis

Wir starten bei a und besuchen solange eine bislang nicht besuchte Kante, bis wir wieder bei der Ecke a ankommen. (Nach dem „rein-raus“-Argument des obigen Satzes können wir in der Tat immer eine neue Kante finden, wenn wir noch nicht bei a angekommen sind.) Wir erhalten einen nach Konstruktion einfachen und geschlossenen Kantenzug positiver Länge, der a besucht.

Damit zeigen wir nun:

Satz (Kriterium für die Existenz von Eulerzügen)

Sei G = (E, K) ein zusammenhängender Graph, und jede Ecke habe einen geraden Grad. Dann existiert ein Eulerzug in G.

Beweis

Sei Z ein einfacher geschlossener Kantenzug in G der Länge k. Ist k die Größe von G, so ist Z ein Eulerzug. Andernfalls zeigen wir, dass wir Z zu einem einfachen geschlossenen Kantenzug Z⁺ erweitern können, der mehr als k Kanten besucht. Nach endlich vielen Iterationen haben wir dann einen Eulerzug gefunden.

Sei G′ der Graph, der aus G durch Streichen der auf Z besuchten Kanten hervorgeht. Dann hat jede Ecke immer noch einen geraden Grad in G′.

Da G zusammenhängend ist, gibt es eine Ecke a von Z und eine Kante a b, die nicht auf Z besucht wird (!). Nach dem Rückkehrlemma existiert ein einfacher und geschlossener Kantenzug

W = a, b, …, a

in G′. Wir fügen nun W in Z an irgendeiner Stelle ein, an der die Ecke a in Z besucht wird. Der so erhaltene Kantenzug Z⁺ in G ist einfach und geschlossen, und er besucht mehr als k Kanten.

Der reduzierte Graph G′ ist i. A. nicht mehr zusammenhängend. Das Rückkehrlemma setzt aber keinen Zusammenhang voraus.

Aus dem Beweis gewinnen wir den sog. Algorithmus von Hierholzer. Gegeben sei ein zusammenhängender Eulerscher Graph. Wir dürfen annehmen, dass die Eckenmenge des Graphen von der Form E = { 1, …, n } ist. Der Algorithmus konstruiert nun eine Folge von einfachen und geschlossenen Kantenzügen Z₀, …, Z_m in G derart, dass Z_m ein Eulerzug ist.

Algorithmus von Hierholzer

Wir beginnen mit Z₀ = 1.

Ist Z_i konstruiert, aber noch kein Eulerzug, so sei a die erste Ecke auf Z_i, von der eine noch unbesuchte Kante wegführt. Wir konstruieren nun einen einfachen, geschlossenen und in a beginnenden Kantenzug W, indem wir immer die kleinste Ecke wählen, zu der eine bislang unbesuchte Kante hinführt. Finden wir keine solche Ecke mehr, so ist W konstruiert. Wir fügen nun W in Z_i an der ersten Stelle des Besuchs der Ecke a ein und erhalten so Z_i + 1.

Dieses Vorgehen wird solange iteriert, bis ein Eulerzug gefunden ist.

Obiger Beweis zeigt, dass der Algorithmus tatsächlich einen Eulerzug konstruiert: Der bei a beginnende Kantenzug W im Rekursionsschritt endet automatisch wieder bei a.