Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 23/latex
\setcounter{section}{23}
\zwischenueberschrift{Eulersche Kantenzüge}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Waeller25.jpg} }
\end{center}
\bildtext {Vorli stellt sich unter einem Graphen eine Ansammlung von Leckerlis vor, die durch lange Würste miteinander verbunden sind.} }
\bildlizenz { Waeller25.jpg } {} {Odatrulle} {Commons} {CC-by-sa 4.0} {}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {7 bridges.svg} }
\end{center}
\bildtext {Euler möchte bei seinem täglichen Spaziergang über jede Brücke genau einmal gehen. Man spricht vom \stichwort {Königsberger Brückenproblem} {.}} }
\bildlizenz { 7 bridges.svg } {} {Chris-Martin} {Commons} {CC-by-sa 3.0} {}
\inputdefinition
{}
{
Es sei
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {Graph}{}{.}
Ein
\definitionsverweis {Kantenzug}{}{}
\mathl{e_1 , \ldots , e_m}{} heißt
\definitionswort {eulersch}{,}
wenn in ihm jede Kante aus $E$ genau einmal vorkommt.
}
Man spricht auch kurz von einem \stichwort {Eulerzug} {.} Bei einem eulerschen Kantenzug wird jede Kante genau einmal durchlaufen. Es kann dabei Knoten geben, die dabei mehrfach oder auch \zusatzklammer {isolierte Punkte} {} {} gar nicht berührt werden. Unter einem geschlossenen eulerschen Kantenzug versteht man einen eulerschen Kantenzug, bei dem die Anfangskante mit der Endkante inzident ist. Nicht geschlossene eulersche Kantenzüge nennt man auch offene eulersche Kantenzüge. Das ursprüngliche Brückenproblem bezieht sich auf einen Multigraphen, da die linke Insel doppelt mit beiden Flussseiten verbunden ist. Indem man aber auf diesen Kanten jeweils einen Hilfsknoten einführt, gelangt man zu einem äquivalenten Problem über einen einfachen Graphen.
\inputdefinition
{}
{
Ein \definitionsverweis {Graph}{}{} $G$ heißt \definitionswort {eulersch}{,} wenn in ihm ein \definitionsverweis {geschlossener Eulerzug}{}{} existiert.
}
\inputdefinition
{}
{
Zwei
\definitionsverweis {Untergraphen}{}{}
\mavergleichskette
{\vergleichskette
{H_1
}
{ = }{ (V_1,E_1)
}
{ \subseteq }{G
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{H_2
}
{ = }{ (V_2,E_2)
}
{ \subseteq }{G
}
{ }{
}
{ }{
}
}
{}{}{}
in einem
\definitionsverweis {Graphen}{}{}
\mavergleichskette
{\vergleichskette
{G
}
{ = }{ (V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißen
\definitionswort {kantendisjunkt}{,}
wenn
\mavergleichskette
{\vergleichskette
{E_1 \cap E_2
}
{ = }{ \emptyset
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist.
}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Hierholzer(1).svg} }
\end{center}
\bildtext {} }
\bildlizenz { Hierholzer(1).svg } {} {Tidoni} {Commons} {CC-by-sa 4.0} {}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Hierholzer(2).svg} }
\end{center}
\bildtext {} }
\bildlizenz { Hierholzer(2).svg } {} {Tidoni} {Commons} {CC-by-sa 4.0} {}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Hierholzer(3).svg} }
\end{center}
\bildtext {} }
\bildlizenz { Hierholzer(3).svg } {} {Tidoni} {Commons} {CC-by-sa 4.0} {}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Hierholzer(4).svg} }
\end{center}
\bildtext {} }
\bildlizenz { Hierholzer(4).svg } {} {Tidoni} {Commons} {CC-by-sa 4.0} {}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Hierholzer(5).svg} }
\end{center}
\bildtext {} }
\bildlizenz { Hierholzer(5).svg } {} {Tidoni} {Commons} {CC-by-sa 4.0} {}
\inputfaktbeweis
{Zusammenhängender Graph/Eulersch/Gerader Grad/Kantendisjunkte Kreise/Fakt}
{Satz}
{}
{
\faktsituation {Für einen
\definitionsverweis {zusammenhängenden Graphen}{}{}
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}}
\faktuebergang {sind folgende Aussagen äquivalent.}
\faktfolgerung {\aufzaehlungdrei{$G$ ist
\definitionsverweis {eulersch}{}{.}
}{Jeder Knotenpunkt von $G$ hat einen geraden
\definitionsverweis {Grad}{}{.}
}{$G$ ist die Vereinigung von
\definitionsverweis {kantendisjunkten}{}{}
\definitionsverweis {Kreisen}{}{}
\zusatzklammer {wobei ein einzelner Punkt hier als Kreis gelte} {} {.}
}}
\faktzusatz {}
\faktzusatz {}
}
{
Von (1) nach (2) ist klar, da bei einen geschlossenen Eulerzug jeder Knotenpunkt genau so oft besucht wie verlassen wird.
Von (2) nach (3). Wir führen Induktion über die Anzahl der Kanten. Da der Graph zusammenhängend ist, handelt es sich um einen isolierten Punkt oder aber jeder Knoten besitzt einen Grad von zumindest $2$. Deshalb muss es in $G$ einen
\definitionsverweis {Kreis}{}{}
$K$ geben. Man kann ja inn einem beliebigen Punkt starten und von diesem Punkt ausgehend nach und nach einen Kantenzug konstruieren. Wenn der Kantenzug in einen Punkt hineingeht, so kann man den Kantenzug fortsetzen, da zumindest zwei Kanten in dem Punkt zusammenlaufen. Wenn erstmal ein schon erreichter Punkt erneut auftaucht, ist der Kreis fertig, die \anfuehrung{Vorperiode}{} kann man außer Acht lassen. Es seien $F$ die Kanten des Kreises und wir betrachten den neuen Graphen
\mavergleichskette
{\vergleichskette
{G'
}
{ = }{ (V, E \setminus F)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Wenn ein Punkt aus $V$ zu einer Kante aus $F$ inzident ist, so reduziert sich der Grad in diesem Knoten um $2$, da ja jeder Punkt in einem Kreis inzident zu zwei Kanten ist. Wenn ein Punkt im Kreis nicht aufgerufen wird, so ändert sich der Grad nicht. In jedem Fall besitzt in $G'$ jeder Punkt wieder einen geraden Grad. Der neue Graph muss nicht mehr zusammenhängend sein, allerdings erfüllen die einzelnen
\definitionsverweis {Zusammenhangskomponenten}{}{}
von $G'$ wieder die Voraussetzung, dass sämtliche Grade gerade sind. Nach Induktionsvoraussetzung besitzen die Zusammenhangskomponenten jeweils eine Darstellung als Vereinigung mit kantendisjunkten Kreisen. Also besitzt $G'$ eine Darstellung als Vereinigung mit kantendisjunkten Kreisen und zusammen mit $K$ ergibt sich eine Darstellung von $G$ als Vereinigung mit kantendisjunkten Kreisen.
Von (3) nach (1). Es seien
\mavergleichskette
{\vergleichskette
{K_j
}
{ = }{ (V_j,E_j)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
\mavergleichskette
{\vergleichskette
{j
}
{ \in }{J
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
die beteiligten kantendisjunkten Kreise, die $G$ überdecken. Wir konstruieren induktiv Kantenzüge, die für zunehmend größere Vereinigungen dieser Kreise einen Eulerzug darstellen. Einen einzelnen Kreis kann man unmittelbar als einen Eulerzug für diesen Kreis auffassen. Es sei nun vorausgesetzt, dass man $s$ Kreise, die wir als $K_1 , \ldots , K_s$ durchnummerieren, derart gefunden hat, dass es einen Eulerzug für
\mavergleichskettedisp
{\vergleichskette
{G_s
}
{ =} { \bigcup_{j = 1}^s K_j
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gibt. Bei
\mavergleichskette
{\vergleichskette
{s
}
{ < }{r
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt es aufgrund des Zusammenhangs des Graphen einen weiteren Kreis, den wir $K_{s+1}$ nennen, der einen gemeinsamen Knotenpunkt mit $G_s$ hat, sagen wir $u$. Dann erhält man aus dem Eulerzug für $G_s$ einen Eulerzug für
\mavergleichskette
{\vergleichskette
{ G_{s+1}
}
{ = }{G_{s} \cup K_{s+1}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
indem man, wenn der Eulerzug den Punkt $u$ erreicht, in den Kreis $K_{s+1}$ abbiegt, diesen einmal durchläuft und danach an der Stelle $u$ den alten Eulerzug fortsetzt. Da $K_{s+1}$ kantendisjunkt zu $G_s$ ist, entsteht dabei wieder ein Eulerzug.
\inputbemerkung
{}
{
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Butterfly graph.svg} }
\end{center}
\bildtext {} }
\bildlizenz { Butterfly graph.svg } {} {KoKo90} {Commons} {CC-by-sa 2.5} {}
Das im Beweis zu Satz 23.4 beschriebende Verfahren, um, falls die Gradbedingung erfüllt ist, einen geschlossenen eulerschen Kantenzug über die kantendisjunkten Kreise zu finden, ist grundsätzlich konstruktiv. Man nennt das Verfahren den \stichwort {Algorithmus von Hierholzer} {.} Bei einem Knotenpunkt vom Grad $2$ ist der Kantendurchlauf für einen Eulerzug bis auf die Orientierung vorgegeben. Man kann aber im Allgemeinen bei einem Knotenpunkt mit einem Grad $>2$ nicht frei vorgeben, in welcher Reihenfolge die in dem Punkt zusammenlaufenden Kanten hintereinander gelegt werden. Im \stichwort {Schmetterlingsgraphen} {} können in einem Eulerzug die beiden rechten Kanten, die am Kreuzungspunkt anliegen, nicht direkt aufeinander folgen, da sonst der rechten Kreis geschlossen wird.
}
\inputfaktbeweis
{Zusammenhängender Graph/Eulersch/Gerader Grad/Kantenfolge/Fakt}
{Korollar}
{}
{
\faktsituation {Es sei
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {zusammenhängender Graph}{}{,}}
\faktvoraussetzung {für den der
\definitionsverweis {Grad}{}{}
eines jeden Knotenpunktes gerade ist. Es sei $u$ ein Punkt und es seien
\mathl{v,w}{} adjazente Punkte zu $u$.}
\faktfolgerung {Dann ist die Kantenfolge
\mathl{\{v,u\}, \{u,w\}}{} genau dann Teil eines
\definitionsverweis {geschlossenen Eulerzuges}{}{}
durch $G$, wenn der Graph $G'$, der aus $G$ entsteht, indem man einen neuen Punkt $u'$ einführt und die beiden Kanten
\mathl{\{v,u\}, \{u,w\}}{} durch
\mathl{\{v,u'\}, \{u',w\}}{} ersetzt, zusammenhängend ist.}
\faktzusatz {}
\faktzusatz {}
}
{
Der konstruierte \anfuehrung{Überbrückungsgraph}{} besitzt ebenfalls die Eigenschaft, dass jeder Knotenpunkt einen geraden Grad besitzt. Wenn er zusammenhängend ist, so gibt es nach Satz 23.4 einen geschlossenen Eulerzug durch $G'$. Da an $u'$ nur die beiden Kanten \mathkor {} {\{v,u'\}} {und} {\{u',w\}} {} anliegen, werden diese hintereinander durchlaufen. Wenn man die Konstruktion rückgängig macht \zusatzklammer {also \mathkor {} {u} {und} {u'} {} identifiziert} {} {,} so erhält man einen Eulerzug von $G$, bei dem die beiden Kanten hintereinander vorkommen. Wenn es umgekehrt einen Eulerzug von $G$ gibt, der die beiden Kanten hintereinander durchläuft, so kann man daraus direkt einen Eulerzug von $G'$ konstruieren, was zeigt, dass $G'$ zusammenhängend ist.
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Chuan2.JPG} }
\end{center}
\bildtext {} }
\bildlizenz { Chuan2.JPG } {} {A52ljgh89} {Commons} {gemeinfrei} {}
\inputfaktbeweis
{Zusammenhängender Graph/Offener Eulerzug/Charakterisierung mit Grad/Fakt}
{Satz}
{}
{
\faktsituation {In einem
\definitionsverweis {zusammenhängenden Graphen}{}{}
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}}
\faktfolgerung {gibt es genau dann einen nichtgeschlossenen
\definitionsverweis {Eulerzug}{}{,}
wenn es genau zwei Knotenpunkte mit ungeradem
\definitionsverweis {Grad}{}{}
gibt.}
\faktzusatz {}
\faktzusatz {}
}
{
Ein nicht geschlossener Eulerzug besitzt einen Anfangspunkt $u$ und einen davon verschiedenen Endpunkt $v$. Wenn man den Eulerzug durchläuft und dabei für jeden Punkt die Grade zählt, so erhöht sich bei jedem Durchlauf durch einen Punkt \zusatzklammer {egal ob $u$ oder $v$ oder sonst ein Punkt} {} {} der Grad um $2$. Am Anfang und am Ende kommt für $u$ bzw. $v$ nochmal $1$ dazu.
Es seien
\mathkor {} {u} {und} {v} {}
die beiden Punkte mit ungeradem Grad. Wenn
\mathl{\{u,v\}}{} nicht zu $E$ gehört, so nimmt man diese Kante hinzu und erhält einen neuen Graphen $G'$, bei dem nun alle Knotenpunkte einen geraden Grad besitzen. Nach
Satz 23.4
gibt es in $G'$ einen geschlossenen Eulerzug. Dieser ist ohne die Kante
\mathl{\{u,v\}}{} ein nichtgeschlossener Eulerzug von $G$. Wenn hingegen
\mathl{\{u,v\}}{} zu $E$ gehört, so nimmt man einen neuen Punkt $w$ zur Knotenmenge und die Kanten
\mathkor {} {\{u,w\}} {und} {\{v,w\}} {}
zur Kantenmenge hinzu. Im neuen Graphen $G'$ besitzt wieder jeder Knoten einen geraden Grad. Ein geschlossener Eulerzug von $G'$ enthält den Kantenzug
\mathl{\{u,w\}, \{w,v\}}{.} Da $w$ in sonst keiner Kante auftritt, erhält man, indem man dieses Teilstück und $w$ weglässt, einen nichtgeschlossenen Eulerzug von $G$.