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.
• Ein zusammenhängender ungerichteter Graph enthält genau dann einen Eulerweg, wenn der Gaph zwei Knoten mit ungeraden Grad besitzt.
• Es sei ein Graph G(V,E) gegeben:

Haus vom Nikolaus

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