Euler-Kreise und -Wege
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
Patrick Schmidt und Kevin Richter
= <b><font color="black">Einführung</font color></b>=
== <b><font color="black">Leonhard Euler </font color></b>==
* geboren am 15. April 1707 in Basel
* gestorben am 18. September 1783 in Sankt Petersburg
* war einer der bedeutendsten Mathematiker und Physiker
* befasste sich mit vielen Themen der Analysis, Zahlentheorie
* löste das Königsberger Brückenproblem
* Mitbegründer der Graphentheorie
== <b><font color="black">Motivation </font color></b>==
* Im Bereich der eulerschen Graphen beschäftigt man sich im Vergleich zu anderen Gebieten der Graphentheorie mit ganzen Rundreise durch Graphen.
* Dies ist ein völlig neuer Ansatz und enthält ebenso neue Problemtypen.
<br>
= <b><font color="black">Euler-Graphen </font color></b>=
== <b><font color="black">Definition </font color></b>==
Was sind Euler-Graphen? <br><br>
* $G=(V,E)$ ist genau dann eulersch, wenn ein Weg bzw. Kreis $P$ existiert, für den gilt $G(|E|)=P(|E|)$
* Das bedeutet eulersche Graphen sind Graphen bei denen alle Kanten genau einmal durchlaufen werden müssen.<br>
<br>Ist folgender Graph eulersch?
[[Bild:eulergraph.PNG]]
<popup name="Antwort">
[[Bild:eulergraph_lsg.PNG]]<br>
Antwort: Der Graph ist nicht eulersch, da nicht alle Kanten des Graphen in einem Zug miteinander verbunden werden können.
</popup>
== <b><font color="black">Euler Kreise </font color></b>==
* Ein Eulerkreis oder auch geschlossener Eulerzug bzw. Eulertour ist ein Zyklus in einem Graphen, der alle Kanten des Graphen enthält.
* Desweiteren haben sie einen gemeinsamen Start bzw. Endpunkt.
* enthält ein Graph einen Eulerkreis, so wird dieser als eulersch bezeichnet.
* Das Problem das sich mit dem Auffinden dieser beschäftigt heißt Eulerkreisproblem.
[[Bild:Kerich_VL_bsp_eulerkreis2.png]]
[[Bild:Kerich_Gerichteter_graph_vorlesung_Eulerkreis.png]]
[[Bild:Kerich_VL_bsp_eulerkreis.png]]
<popup name=Vorraussetzung>
$G=(V,E)$
Für ungerichtete Graphen gilt:
* $G$ ist genau dann eulersch, wenn
** $G$ zusammenhängend und der Knotengrad $d$<sub>$G$</sub>$(|V|)$ gerade ist. <b>oder</b>
** $G$ zusammenhängend und $G(|E|)$ die Vereinigung aller Kanten von paarweise disjunkten Kreise ist.
Für gerichtete Graphen gilt:
* $G$ ist genau dann eulersch, wenn
** $G$ stark zusammenhängend und der Eingansgrad $d$<sup>$+$</sup><sub>$G$</sub>($v$) = Ausgangsgrad $d$<sup>$-$</sup><sub>$G$</sub>($v$) für $|V|$ ist. <b>oder</b>
** $G$ stark zusammenhängend und $G(|E|)$ die Vereinigung aller Kanten von paarweise disjunkten gerichteten Kreise ist.
Knotengrad:
* Der Grad $d$<sub>$G$</sub>($v$) eines Knotens $v$ ist die Anzahl der mit $v$ inzidenten Kanten.
* Ein gerader Knotengrad bedeutet immer, dass dieser Knoten so oft betreten wird, wie er verlassen wird und umgekehrt.
</popup>
<br>
== <b><font color="black">Euler Wege </font color></b>==
* Ein Eulerweg oder auch offener Eulerzug ist in der Graphentheorie die Bezeichnung für eine Kantenfolge eines Graphen, bei der jede Kante genau einmal durchlaufen wird.
* Dabei sind der Start- und Endknoten nicht identisch.
* Insofern ein Graph nur einen Eulerweg besitzt, bezeichnet man ihn als semi-eulersch.
[[Bild:euleweg_1.png]]
[[Bild:eulerweg_2.png]]
<popup name=Vorraussetzung>
$G=(V,E)$
Für ungerichtete Graphen gilt:
* $G$ ist genau dann semi-eulersch,wenn
** $G$ zusammenhängend ist und es einen Knoten $a \in V$ und einen Knoten $b \in V$ gibt, wobei $d$<sub>$G$</sub>$(a)$ und $d$<sub>$G$</sub>$(b)$ ungerade ist.
Für gerichtete Graphen gilt:
* $G$ ist genau dann semi-eulersch,wenn
** $G$ zusammenhängend ist und es einen Knoten $a \in V$ und ein Knoten $b \in V$ gibt, wobei $a$ einen Eingangsgrad ($d$<sup>$+$</sup><sub>$G$</sub>) mehr hat und $b$ einen Ausgangsgrad($d$<sup>$-$</sup><sub>$G$</sub>) mehr hat.
Knotengrad $d$<sub>$G$</sub>$(v)$:
* Bei einem ungeraden Knotengrad kann der Knoten einmal mehr verlassen oder betreten werden.
</popup>
<br>
<popup>
[[Bild:eulerweg_1_g.png]]
[[Bild:eulerweg_2_g.png]]
</popup>
=== <b><font color="black">Das Haus des Nikolaus</font color></b>===
Ein altes, aber heute noch präsentes <u>Kinderrätsel</u>: "Das-ist-das-Haus-des-Ni-ko-laus"
*Gegeben sei ein Graph $G(V,E)$ mit $V$=5 und $E$=8:
[[Bild:nikolaus_haus.gif]] [[Bild:nikolaus_haus.png]]
* Ziel hierbei ist es, alle Kanten des Graphen miteinander zu verbinden ohne Abzusetzen.
* Versuchen Sie es: Zeichen Sie diesen Graphen nach der vorgegebenen Zielstellung. Was fällt ihnen auf?
<br>
<popup name="Erklärung">
# Warum funktioniert das?
# Wie viele Möglichkeiten gibt es überhaupt das Haus zu zeichen?
----
Zu 1.:
* Besonders hier zeigt sich die Bedeutung des Knotengrades.
* Man betrachtet alle Knoten des Graphen mit ihrem Kotengrad, folgende Übersicht entsteht:
{| class="wikitable"
|-
| '''Knoten''' || 1 || 2 || 3 || 4 || 5
|-
| '''d<sub>G</sub>(v)''' || 3 || 3 || 4 || 4 || 2
|}
* In diesem Beispiel gibt je zwei Durchlaufstationen in 3 und 4, sowie eine in 5.
* Durchlaufstation = betreten und anschließendes verlassen des Knotens
* In den Knoten 1 und 2 allerdings existierten je zwei Durchlaufstationen und zusätzlich eine End- bzw. Startstelle.
* Unter diesen Umständen muss also der Graph in 1 oder 2 beginnen bzw. enden.
Zu 2.:
* Bei dem Haus vom Nikolaus gibt es insgesamt 44 Möglichkeiten dieses zu zeichnen, vorrausgestzt man startet immer im Knoten 1 und endet in 2.
* Andernfalls gibt es 88 Möglichkeiten aufgrund der Symmetrie.
<popup name="Möglichkeiten">
[[Bild:mgl_nikolaus_haus.png]]
</popup>
<br>
= <b><font color="black">Algorithmen</font color></b>=
== <b><font color="black">Algorithmus von Fleury</font color></b>==
* Beim Algorithmus von Fleury sind Brückenkanten von besonderer Bedeutung.
* Dies sind Kanten, ohne die der Graph in zwei Komponenten zerfallen würde. <br>
* Input: Graph $G(V,E)$
* Output: Eulerkreis oder Eulerweg<br>
1. Wähle einen beliebigen Knoten $v \in V$ als aktuellen Knoten.
2. Wähle nun unter den mit dem aktuellen Knoten $v$ inzidenten Kanten eine beliebige Kante $e \in E$ aus.<br> Dabei ist $e$ so zu wählen, dass diese im unmarkierten Graphen keine Brückenkante ist.
3. Markiere $e$ und entferne sie.
4. Wähle den anderen Knoten $w \in V$ von $e$ als neuen aktuellen Knoten.
5. Wenn noch unmarkierte Kanten existieren, dann gehe zu Schritt 2.
* Mit einer Laufzeit von $O(|E|)$ kann festgestellt werden, ob eine Kante eine Brückenkante ist.
* Für das Entfernen der Kanten werden $|E|$ Iterationen benötigt.
* Somit ergibt sich eine Gesamtlaufzeit von $O(|E$<sup>2</sup>$|)$.
== <b><font color="black">Algorithmus von Hierholzer</font color></b>==
* Dieser Algorithmus macht sich die Eigenschaften zu nutze, dass eulersche Graphen in paarweise Kantendisjunkte Kreise zerlegt werden können.
* Der Algorithmus funktioniert demnach wie folgt:
* Man wählt einen beliebigen Knoten aus dem Graphen und bildet über eine Folge von Kanten einen Kreis.
* Danach wählt man einen Knoten aus den bereits gebildeten Kreis/en von dem aus es noch unbesuchte Kanten gibt und bildet von diesem Knoten ausgehend erneut einen Zyklus.
** Ist der Graph semi-eulersch, enthält der Graph zudem zusätzlich einen Weg zwischen den beiden Knoten mit ungeraden Grad.
* Dies wiederholt man solange bis der Graph mithilfe der Subkreise zu einem Eulerkreis oder ergänzt um einen Weg zu einen Eulerweg zusammengesetzt werden kann.
<br>
* Input: Graph $G(V,E)$
* Output: Eulerkreis oder Eulerweg
1. setze $C: = 0 $; wähle $ v \in V$ beliebig.
2. wähle weitere Knoten $v$<sub>i</sub> $\in V$, sodass $(v,...,v$<sub>i</sub>) ein Weg in $G$ ist, und zwar so lange bis ein Kreis $C'$ entsteht.<br> Füge $C'$ bei $v$ an $C$ an.
3. Falls $C$ ein Eulerkreis ist $STOPP$ und Ausgabe von $C$.
4. Ansonsten wähle einen in $C$ enthaltenen Knoten $w \in V$, der zu einer nicht in $C$ enthaltenen Kante gehört<br> und gehe zum 2.Schritt
* Er ist wesentlich effizienter, da er ein Eulerkreis oder Eulerweg in linearzeit,d.h mit einer Laufzeit von $O(|E|)$ auffinden kann.
* Das liegt daran, dass der Algorithmus nur die Kanten entlang geht und Zyklen bildet.
* Damit ist der Aufwand von der Kantenzahl des Graphen abhängig.
https://www-m9.ma.tum.de/graph-algorithms/hierholzer/index_de.html
<br>
= <b><font color="black">Das Postbotenproblem</font color></b>=
== <b><font color="black">Definition</font color></b>==
* Benannt nach dem chinesischen Mathematiker Mei-Ko Kwan der sich ersmals 1962 damit beschäftigte.
* Ein Postbote soll die Briefe (auf beiden Seiten der Straße gleichzeitig) in einem Straßennetzwerk (Stadt) zustellen und anschließend zum Postamt zurückkehren.
* Dies soll in kürzester Zeit geschehen.
== <b><font color="black">Modellierung</font color></b>==
* Das Problem kann mithilfe eines Graphen dargestellt werden, wobei die Kreuzungen als Knoten, die Straßen als Kanten, sowie deren Länge(Zeit) als Gewicht betrachtet werden.
* Um alle Straßen in kürzester Zeit überqueren und wieder beim Ausgangspunkt landen zu können, muss nach einem möglichst kurzen Eulerkreis gesucht werden.
== <b><font color="black">Lösung</font color></b>==
* Existieren keine Knoten mit ungeraden Grad ist die Lösung der jeweilige Eulerkreis.<br>
<b>Problem:</b>
* Was tun wen der Graph nicht eulersch ist?
<b>Vorüberlegung:</b>
* ein Graph $G(V,E)$ ist genau dann nicht eulersch, wenn $d$<sub>$G$</sub>$(v)$ ist ungerade für mindestens ein Knoten.
* Die Anzahl der Knoten mit ungeraden Grad in Graphen ist immer gerade.
<b>Lösung:</b>
* es müssen Kanten zwischen diesen Knoten hinzugefügt werden, sodass der Graph wieder eulersch wird.
* Das bedeutet für den Postman einfach ein doppeltes Ablaufen der Straße.
<br>
<popup name=Festlegung>
* nur nicht-negativ bewertete Graphen erlaubt
* Fallunterscheidung zwischen gerichteten, ungerichteten Graphen bzw. Mischfform
** Je nach Bezugnahme auf Praxis
</popup><br>
== <b><font color="black">Algorithmus</font color></b>==
Für ungerichtete Graphen gilt:<br>
1. Fasse die Knoten ungeraden Grades zu einer Teilmenge $V'$ von $V$ zusammen und definiere $G'$ als den<br> vollständigen Graphen auf den Knoten $V'$
2. Definiere eine Bewertung auf $G'$ mithilfe kürzester Wege (z.B. Algorithmus von Dijkstra)
3. Bestimme ein bezüglich dieser Bewertung Minimales Matching $M$ auf $G'$ und füge zu $G$ die Kanten des Matchings hinzu
4. Bestimme den Eulerkreis von $G$
<br>
Für gerichtete Graphen gilt:<br>
1. Fasse die Knoten von $V$ mit $d$<sup>$-$</sup><sub>$G$</sub>$(v)$ $\lt$ $d$<sup>$+$</sup><sub>$G$</sub>$(v)$ zu einer Menge $V$<sup>$+$</sup> und die Knoten von<br> $V$ mit $d$<sup>$-$</sup><sub>$G$</sub>$(v)$ $\gt$ $d$<sup>$+$</sup><sub>$G$</sub>$(v)$ zu einer Menge $V$<sup>$-$</sup> zusammen.
2. Definiere $G'$ als den vollständigen bipartiten gerichteten Graphen zwischen $V$<sup>$-$</sup> und $V$<sup>$+$</sup>.
3. Definiere auf diesem Hilfsgraphen eine Bewertung mithilfe kürzester Wege
4. Wähle eine bezüglich dieser Bewertung minimale Teilmenge von Pfeilen aus dem Hilfsgraphen aus und füge sie zu $G$ hinzu
5. Bestimme den Eulerkreis von $G$
<br>
= <b><font color="black">Anwendungsgebiete</font color></b>=
== <b><font color="black">Königsberger Brückenproblem</font color></b>==
*Das Problem bestand darin, zu klären, ob es einen Weg gibt, bei dem man alle sieben Brücken genau einmal überquert, und wenn ja, ob auch ein Rundweg möglich ist, bei dem man wieder zum Ausgangspunkt gelangt.
[[Bild:brückenproblem.png]] <b>nach Postbotenproblematik</b>
[[Bild:brückenproblem_pb.png]]
* Laut Eulers Definition des Euler-Graphen kann dieser Graph nicht eulersch sein.
* Bei näheren Hinschauen fällt auf, dass er auch nicht semi-eulersch ist, da die Anzahl der ungeraden Knoten auf 2 limitiert sein muss.
* Somit hat Euler das Brückenproblem dahinggehend gelöst, dass er bewiesen hat, dass es kein Eulergraph zu diesem Problem gibt.
* Daraus folgt, dass es in diesem Zusammenhang nicht möglich ist alle Brücken <b>einmalig</b> zu überqueren.
* Das Postbotenproblem liefert hier aber eine Lösung bei der man zumindest alle Brücken überqueren kann und zum Anfangspunkt zurückehrt.
* Jedoch ist dies in Hinblick auf die ursrprüngliche Fragestellung nur ein Trost.
== <b><font color="black">Weitere Gebiete</font color></b>==
* weitere Anwendungsgebiete in der Praxis sind besonders in Bezug auf das Postbotenproblem schnell gefunden
* Im Großen und Ganzen überall da wo es darum geht alle Wege zwischen Punkten zu passieren und gegebenenfalls wieder an der Startposition zu landen
* Beispiele hierfür sind:
* Postzusteller, wie bereits geklärt
* Müllzufuhr
* Museentouren
* im Tourismus
* Zustellungsservices
* Zulieferer
* persönliche Einkäufe
= <b><font color="black">Quellen</font color></b>=
* https://de.wikipedia.org/wiki/Eulerkreisproblem
* https://www-m9.ma.tum.de/graph-algorithms/hierholzer/index_de.html
* http://mediathek.mt.haw-hamburg.de/video/M2-2014-06-20-04-Der-Algorithmus-von-Fleury/72ef1f761005bca600f4766b005d84ed
* http://mediathek.mt.haw-hamburg.de/video/M2-2014-06-20-05-Der-Algorithmus-von-Hierholzer/b2046b3183af22bb5f13fe55f1f9629b
* https://de.wikipedia.org/wiki/Brieftr%C3%A4gerproblem
* https://www-m9.ma.tum.de/graph-algorithms/directed-chinese-postman/index_de.html
* Wessler_Graphen-und-Netzwerktheorie, André Krischke, Helge Röpcke