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>==
Allgemeines über Euler:
<ul>
<li>geboren am 15. April 1707 in Basel</li>
<li>gestorben  am 18. September 1783 in Sankt Petersburg</li>
<li>war ein Physiker und Mathematiker</li>
<li>befasste sich mit vielen Themen der Analysis, Zahlentheorie</li>
</ul>

== <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 <u>Kinderrätzel</u>: "Das-ist-das-Haus-des-Ni-ko-laus"
*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?
* Stichwort: Start-,Endknoten; Anzahl Möglichkeiten; Erfolgsrate
* Dieser Graph enthält also einen Eulerweg, wobei sich besonders hier die Bedeutung des Knotengrades zeigt.
<popup name="Erklärung">
# Warum ist es nur möglich den Graphen vollständig zu zeichen wenn der Startknoten einer der beiden unteren ist?
# Wie viele Möglichkeiten gibt es überhaupt das Haus zu zeichen?
# Warum funktioniert das?
</popup>

== <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