Euler-Kreise und -Wege

Wiki-Quelltext dieser Seite.

Patrick Schmidt (Euler Wege, Algorithmus von Hierholzer,Fleur,Postprobem Definition)
Kevin Richter (Einführung, Euler Kreise, Postbotenproblem(Algorithmus))
= <b><font color="black">Einführung</font color></b>=
== <b><font color="blacjavascript:openUploadWindow()k">Leonhard Euler </font color></b>==
== <b><font color="black">Königsberger Brückenproblem</font color></b>==
= <b><font color="black">Euler-Graphen </font color></b>=
Was sind Euler-Graphen?<br>
Eulersche Graphen sind Graphen bei denen alle Kanten in einem Graphen einmal Durchlaufen werden.<br>
<br>Ist folgender Graph eulersch?
[[Bild:eulergraph.PNG]]
<popup name="Antwort">
[[Bild:eulergraph_lsg.PNG]]<br>
Antwort: Der Graph ist nicht eulersch, da nicht alle Kanten des Graphen in einem Zug miteinander verbunden werden können.
</popup>
== <b><font color="black">Euler Wege </font color></b>==
* 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.

=== <b><font color="black">Haus vom Nikolaus</font color></b>===
Ein altes, aber heute noch präsentes Kinderrätzel: "Das Haus des Nikolaus"
*Gegeben sei ein Graph G(V,E) mit V=8 und E=5:
[[Bild:nikolaus_haus.gif]]
* 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.
== <b><font color="black">Euler Kreise </font color></b>==
=== <b><font color="black">Beispiel</font color></b>===


= <b><font color="black">Algorithmen</font color></b>=
== <b><font color="black">Algorithmus von Hierholzer</font color></b>==
== <b><font color="black">Algorithmus von Fleury</font color></b>==
= <b><font color="black">Das Postbotenproblem</font color></b>=
Allgemein: Das Postbotenproblem beschäftigt sich damit alle Kannten im Graphen <em>genau ein mal</em> entlang zu laufen.
== <b><font color="black">Definition</font color></b>==
== <b><font color="black">Algorithmus</font color></b>==
= <b><font color="black">Quellen</font color></b>=
* https://de.wikipedia.org/wiki/Eulerkreisproblem
* Wessler_Graphen-und-Netzwerktheorie, André Krischke, Helge Röpcke
* Algorithmen und Komplexität, Christian Wagneknecht