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

Einführung

Leonhard Euler

Königsberger Brückenproblem

Euler-Graphen

Was sind Euler-Graphen?
Eulersche Graphen sind Graphen bei denen alle Kanten in einem Graphen einmal Durchlaufen werden.

Ist folgender Graph eulersch?

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.

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