Chr.Nelius: Graphentheorie (WS 2015/16)
19
Kap. II: Euler– und Hamilton–Graphen
§7 : Euler–Graphen
Das Königsberger Brückenproblem:
Gibt es einen Rundweg durch die vier Stadtteile von Königsberg, der über jede der sieben Brücken
genau einmal führt? In der abgeschwächten Form des Problems wird darauf verzichtet, dass man
wieder zum Ausgangspunkt zurückkommen muss .
(7.1) DEF: Sei G ein Graph.
a) Ein nichtgeschlossener Kantenzug, in dem jede Kante von G genau einmal vorkommt, heißt eine
Euler–Tour in G .
b) Ein geschlossener Kantenzug, in dem jede Kante von G genau einmal vorkommt, heißt eine
Euler–Rundtour in G .
(7.2) BEM: Eine Euler–Tour muss kein Weg sein, eine Euler–Rundtour muss kein Kreis sein.
b) Eine Euler–Tour oder eine Euler–Rundtour können Ecken mehrfach durchlaufen.
!
(7.3) BEM: Wir können jetzt das Königsberger Brückenproblem in der Sprache der Graphen
formulieren. Dabei werden die Stadtteile als Ecken und die Brücken als Kanten interpretiert:
Gibt es in dem Graphen
C
A
D
B
eine Euler–Rundtour (abgeschwächt: eine Euler–Tour) ?
(7.4) DEF: Ein Graph heißt ein Euler–Graph , wenn er zusammenhängend ist und wenn es in
ihm eine Euler–Rundtour gibt.
(7.5) BEM: Ein Graph kann eine Euler–Rundtour enthalten, ohne dass er zusammenhängend ist:
α
ist unzusammenhängend und besitzt die Euler–Rundtour (α, β) .
Der Graph
β
Chr. Nelius: Graphentheorie (WS 2015/16)
20
(7.6) SATZ: Euler (1736)
Ist G ein Euler–Graph, so ist jede Ecke von G gerade.
(7.7) FOLG: Es gibt keine Lösung für das Königsberger Brückenproblem.
Bew: Annahme: das Königsberger Brückenproblem wäre lösbar. Dann müßte der in (7.3) angegebene
Graph ein Euler–Graph sein. Nach (7.6) wäre dann aber jede Ecke gerade im Widerspruch dazu,
dass der Graph die Gradfolge (3, 3, 3, 5) besitzt.
Diese Lösung des Königsberger Brückenproblems findet sich in der Arbeit ”Solutio
problematis ad geometriam situs pertinensis” von Euler aus dem Jahre 1736 .
Wir wollen jetzt die umgekehrte Frage behandeln:
Ist ein Graph G, in dem jede Ecke gerade ist, ein Euler–Graph ?
In dem folgenden unzusammenhängenden Graphen ist zwar jede Ecke gerade, es gibt jedoch keine
Euler–Rundtour:
Für zusammenhängende Graphen ist die Umkehrung aber richtig. Dies hatte Euler in der Originalarbeit von 1736 als (unbewiesenes) Ergebnis formuliert, ein erster Beweis wurde aber erst von
Carl Hierholzer gegeben (“Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren” Mathematische Annalen 6 (1873), 30–32) . Für den Beweis benötigen wir
das folgende Ergebnis:
(7.8) SATZ: Ist G ein Graph mit δ(G) ≥ 2 , so gibt es einen Kreis in G .
(7.9) SATZ:
Euler (1736) / Hierholzer (1873)
Für einen Graphen G mit mindestens 2 Ecken sind folgende Aussagen äquivalent:
a) G ist ein Euler–Graph
b) G ist zusammenhängend, und jede Ecke von G ist gerade.
Bew: a) =⇒ b)
Ein Euler–Graph ist nach Definition zusammenhängend, und nach (7.6) ist jede Ecke gerade.
21
Chr. Nelius: Graphentheorie (WS 2015/16)
b) =⇒ a)
Da G zusammenhängend ist und mindestens 2 Ecken hat, besitzt G keine isolierte Ecke. Da jede
Ecke nach Voraussetzung gerade ist, folgt δ(G) ≥ 2 . Nach (7.8) gibt es daher einen Kreis in G .
Die weitere Beweisidee soll an einem Beispiel klargemacht werden:
α ist ein Kreis in dem Graphen G (linkes Bild) , der zusammenhängend ist und in dem jede Ecke
gerade ist. Wir wollen uns überlegen, wie wir eine Euler–Rundtour finden können.
9
G
9
8
8
3
β
3
β
2
4
2
G1
4
G1
7
1
5
7
1
5
α
0
6
14
13
G2
0
11
10
γ
12
6
14
13
G2
11
10
γ
12
Nach Entfernen der Kanten von α entstehen aus G die vier Untergraphen {0} , {4} , G1 und G2
(rechtes Bild) . G1 und G2 sind zusammenhängend, haben nur gerade Ecken und haben weniger
Kanten als G . (Damit ist die Möglichkeit für einen Induktionsbeweis gegeben !) In den beiden
Untergraphen G1 bzw. G2 gibt es die Euler–Rundtouren β bzw. γ .
Aus α , β und γ läßt sich nun folgendermaßen eine Euler–Rundtour in G zusammensetzen: Starte
etwa in der Ecke 0 , gehe bis zur ersten Ecke, die zu β gehört (das ist hier 1) , durchlaufe die Rundtour
β zurück zur Ecke 1 , gehe weiter den Kreis entlang bis zur ersten Ecke von γ (hier 5) , durchlaufe
die Rundtour γ zurück zur Ecke 5 , gehe weiter den Kreis entlang bis zur Ausgangsecke 0 . Dies
ergibt die Euler–Rundtour
0−1−7−3−8−9−3−2−1−2−3−4−5−10−11−12−13−14−6−12−11−5−6−0 ,
die jede der 23 Kanten von G genau einmal enthält.
22
Chr. Nelius: Graphentheorie (WS 2015/16)
(7.10) Der Algorithmus von Fleury
Mit dem Algorithmus von Fleury läßt sich in einem Euler–Graphen G eine Euler–Rundtour finden:
Starte mit irgendeiner Ecke von G und durchlaufe die Kanten von G in einer beliebigen Reihenfolge,
wobei nur die beiden folgenden Regeln zu beachten sind:
• Entferne jede durchlaufene Kante und jede dabei entstandene isolierte Ecke
• Bei jedem Schritt darf eine Brücke in dem neu entstandenen Graphen nur dann benutzt werden,
wenn es nicht anders geht.
(7.11) SATZ: Für einen zusammenhängenden Graphen G sind folgende Aussagen äquivalent:
a) Es gibt eine Euler–Tour in G
b) G besitzt genau zwei ungerade Ecken .
(7.12) BEM: a) Existiert in einem zusammenhängenden Graphen eine Euler–Tour, so verbindet
sie die beiden ungeraden Ecken.
b) Auch die abgeschwächte Form des Königsberger Brückenproblems hat keine Lösung, da es in
dem zugehörigen Graphen (7.3) vier ungerade Ecken gibt.
c) Beginnt man mit einer ungeraden Ecke, so liefert der Algorithmus von Fleury eine Euler–Tour.
d) Euler-Touren oder Euler–Rundtouren zu finden, ist bei solchen mathematischen Spielereien
erforderlich, bei denen eine bestimmte Figur in einem Zug gezeichnet werden soll, ohne eine Linie
doppelt zu zeichnen (vgl. Titel der Arbeit von Hierholzer). Aus früher Kindheit ist allen sicher noch
die Aufgabe in Erinnerung, das “Haus der Nikolaus” in einem Zug zu zeichnen:
a
c
b
u
v
N:
Beginnend mit der ungeraden Ecke u finden wir z.B. die Euler–Tour
u−b−c−v−u−c−a−b−v
in N , die bei der anderen ungeraden Ecke v ankommt.
© Copyright 2024 ExpyDoc
