7 Eulersche Graphen
Definition 7.1
- A closed walk in a graph an Euler tour if it traverses every edge of the graph exactly once.
- A graph is Eulerian if it admits an Euler tour.
Satz 7.2 (Euler, 1736)
\(G\) Eulersch \(\eq\) alle Knoten sind gerades Grades.
Definition 7.3
Ein Kantenzug ist semi-eulersch: \(\Longleftrightarrow\) jede Kante genau einmal vorkommt.
Ein Graph ist semi-eulersch : \(\eq\) Graph enthält einen semi-eulerschen Kantenzug.
Satz 7.4
Ein Graph is semi-eulersch \(\eq\) genau zwei Knoten sind ungerades Grades.
Beweis
Beweis verläuft durch Verbindung der Knoten mit ungeradem Grad und Anwendung des vorheriges Satzes.
Example
Das beliebte Kinderrätsel “Das ist das Haus vom Nikolaus“ enthält einen Eulerweg, aber keinen Eulerkreis, da sein Graph zwei Knoten vom Grad 3 enthält.
Satz 7.5
Ein nicht-trivialer zusammenhängender Graph \(G\) ist Eulersch \(\eq\) \(G\) läßt sich in die kantendisjunkten Kreise zerlegen (d.h. der Graph ist Vereinigung von kantendisjunkten Kreisen)
Beweis
Ist G eulersch, dann ist G zusammenhängend und jeder Knoten hat geraden Grad. Damit enthält G (nach Satz 3.8) einen Kreis C der Länge \(\delta(G)+1\). In \(G^\prime = G - E(C)\) sind wieder alle Knoten geraden Grades. Nach Entfernen von Knoten vom Grad 0 in \(G^\prime\) können wir erneut den Satz 3.8 anwenden und so weiter. Das Ergebnis ist eine Zerlegung von G in kantendisjunkten Kreise.
Umgekehrt gilt, wenn G in kantendisjunkten Kreise zerlegt werden kann, haben alle Knoten geraden Grad. Die Behauptung folgt mit dem Satz 7.2.
Example
In kantendisjunkte Kreise zerlegter Eulergraph:
Eine Eulertour der Knotenfolge (1, 2, 3, 1, 8, 7, 6, 9, 5, 4, 9, 7, 4, 3, 7, 1) ist in alphabetischer Reihenfolge angegeben.
Satz 7.6
Jeder zusammenhängende nicht-triviale Graph besitzt eine geschlossene Kantenfolge, in der jede Kante genau zweimal vorkommt.
Beweis
Im Beweis 7.2 haben wir nicht verwendet, dass G schlicht sein soll. Der Beweis gilt ebenso für Multigraphen. Definiere G‘ als Kopie von G, wobei jede Kante genau zwei mal zugefügt wird. Dann gilt, dass G‘ nur gerade Knotengraden hat und damit laut Satz 7.2 eulersch. Der geschloßene Knotenzug durchläuft alle Ursprungskanten zwei mal.
Satz 7.7
Sei \(p \in \mathbb{N}\) und \(G\) ein zusammenhängender Graph mit genau \(2p\) Knoten ungerades Grades. Dann gilt:
- G läßt sich in \(p\) kantendisjunkten offenen Kantenzüge \(Z_{1}, Z_{2}, ...,Z_n\) zerlegen, deren Anfangs- und Endknoten die \(2p\) Knoten ungerades Grades sind.
- Ist \(W_{1}, W_{2}, ..., W_{r}\) eine Zerlegung von \(G\) in \(r\) kantendisjunkten Kantenzüge, so gilt \(r \geq p\).
Beweis
Die Knoten ungeraden Grades fassen wir zu beliebigen Paaren \((a_1,b_1), \ldots, (a_p,b_p)\) zusammen und füge p neue Kanten \(a_1 b_1, \ldots, a_p b_p\) zu Graphen G hinzu. In den so enstandenen Graph \(G^\prime\) hat jeder Knoten den geraden Grad und damit ist \(G^\prime\) eulersch. Die Eulertour (ein geschloßener Kantenzug) \(Z_1\) einthält auch die p neue Kanten. Nach Entfernen bleiben Abschnitte \(Z_1, \ldots, Z_p\) übrig mit den 2p Knoten als Angangs- und Endknoten.
Angenommen, r < p. Dann gibt es höchstens 2r Knoten ungerades Grades, da alle andere Knoten inneren Knoten der Kantenzüge \(W_1, \ldots, W_r\) sind. Widerspruch.
Satz 7.8
Sei \(G\) ein nicht-trivialer, zusammenhangender Graph. Dann gilt:
\(G\) is Eulersch \(\eq\) jede Kante von G auf einer geraden Anzahl unterschiedlichen Kreise liegt.
Gute Knoten in Eulerschen Graphen
Definition 7.9
- Sei \(G=(V,E)\) ein eulerscher Graph. Sei \(Z=(v_{1},e_{1},v_{2},\dots,e_{p},v_{p+1})\) ein Kantenzug in \(G\). Ein Kantenzug \[ W'=(v_{1},e_{1},v_{2},\dots,e_{p+r},v_{p+r+1}) \] mit \(r>1\) heißt Fortsetzung von \(Z\).
- Ein Knoten \(u\in V\) heißt gut, wenn jeder Kantenzug in \(G\) mit Anfangsknoten \(u\) zu einer Eulertour fortgesetzt werden kann.
Definition 7.10
Die zyklomatische Zahl \(\mu(G)\) eines Graphen \(G\) entspricht die minimale Zahl von Kanten, welche entfernt werden müssen, damit der resultierende Graph azyklisch / kreisfrei wird: \[\mu(G) := m(G) - n(G) + c(G)\] wobei \(c(G)\) ist die Anzahl der Komponente von G.
Beispiel
- Bei einem Wald ist \[\mu(G) = (n(G) - 1 - n(G) + c(G) = 0.\]
- Bei einem Kreis \(C_n\) ist \[\mu(C_n) = n - n + 1 = 1\]
- Bei einem vollständigen Graph \(K_n\) ist \[\mu(K_n) = \frac{(n-1)(n-2)}{2}\]
Bemerkung
Daraus folgt insbesondere, dass für einen Graphen \(G\) gilt:
- \(\mu(G) = 0 \eq G\) ist ein Wald (d.h. azyklisch);
- \(\mu(G) = 1 \eq G\) enthält einen Kreis.
Satz 7.11 (Ore, 1951)
Sei \(G\) eulersch und \(u \in V(G)\). Die Folgende Aussagen sind äquivalent:
- \(u\) ist gut
- Alle Kreise von \(G\) gehen durch \(u\)
- \(G - u\) ist ein Wald
- \(c(G - u) = d_G(u) - \mu(G) - s(u)\),
wobei \(s(u)\) die Anzahl der Schlinge (Loops) inzident zu u, was bei einem schlichten Graph \(s(u) = 0\) entspricht.
Folgerung
Ist G ein Kreis, dann sind alle Knoten gut.
Satz 7.12
Ein Eulersche Graph, der keinen Kreis ist, besitzt zwei gute Knoten.
Satz 7.13
Sei \(G\) ein Eulerscher Graph mit einem guten Knoten \(u\), so gilt:
- \(d_G(u)=\Delta(G)\),
- Jeder Knoten \(v\) mit \(d_G(v)=\Delta(G)\) ist gut.
Eulersche Digraphen
Definition 7.14 (Gerichteter Graph)
Ein gerichteter Graph oder Digraph ist ein Paar \(D = (V, A)\) disjunkte Menge von Knoten und Bogen(Arcs) wofür \(A\) geordnete Paaren der Knoten enthalt.
Definition 7.15 (Semi-Eulerscher Digraph)
Sei \(D\) nicht triviale zusammengehende Digraph. \(D\) ist semi-eulersch: \(\eq\) existiert ein orientierter Kantenzug in \(D\) sodass \(A(Z) = A(D)\).
Defintion 7.16 (Eulersche Digraph)
Sei \(D\) nicht triviale zusammengehende Digraph. \(D\) is eulersch: \(\eq\) \(d_D^+(v)=d_D^-(v)\) fur alle \(v \in V(D)\) wobei \[d_{D}^{+}(v):= |\{(v,w) | v, w \in A\}|\] \[d_{D}^{-}(v):= |\{(w, v) | v, w \in A\}|\]
Satz 7.18
Ein nicht-triviale zusammenhängende Digraph is eulersch \(\eq\) man kann die in bogen disjunkte orientierte Kreise zerlegen.
Satz 7.19
Sei \(D\) nicht triviale zusammengehende Digraph. \(D\) ist semi-eulersch \(\eq\) existiersn \(u,v \in V(D)\) sodass \[d_{D}^{+}(u)=d_{D}^{-}(u)+1 \text{ und } d_{D}^{+}(w \in V(D) \setminus \{u, v\})=d_{D}^{-}(w).\]
