Grundlagen und Beweis der Eulertouren

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 v₁ ∈ 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
- https://de.wikipedia.org/wiki/Weg_(Graphentheorie)