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 Kreise

Beispiel

Euler Wege

• Ein Euler Weg oder auch offener Eulerzug, ist ein Zyklus eines Graphen innerhalb der Grapentheorie, bei welchem der Start- und Endknoten nicht identisch sind.
• D.h. Insofern man alle Kanten in einem Zug miteinander verbindet ist der Graph eulersch
• Ein zusammenhängender ungerichteter Graph enthält genau dann einen Eulerweg, wenn der Gaph höchstens Zwei Knoten mit ungeraden Grad besitzt.
• Es sei ein Graph G(V,E) gegeben:

Haus vom Nikolaus

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