Patrick Schmidt (Euler Wege, Algorithmus von Hierholzer,Fleur,Postprobem Definition) Kevin Richter (Einführung, Euler Kreise, Postbotenproblem(Algorithmus))

Einführung

Leonhard Euler

Allgemeines über Euler:

• 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

Motivation

• 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.

Euler-Graphen

Definition

Was sind Euler-Graphen?

• G=(V,E) ist genau dann eulersch, wenn ein Weg bzw. Kreis P existiert, für den gilt E(G)=E(P)
• Das bedeutet eulersche Graphen sind Graphen bei denen alle Kanten genau einmal durchlaufen werden müssen.
  

Ist folgender Graph eulersch?

Euler Kreise

• Euler-Kreise oder auch geschlossene Eulerzüge bzw. Eulertouren sind Zyklen in Graphen, die alle Kanten des Graphen enthalten.
• Desweiteren haben sie einen gemeinsamen Start bzw. Endpunkt.

Beispiel

Euler Wege

• 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.

Das Haus des Nikolaus

Ein altes, aber heute noch präsentes Kinderrätzel: "Das-ist-das-Haus-des-Ni-ko-laus"

• Gegeben sei ein Graph G(V,E) mit V=5 und E=8:

• 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.

Algorithmen

Lösbarkeit

• 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.

Algorithmus von Fleury

• Beim Algorithmus von Fleury sind Brückenkanten von besonderer Bedeutung.
• Dies sind Kanten, ohne die der Graph in zwei Komponenten zerfallen würde.
  
• Input: Graph G(V,E)

1. Wähle einen beliebigen Knoten als aktuellen Knoten.
2. Wähle nun unter den mit dem aktuellen Knoten inzidenten Kanten eine beliebige Kante aus.
   Dabei sind zuerst Kanten zu wählen, die im unmarkierten Graphen keine Brückenkanten sind.
3. Markiere die gewählte Kante und entferne sie.
4. Wähle den anderen Knoten der gewählten Kante als neuen aktuellen Knoten.
5. 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²|).

Algorithmus von Hierholzer

• Dieser Algorithmus macht sich die Eigenschaften zu nutze, dass eulersche Graphen in paarweise Kantendisjunkte Kreise zerlegt werden können.
• Input: Graph G(V,E)

• 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.

Das Postbotenproblem

Definition

• Erstmal 1962 vom chinesischen Mathematiker Mei-Ko Kwan definiert.
• Ein Postbote soll die Briefe (auf beiden Seiten der Straße gleichzeitig) in einem Straßennetzwerk (Stadt) zustellen.
• Dies soll in kürzester Zeit geschehen.
• Ergo: Das Postbotenproblem beschäftigt sich damit in kürzester Zeit alle Kanten im Graphen genau einmal entlang zu laufen.
• Hierbei werden Kreuzungen als Knoten und Straßen als Kanten, sowie deren Länge als Gewicht betrachtet.

Algorithmus

Bei Eulergraphen ist dies die Lösung der jeweilige Eulerweg bzw. Eulerkreis. Wenn der Graph nicht eulersch ist müssen Kanten hinzugefügt werden, sodass er wieder eulersch wird.

Aus Wikipedia noch umschreiben

• Ist ein zusammenhängender Graph nicht Eulersch, besitzt er V > 0 Knoten mit ungeradem Knotengrad.
• Da in jedem Graphen Knoten mit ungeradem Grad nur in gerader Anzahl auftreten, ist R gerade.
• Verbindet man jeweils zwei Knoten ungeraden Knotengrades durch einen zusätzlichen Weg, werden die ungeraden Knotengrade gerade, während die geraden Knotengrade gerade bleiben.
• Um den Graph eulersch zu machen müssen also insgesamt \frac{r}{2} zusätzliche Wege in den Graphen eingefügt werden.

Zur kostenminimalen Erweiterung des Graphen wird zu den Knoten mit ungeradem Grad ein vollständiger Graph erstellt. Als Kantengewichte wählt man jeweils die Distanz des kürzesten Weges (beispielsweise mit dem Matrixmultiplikations- oder dem Tripelalgorithmus ermittelt) zwischen den beiden entsprechenden Knoten im ursprünglichen Graphen. In diesem vollständigen Graphen wird dann eine kostenminimale perfekte Paarung mit \frac{r}{2} Matchingkanten gesucht. Für jede Matchingkante werden dann im ursprünglichen Graphen die Kanten des entsprechenden kürzesten Weges zwischen den beiden Knoten dupliziert. Auf diesen Kanten des Ursprungsgraphen muss der Briefträger also genau zweimal entlanglaufen. Jede Eulertour in dem so erweiterten Graphen ist dann eine optimale Lösung des Briefträgerproblems.

Anwendungsbeispiele

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.

• 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 nicht möglich ist alle Brücken einmalig zu überqueren.

Quellen

• https://de.wikipedia.org/wiki/Eulerkreisproblem
• Wessler_Graphen-und-Netzwerktheorie, André Krischke, Helge Röpcke
• Algorithmen und Komplexität, Christian Wagenknecht