Nicht jeder Graph lässt sich in einem Zug zeichnen. Die Graphen, die sich zeichnen lassen haben sogenannte Eulertouren und besitzen nebenbei auch noch bestimmte Eigenschaften. Möchte man erkennen wann eine Eulertour möglich ist oder möchte man solch eine Eulertour sogar finden, benötigt man ein Verfahren, das einem dabei hilft. Bevor wir uns jedoch an das Verfahren begeben, nennen wir zunächst noch ein paar Grundlagen, um die nötigen Vokabeln zu kennen, die für das Verfahren gebraucht werden.
Inhaltsverzeichnis
1 Einleitung
2 Grundlagen
2.1 Graphentheoretische Begriffe
2.2 Entscheidungsproblem
3 Algorithmus von Hierholzer
4 Beweis
4.1 Notwendige Bedingung
4.2 Lemma
4.3 Vollständige Induktion
5 Ausblick
5.1 Offener Eulerzug
5.2 Königsberger Brückenproblem
5.3 Hamiltonkreisproblem
6 Quellen
1 Einleitung
Nicht jeder Graph lässt sich in einem Zug zeichnen. Die Graphen, die sich zeichnen lassen haben sogenannte Eulertouren und besitzen nebenbei auch noch bestimmte Eigenschaften. Möchte man erkennen wann eine Eulertour möglich ist oder möchte man solch eine Eulertour sogar finden, benötigt man ein Verfahren, das einem dabei hilft. Bevor wir uns jedoch an das Verfahren begeben, nennen wir zunächst noch ein paar Grundlagen, um die nötigen Vokabeln zu kennen, die für das Verfahren gebraucht werden.
2 Grundlagen
Eine Eulertour ist in der Graphentheorie ein Zyklus, der alle Kanten ei- nes Graphen genau einmal enthält. Dann gibt es nach dem Satz von Euler- Hierholzer genau drei äquivalente Aussagen, um einen euerschen Graphen G zu charakterisieren:
1. G ist eulersch.
2. G ist zusammenhängend und alle Knoten haben geraden Grad.
3. G ist zusammenhängend und die Kantenmenge von G ist die Vereini- gung aller Kanten von paarweise disjunkten Kreisen.
Über die letzten beiden Aussagen wird man im Folgenden anhand der Beispiele des Hierholzer Algorithmus und dessen Beweis aufgeklärt.
2.1 Graphentheoretische Begriffe
Um die Beispiele für Eulertouren und den Beweis besser nachvollziehen zu können, folgen einige Begriffserklärungen.
Weg: Sei G = (V, E) ein ungerichteter Graph, so ist ein Weg W eine Folge von Knoten [illustration not visible in this excerpt] ∈ V mit W = [illustration not visible in this excerpt], deren aufeinanderfolgende Knoten durch Kanten des Graphen ei ∈ E verbunden sind.
Pfad: Ein Pfad ist ein Weg W = [illustration not visible in this excerpt], dessen Knoten in der Knotenfolge höchstens einmal auftreten. [illustration not visible in this excerpt] mit i, j ∈ {1, ..., n} und i = j.
Zyklus: Ein Zyklus ist ein Weg W = [illustration not visible in this excerpt] bei dem Start- und Endknoten in der Knotenfolge identisch sind. [illustration not visible in this excerpt].
Kreis: Ein Kreis ist ein Weg W = [illustration not visible in this excerpt] bei dem ausschließlich der Start- und Endknoten in der Knotenfolge identisch sind.
[illustration not visible in this excerpt] mit [illustration not visible in this excerpt] wobei i ∈ {1,...,n} \ {1,n}.
2.2 Entscheidungsproblem
Wenn ein Graph G gegeben ist, so stellt sich die Frage ob eine Eulertour in dem Graphen überhaupt möglich ist. Wir werden im Nachfolgenden zeigen, dass die hauptsächliche Bedingung davon abhängig ist, dass jeder Knoten in G einen geraden Grad haben muss. Die kann man jedoch leicht nutzen um die Frage leicht mittels Breitensuche oder Tiefensuche beantworten. Man untersucht einfach jeden Knoten in G auf geraden Grad. Das Entscheidungsproblem ist somit in linearer Zeit O(N ) lösbar.
Listing 1: DFS Entscheidungsproblem (Pseudocode)
illustration not visible in this excerpt
3 Algorithmus von Hierholzer
Was bis jetzt noch fehlt ist ein Verfahren einen Eulerkreis zu finden. Im Jah- re 1873 veröffentlichte Carl Hierholzer einen Algorithmus, der eine Eulertour in einem Graphen in linearzeit auffindet. Er basiert darauf den Graphen in paarweise kantendisjunkte Kreise zu zerlegen. Außerdem geht der Algorith- mus von einem ungerichteten zusammenhängenden Graphen aus, der das Entscheidungsproblem erfüllt. Sei G = (V, E) ein Graph mit den zuvor ge- nannten Eigenschaften, so kann man eine Eulertour wie folgt finden:
1. Sei v0 ∈ V ein beliebig gewählter Knoten aus G so konstruiere von v0 ausgehend einen Unterkreis K in G, der keine Kante aus G zweimal durchläuft.
2. Wenn K ein Eulerkreis ist, breche ab. Andernfalls:
3. Vernachlässige alle Kanten des Unterkreises K.
4. Sei v1 ∈ V der ersten Eckpunkt von K, dessen Grad größer 0 ist. So lasse einen weiteren Unterkreis K′ entstehen, der keine Kante der restlichen Kanten in G zweimal durchläuft.
5. Führe nun K und K′ zusammen, indem v1 durch K′ ersetzt wird.
6. Nenne den entstandenen Zyklus K und fahre mit Schritt 2 fort.
Listing 2: Algorithmus von Hierholzer (Pseudocode)
illustration not visible in this excerpt
4 Beweis
Wir beweisen nun eine notwendige Bedingung und ein Lemma, welche wir für den Induktionsbeweis des Hierholzer Algorithmus verwenden werden.
4.1 Notwendige Bedingung
Behauptung: Sei G ein Graph und G ist eulersch, so müssen alle Knoten von G geraden Grad haben.
Beweis: Seien u und v zwei verschiedene Knoten in einem Graphen G.
Angenommen u ist der Startknoten von dem aus die Eulertour beginnt und deg(u) ist ungerade. Das bedeutet, dass wenn wir alle seine Kan- ten benutzen, so verlassen wir am Ende den Startknoten u und können ihn nicht mehr erreichen. Die Eulertour endet dann jedoch nicht im Startknoten, was aber nach Definition gefordert ist. Somit muss deg(u) gerade sein, damit es beim Zeichnen der Eulertour möglich ist im Start- knoten zu enden, da alle Kanten von u benutzt werden sollen.
Angenommen v ist ein beliebiger Knoten, der nicht der Startknoten ist und deg(v) ist ungerade. Die Eulertour beginnt dann in einem Start- knoten u. Das bedeutet wiederum, dass wir in v enden, wenn wir alle seine Kanten benutzen, da es ungerade viele sind. Die Eulertour endet dann wieder nicht im Startknoten, was aber nach Definition gefordert ist. Jeder nicht Startknoten v muss somit einen geraden Grad haben, damit es beim Zeichnen der Eulertour möglich ist diesen Knoten v zu verlassen, um nicht dort, sondern im Startknoten zu enden. Die Annah- me, wenn G eulersch ist, dann dürften Knoten einen ungeraden Grad haben, wurde zum Widerspruch geführt, sodass unsere Behauptung zu Anfang stimmen muss.
4.2 Lemma
Behauptung: Sei G ein ungerichteter Graph, dessen Knoten alle einen Grad von mindestens zwei haben, dann hat G mindestens einen Kreis.
Beweis: Sei G ein Graph, so konstruiere in G einen Pfad indem man immer wei- ter Knoten hinzufügt. Dies machen wir so lange bis es sich um einen maximalen Pfad mit beliebiger aber endlicher Länge handelt, da ein Graph endlich viele Knoten und Kanten hat. Dann entsteht zwar kein Kreis, die beiden Endknoten des Pfades haben jedoch einen Grad von eins. Damit diese einen Grad von mindestens zwei haben, müssen diese mit einen der vorhandenen Knoten verbunden werden. Wenn das passiert, so enthält G mindestens einen Kreis. Das zeigt, dass die ursprüngliche Behauptung stimmt.
4.3 Vollständige Induktion
Behauptung: Ein Graph G ist genau dann eulersch, wenn er zusammenhängend ist und alle Knoten einen geraden Grad haben.
Induktionsanfang: Ein Graph, der aus einem Knoten ohne Kanten besteht, ist eulersch.
Induktionsschritt: Sei G = (V, E) ein zusammenhängender Graph mit Kanten und keinem einzelnem isolierten Knoten, sodass für alle v ∈ V gilt deg(v) ≥ 2 und deg(v) ist gerade. Dann wissen wir nach unserem Lemma, dass G einen Kreis C hat. Wenn C alle Kanten von G enthält, hören wir auf, da dies unsere gesuchte Eulertour ist. Andernfalls betrachten wir den Graphen H := (V, E\E(C)). H ist u.U. nicht zusammenhängend. Alle Zusam- menhangskomponenten von H haben immer noch einen geraden Grad, da wir in G die Kanten des Kreises C entfernt haben, was zur Reduk- tion um zwei Kanten (also gerade viele) bei jedem betroffenen Knoten geführt hat. Nach Induktionsannahme ist jede Zusammenhangskom- ponente von H eulersch. Zudem hat jede Zusammenhangskomponente von H mindestens einen Knoten mit C gemeinsam. Dann können wir die Eulertour nach dem Hierholzer Algorithmus zeichnen. In G gibt es eine Eulertour, da die Kanten von H und C zusammen gerade die Kanten von G sind.
5 Ausblick
Neben dem Geschlossen Eulerzug gibt es außerdem auch noch weitere Anwendungsbeispiele oder ähnliche Probleme wie den Offenen Eulerzug, das Königsberger Brückenproblem oder das Hamiltonkreisproblem.
5.1 Offener Eulerzug
Der offene Eulerzug, oder auch Eulerweg genannt, ist ein zu dem geschlossem Eulerzug sehr änhliches Problem. Es handelt sich um einen Weg, der alle Kanten eines Graphen genau einmal enhält. Jedoch sind Anfangs- und Endknoten voneinander verschieben. Ein beliebtes Beispiel für einen solchen Eulerweg ist das Haus vom Nikolaus.
5.2 Königsberger Brückenproblem
Das Königsberger Brückenproblem ist ein von Leonhard Euler hinterfragtes Problem, welches versucht durch vier Städte und sieben Brücken einen Rundgang zu machen, wobei eine Stadt den Grad fünf und der Rest den Grad drei hat. Ein Eulerzug ist in diesem Fall jedoch nicht möglich, da mehr als zwei Knoten ungeraden Grad besitzen.
5.3 Hamiltonkreisproblem
Bei dem Hamiltonkreisproblem handelt es sich um einen Zyklus, der alle Knoten eines Graphen genau einmal durchläuft. Die Anzahl der durchlaufenen Kanten ist hierbei beliebig.
6 Quellen
- https://www3.mathematik.tu-darmstadt.de (Graphen und Algorith- men Dr. Armin Fügenschuh TU Darmstadt)
- http://www.mathepedia.de/Wege,_Pfade,_Zyklen_und_Kreise.aspx
- https://de.wikipedia.org/wiki/Eulerkreisproblem
Häufig gestellte Fragen
Was ist eine Eulertour in der Graphentheorie?
Eine Eulertour ist ein Zyklus, der jede Kante eines Graphen genau einmal enthält.
Welche Bedingungen müssen erfüllt sein, damit ein Graph eine Eulertour besitzt?
Ein Graph ist eulersch, wenn er zusammenhängend ist und alle Knoten einen geraden Grad haben. Alternativ kann man sagen, dass die Kantenmenge des Graphen die Vereinigung aller Kanten von paarweise disjunkten Kreisen ist.
Wie kann man feststellen, ob ein Graph eine Eulertour besitzt?
Man kann das Entscheidungsproblem in linearer Zeit O(N) lösen, indem man mit Breitensuche oder Tiefensuche jeden Knoten auf geraden Grad untersucht.
Was ist der Algorithmus von Hierholzer und wie funktioniert er?
Der Algorithmus von Hierholzer ist ein Verfahren, um eine Eulertour in einem Graphen in Linearzeit zu finden. Er basiert darauf, den Graphen in paarweise kantendisjunkte Kreise zu zerlegen. Der Algorithmus geht von einem ungerichteten zusammenhängenden Graphen aus, der die Bedingung erfüllt, dass alle Knoten geraden Grad haben. Zuerst wird ein Unterkreis konstruiert, dann werden die Kanten dieses Unterkreises vernachlässigt und weitere Unterkreise entstehen ausgehend von Eckpunkten mit Grad größer 0. Die Kreise werden zusammengeführt, bis ein Eulerkreis gefunden wurde.
Was sind Weg, Pfad, Zyklus und Kreis in Bezug auf Graphen?
- Weg: Eine Folge von Knoten, deren aufeinanderfolgende Knoten durch Kanten des Graphen verbunden sind.
- Pfad: Ein Weg, dessen Knoten in der Knotenfolge höchstens einmal auftreten.
- Zyklus: Ein Weg, bei dem Start- und Endknoten in der Knotenfolge identisch sind.
- Kreis: Ein Weg, bei dem ausschließlich der Start- und Endknoten in der Knotenfolge identisch sind und alle anderen Knoten nur einmal vorkommen.
Was ist der Unterschied zwischen einem offenen und einem geschlossenen Eulerzug?
Ein geschlossener Eulerzug (Eulertour) ist ein Zyklus, der alle Kanten eines Graphen genau einmal enthält und im Startknoten endet. Ein offener Eulerzug (Eulerweg) ist ein Weg, der alle Kanten eines Graphen genau einmal enthält, aber Anfangs- und Endknoten sind unterschiedlich.
Was ist das Königsberger Brückenproblem?
Das Königsberger Brückenproblem ist ein Problem, bei dem es darum geht, durch vier Städte und sieben Brücken einen Rundgang zu machen, wobei jede Brücke genau einmal überquert werden soll. Ein Eulerzug ist in diesem Fall nicht möglich, da mehr als zwei Knoten ungeraden Grad besitzen.
Was ist das Hamiltonkreisproblem?
Bei dem Hamiltonkreisproblem handelt es sich um einen Zyklus, der alle Knoten eines Graphen genau einmal durchläuft. Die Anzahl der durchlaufenen Kanten ist hierbei beliebig.
Warum müssen bei einem eulerschen Graphen alle Knoten einen geraden Grad haben?
Wenn ein Knoten einen ungeraden Grad hätte, würde man beim Durchlaufen der Eulertour entweder nicht mehr zu diesem Knoten zurückkehren können oder ihn nicht mehr verlassen können, was der Definition einer Eulertour widerspricht.
- Quote paper
- Tim Kilian (Author), Deniz Guel (Author), 2016, Grundlagen und Beweis der Eulertouren, Munich, GRIN Verlag, https://www.grin.com/document/350008