Euler-Kreise und -Wege
Inhaltsverzeichnis |
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 ein Physiker und Mathematiker
- befasste sich mit vielen Themen der Analysis, Zahlentheorie
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
Euler-Graphen
Was sind Euler-Graphen?
Eulersche Graphen sind Graphen bei denen alle Kanten in einem Graphen einmal Durchlaufen werden.
Ist folgender Graph eulersch?
Antwort
Antwort: Der Graph ist nicht eulersch, da nicht alle Kanten des Graphen in einem Zug miteinander verbunden werden können.
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.
Haus vom 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=8 und E=5:
- 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.
Erklärung
- Warum ist es nur möglich den Graphen vollständig zu zeichen wenn der Startknoten einer der beiden unteren ist?
- Wie viele Möglichkeiten gibt es überhaupt das Haus zu zeichen?
- Warum funktioniert das?
Zu 1.:
- Um dies zu klären muss man zunächst noch einmal den Begriff Knotengrad erläutern.
- Der Grad dG(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:
| Knoten || 1 || 2 || 3 || 4 || 5 | |||||
|---|---|---|---|---|---|
| dG(v) | 3 | 3 | 4 | 4 | 2 |
Euler Kreise
Beispiel
Algorithmen
Algorithmus von Hierholzer
Algorithmus von Fleury
Das Postbotenproblem
Allgemein: Das Postbotenproblem beschäftigt sich damit alle Kannten im Graphen genau ein mal entlang zu laufen.
Definition
Algorithmus
Quellen
- https://de.wikipedia.org/wiki/Eulerkreisproblem
- Wessler_Graphen-und-Netzwerktheorie, André Krischke, Helge Röpcke
- Algorithmen und Komplexität, Christian Wagneknecht