Kreiszerlegungen
Wir wollen nun die Eigenschaft „Alle Ecken haben einen geraden Grad“ noch etwas weiter analysieren. Hierzu beweisen wir zunächst einen allgemeinen Satz über die Zerlegung von einfachen geschlossenen Kantenzügen:
Satz (Kreiszerlegung von Kantenzügen)
Sei G = (E, K) ein Graph, und sei Z ein einfacher geschlossener Kantenzug in G positiver Länge. Dann lässt sich Z in Kreise C1, …, Cm mit disjunkten Kanten zerlegen, sodass Z = Cm + Cm − 1 + … + C1.
Beweis
Sei Z = a0, a1, …, an, a0. Wird keine Ecke außer der Startecke a0 zweimal besucht, so ist Z bereits ein Kreis (da Z einfach ist, ist n ≥ 2). Andernfalls sei j < n minimal derart, dass der verkürzte Kantenzug
a0, …, aj
die Ecke aj zweimal besucht. Nach minimaler Wahl von j gibt es ein eindeutiges 0 ≤ i < j mit ai = aj. Wir setzen nun
| C | = ai, …, aj |
| Z′ | = a0, …, ai, aj + 1, …, an, a0 |
Dann ist Z′ ein einfacher geschlossener Kantenzug positiver Länge. Nach Konstruktion ist C ein Kreis und die Mengen der von Z′ und C besuchten Kanten sind disjunkt, da Z einfach ist. Weiter gilt Z = Z′ + C. Eine endliche Wiederholung dieses Verfahrens liefert die gewünschte Zerlegung.
Beispiel
Wir betrachten den folgenden Graphen und den einfachen geschlossenen Kantenzug Z mit
Z = 1, 2, 3, 4, 5, 6, 7, 8, 5, 9, 3, 10, 1
Das Verfahren der Kreiszerlegung liefert mit Z0 = Z:
| Z0 | = 1, 2, 3, 4, 5, 6, 7, 8, 5, 9, 3, 10, 1 |
| C1 | = 5, 6, 7, 8, 5 |
| Z1 | = 1, 2, 3, 4, 5, 9, 3, 10, 1 |
| C2 | = 3, 4, 5, 9, 3 |
| Z2 | = 1, 2, 3, 10, 1 |
| C3 | = 1, 2, 3, 10, 1 |
Damit ist Z in die disjunkten Kreise C1, C2 und C3 zerlegt:
Z = C3 + C2 + C1.
Der nichteinfache geschlossene Kantenzug Z = 1, 2, 3, 10, 2, 1 in G kann nicht in Kreise zerlegt werden. Dies zeigt, dass die Forderung der Einfachheit wesentlich ist.
Die Kantenzüge W0, …, W3 des obigen Beispiels zum Algorithmus von Hierholzer sind eine Kreiszerlegung des gefundenen Euler-Zugs. Im Allgemeinen sind die Kantenzüge Wi, die der Algorithmus erzeugt, jedoch keine Kreise, sondern lediglich geschlossen und einfach.
Nach diesen Vorbereitungen zeigen wir:
Satz (Satz von Veblen, Kreiszerlegungssatz)
Sei G = (E, K) ein Graph. Dann sind äquivalent:
(1) | G ist gerade. |
(2) | Es existieren Kreise C1, …, Cm in G derart, dass jede Kante von G von genau einem Kreis besucht wird. |
Wir nennen Kreise C1, …, Cm wie in (2) auch eine Kreiszerlegung von G.
Beweis
(1) impliziert (2): Der Graph G besitze gerade Grade. Der Satz von Euler-Hierholzer liefert Euler-Züge für jede Zusammenhangskomponente von G. Obiger Satz über die Kreiszerlegung von Kantenzügen beschert uns mit einer Kreiszerlegung für jede Zusammenhangskomponente. Zusammengenommen bilden diese Zerlegungen eine Kreiszerlegung von G wie gewünscht.
(2) impliziert (1): Sei C1, …, Cm eine Kreiszerlegung von G. Weiter sei a ∈ E beliebig. Kommt die Ecke a in genau r der Kreise C1, …, Cm vor, so gilt d(a) = 2r. Denn jeder der r Kreise besucht genau zwei Kanten mit a als Ecke, und diese Kantenpaare sind nach Voraussetzung disjunkt. Dies zeigt, dass d(a) gerade ist. Damit hat G gerade Grade.
Eine Kreiszerlegung eines Graphen in 6 Kreise