Weitere Ergebnisse
Die Analyse des Problems „Durchlaufe alle Kanten“ ist mit den obigen Ergebnissen keineswegs abgeschlossen. Eine Frage ist zum Beispiel:
Was gilt, wenn auf die Forderung „geschlossen“ verzichtet wird?
Wir definieren hierzu:
Definition (offener Euler-Zug)
Sei G = (E, K) ein Graph. Ein offener Euler-Zug in G ist ein einfacher Kantenzug Z = a0, …, an mit a0 ≠ an, der jede Kante von G genau einmal besucht.
Ein bekanntes Beispiel ist:
Beispiel
Sei G = (E, K) mit E = { 1, …, 5 } und K = { 12, 13, 14, 23, 24, 34, 35, 45 }.
Das Haus vom Nikolaus
Der Kantenzug
Z = 1, 2, 3, 4, 1, 3, 5, 4, 2
ist ein offener Euler-Zug von 1 nach 2 in G.
Ohne große Schwierigkeiten erhalten wir:
Satz (Existenz offener Euler-Züge)
Sei G = (E, K) zusammenhängend, und seien a, b zwei verschiedene Ecken von G. Dann sind äquivalent:
(1) | Es gibt einen offenen Euler-Zug von a nach b. |
(2) | a und b sind die einzigen Ecken von G mit einem ungeraden Grad. |
Beweis
Wir führen eine neue Ecke e und zwei neue Kanten ae* und be* ein. Der so entstehende Graph G′ ist gerade und weiterhin zusammenhängend. Nun folgt die Äquivalenz der beiden Bedingungen aus den bisherigen Resultaten, denn ein geschlossener Euler-Zug in G′ führt zu einem offenen Euler-Zug von a nach b in G und umgekehrt.
Der Beweis zeigt, dass ein offener Euler-Zug mit Hilfe des Algorithmus von Hierholzer gefunden werden kann, falls die Grad-Bedingung (2) des Satzes erfüllt ist. Alternativ können wir den Algorithmus modifizieren, sodass der Übergang zu G′ unnötig wird: Starten wir bei a und durchlaufen wir solange möglich unbesuchte Kanten, so endet der entstehende einfache Kantenzug irgendwann bei b (Rein-Rauslaufen-Argument). Der Rest ist wie zuvor.
Mehrfacher Kantenbesuch
Eine weitere natürliche Frage lautet:
Was können wir ohne Grad-Forderung erreichen?
Ein Resultat im Umfeld der obigen Ergebnisse ist folgender Satz:
Satz (zweifacher Kantenbesuch)
Sei G = (E, K) ein zusammenhängender Graph. Dann gibt es einen geschlossenen Kantenzug Z in G, der jede Kante genau zweimal besucht. Weiter kann erreicht werden, dass in Z jede Kante in beiden Richtungen durchlaufen wird.
Wir diskutieren Beweise dieses bemerkenswert allgemeinen Ergebnisses in den Übungen. Neben einer Version des Hierholzer-Algorithmus existiert ein Algorithmus, der den gesuchten Kantenzug mit Hilfe von an den Kanten angebrachten Markierungspfeilen in einem Durchlauf − ohne späteres Einfügen von geschlossenen Kantenzügen − findet.
Schließlich erwähnen wir noch ein offenes Problem im Umfeld des Satzes von Veblen:
Vermutung von Szekeres und Seymour
Sei G = (E, K) ein Graph ohne Brücke. Dann lässt sich G so durch Kreise
C1, …, Ck überdecken, dass jede Kante genau zweimal besucht wird.
Brücken spielen bei der Kreisbildung in einem Graphen eine wichtige Rolle: Ist ab eine Brücke von G, so gibt es gar keinen Kreis in G, der ab besucht. Damit ist die Brückenfreiheit notwendig für jede Form der Kreisüberdeckung. Die Vermutung besagt, dass bei Brückenfreiheit eine relativ einfache Überdeckung von G durch Kreise möglich ist. Für eine einfache Kreiszerlegung reicht diese Voraussetzung nicht, wie der Satz von Veblen zeigt: Die Existenz einer einzigen Ecke mit einem ungeraden Grad schließt eine einfache Kreiszerlegung aus.
Beispiele
(1) | Sei G = (E, K) mit E = { 1, …, 8 } und K = { 12, 14, 23, 34, 35, 56, 58, 67, 78 }. Die Brücke 35 verhindert die Zerlegung von G in Kreise. |
(2) | Sei G = (E, K) mit E = { 1, …, 7 } und K = { 12, 14, 16, 23, 27, 34, 45, 56, 67 }. Der Graph G besitzt keine Brücke. Die Gradfolge ist 2, 2, 2, 3, 3, 3, 3. Die vier Kreise C1 = 1, 2, 3, 4, 1 C2 = 1, 4, 5, 6, 1 C3 = 1, 6, 7, 2, 1 C4 = 2, 3, 4, 5, 6, 7, 2 bilden eine Überdeckung von G, bei der jede Kante genau zweimal besucht wird. Der geschlossene Kantenzug Z = 1, 4, 3, 2, 1, 6, 5, 4, 1, 2, 7, 6, 1 besucht die inneren Kanten genau zweimal und die äußeren genau einmal. Der Kantenzug Z + C4 durchläuft jede Kante genau zweimal mit unterschiedlichen Durchlaufrichtungen. |