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? Eulerische Graphen sind Graphen bei denen alle Kanten in einem Graphen einmal Durchlaufen werden. Das heißt: G'=(V,E) Ist folgender Graph eulersch?

Euler Kreise

Beispiel

Euler Wege

• Ein Euler Weg oder auch offener Eulerzug, ist ein Zyklus innerhalb der Grapentheorie, bei welchem der Start- und Endknoten nicht identisch sind.

D.h. Nach einmaligen Durchgehen aller Kanten des Graphen

• 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