Euler-Kreise und -Wege

Wiki-Quelltext dieser Seite.

Patrick Schmidt (Euler Wege, Algorithmus von Hierholzer,Fleur,Postprobem Definition)
Kevin Richter (Einführung, Euler Kreise, Postbotenproblem(Algorithmus))
= <b><font color="black">Einführung</font color></b>=
== <b><font color="black">Leonhard Euler </font color></b>==
Allgemeines über Euler:

*geboren am 15. April 1707 in Basel
*gestorben  am 18. September 1783 in Sankt Petersburg
*war ein Physiker und Mathematiker
*befasste sich mit vielen Themen der Analysis, Zahlentheorie
*mitbegründer der Graphentheorie
*beschäftigte sich mit dem Königsberger Brückenproblem:
**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.

= <b><font color="black">Euler-Graphen </font color></b>=
== <b><font color="black">Definition </font color></b>==
Was sind Euler-Graphen? <br><br>
* Laut dem Satz von Euler-Hierholzer ist ein Graph genau dann eulersch, wenn dieser zusammenhängend und der Grad der Knoten gerade ist.
* Dieser Satz lässt sich um den Begriff der Eulerwege erweitern.
* 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 Wege </font color></b>==
* Ein Euler Weg 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 bzw. die Identität wird nicht verlangt.
* Darüberhinaus enthält ein zusammenhängender, ungerichteter Graph genau dann einen Eulerweg, wenn der Gaph genau zwei Knoten mit ungeraden Grad besitzt.
* In diesem Fall markieren diese beiden Knoten den Anfangs- bzw. Endeknoten des Graphen.
* Insofern ein Graph nur einen Eulerweg besitzt, bezeichnet man ihn als Semieulersch.

=== <b><font color="black">Haus vom Nikolaus</font color></b>===
Ein altes, aber heute noch präsentes <u>Kinderrätzel</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?
* Stichwort: Start-,Endknoten; Anzahl Möglichkeiten; Erfolgsrate
* Dieser Graph enthält also einen Eulerweg, wobei sich besonders hier die Bedeutung des Knotengrades zeigt.
<popup name="Erklärung">
# Warum funktioniert das?
# Wie viele Möglichkeiten gibt es überhaupt das Haus zu zeichen?

----
Zu 1.:
* Um dies zu klären muss man zunächst noch einmal den Begriff Knotengrad erläutern.
* Der Grad d<sub>G</sub>(v) eines Knotens ist die Anzahl der Kanten die mit einem Knoten verbunden sind.
* Nun zur Erklärung:
* 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
|}
* Ein gerader Knotengrad bedeutet immer, dass dieser Knoten so oft betreten werden kann wie er verlassen wird und umgekehrt.
* Bei einem ungeraden Knotengrad kann der Knoten einmal mehr verlassen oder betreten werden.
* D.h. in diesem Beispiel gibt je zwei Durchlaufstationen in 3 und 4, sowie eine in 5.
* In den Knoten 1 und 2 allerdings existierten je zwei Durchlaufstationen und zusätzlich eine End- bzw. Startstelle. 
* Unter diesen Umständen muss also, bei diesem Eulerweg, 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>

== <b><font color="black">Euler Kreise </font color></b>==
=== <b><font color="black">Beispiel</font color></b>===
Euler-Kreise sind geschlossende Euler-Züge, jedoch haben diese einen gemeinsamen Start bzw Endpunkt.

= <b><font color="black">Algorithmen</font color></b>=
==<b><font color="black">Lösbarkeit</font color></b>==
* Das Problem herauzufinden ob ein Graph eulersch ist, lässt sich algorithmsch leicht bestimmen.
* Da laut Eigenschaften ein Graph genau dann eulersch ist,wenn er zusammenhängend und jeder Knoten einen geraden Grad besitzt.
* Mit dieser Information ist in linearer Zeit mit eben diesem Aufwand möglich, mittels Tiefensuche das Problem zu lösen.
* Es exitiere aber noch weitere Methoden um Euler-Graphen zu finden.
== <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)

# Wähle einen beliebigen Knoten als aktuellen Knoten.
# Wähle nun unter den mit dem aktuellen Knoten inzidenten Kanten eine beliebige Kante aus.<br>Dabei sind zuerst Kanten zu wählen, die im unmarkierten Graphen keine Brückenkanten sind.
# Markiere die gewählte Kante und entferne sie.
# Wähle den anderen Knoten der gewählten Kante als neuen aktuellen Knoten.
# Wenn noch unmarkierte Kanten existieren, dann gehe zu Schritt 2.

Output: Eulerkreis oder Eulerweg

* Mittels Tiefensuche kann in einer Laufzeit von O(|E|) 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. 
* Input: Graph G(V,E)
[[Bild:hierholzer.png]]
* Output: Eulerkreis
** Wenn der Output ein Eulerweg sein soll muss man w so wählen, dass dieser ein ungeraden Grad hat.
* Er ist wesentlich effizienter,da er ein Eulerkreis in linearzeit,d.h mit einer Laufzeit von O(|E|) auffinden kann.
= <b><font color="black">Das Postbotenproblem</font color></b>=
Allgemein: Das Postbotenproblem beschäftigt sich damit alle Kannten im Graphen <em>genau ein mal</em> entlang zu laufen.
== <b><font color="black">Definition</font color></b>==
== <b><font color="black">Algorithmus</font color></b>==
= <b><font color="black">Anwendungsbeispiele</font color></b>=
= <b><font color="black">Quellen</font color></b>=
* https://de.wikipedia.org/wiki/Eulerkreisproblem
* Wessler_Graphen-und-Netzwerktheorie, André Krischke, Helge Röpcke
* Algorithmen und Komplexität, Christian Wagenknecht