Eulerkreisproblem

Stichpunkte

Allgemein
	Ein Eulerkreis oder (geschlossener) Eulerzug (auch Eulertour oder Eulersche Linie) ist in der Graphentheorie ein Zyklus
	der alle Kanten eines Graphen genau einmal enthält
	d.h. statt eines Zyklus wird lediglich ein Weg verlangt
	wenn die Identität von Start- und Endknoten nicht verlangt wird
	Ein offener Eulerzug oder Eulerweg ist dann gegeben
	der jede Kante des Graphen genau einmal enthält
	der einen Eulerkreis besitzt
	Einen zusammenhängenden Graph
	bezeichnet man auch als eulersch
	zu einem gegebenen Graph zu bestimmen
	bezeichnet man als Eulerkreis-Problem
	Die Aufgabe
	ob dieser eulersch ist oder nicht
	Es geht auf das 1736 von Leonhard Euler gelöste Königsberger Brückenproblem zurück
	Das Problem existiert auch für gerichtete Graphen und Graphen mit Mehrfachkanten. Inhaltsverzeichnis showTocToggle("Anzeigen"
	"Verbergen") 1 Beispiel 2 Eigenschaften 2.1 Verallgemeinerung: Eulerweg 3 Lösung 4 Anwendungsbeispiele 4.1 Das Königsberger Brückenproblem 4.2 "Das-ist-das-Haus-vom-Nikolaus" 5 Siehe auch [Bearbeiten]
Beispiel
	[Bearbeiten]
Eigenschaften
	Für ungerichtete Graphen sind folgende Aussagen äquivalent: G ist eulersch
	G ist zusammenhängend und jeder Knoten hat geraden Grad
	G ist zusammenhängend und die Kantenmenge von G ist die Vereinigung aller Kanten von paarweise disjunkten Kreisen. Analog sind für gerichtete Graphen folgende Aussagen äquivalent: G ist eulersch
	G ist stark zusammenhängend und für jeden Knoten sind Eingangsgrad und Ausgangsgrad äquivalent
	G ist stark zusammenhängend und die Kantenmenge von G ist die Vereinigung aller Kanten von paarweise disjunkten gerichteten Kreisen. [Bearbeiten]
Verallgemeinerung: Eulerweg
	Ein (ungerichteter zusammenhängender) Graph enthält einen Eulerweg gdw
	2 oder 0 seiner Knoten von ungeradem Grad sind; Sind es genau 0 Knoten handelt es sich bei dem Eulerweg um einen Eulerkreis. [Bearbeiten]
Lösung
	da ein Graph genau dann eulersch ist
	wenn er zusammenhängend ist und jeder Knoten geraden Grad besitzt
	Das Problem lässt sich relativ leicht algorithmisch lösen
	Mittels Tiefensuche lässt sich dies leicht in linearer Zeit feststellen
	Zu einem eulerschen Graphen einen Eulerkreis zu finden erfordert dagegen einen etwas komplizierteren Algorithmus
	der auch auf Tiefensuche basiert und dieses Problem ebenfalls in Linearzeit lösen kann
	dass eulersche Graphen auch dadurch charakterisiert werden können
	Den ersten Linearzeit-Algorithmus dafür konnte Hierholzer angeben
	der ausnutzte
	dass sie aus kantendisjunkten Kreisen zusammengesetzt werden können. [Bearbeiten]
Anwendungsbeispiele
	[Bearbeiten]
Das Königsberger Brückenproblem
	sind die jeweiligen Stadtteile bzw
	Das Königsberger Brückenproblem lässt sich in folgendem Graphen ausdrücken: Die roten Punkte (Knoten)
	Standpunkte
	Die blauen Linien (Kanten) sind die Brücken
	dass es nicht möglich ist
	Durch Probieren wird man herausfinden
	alle Stadtteile hintereinander zu besuchen und jede Brücke nur ein einziges Mal zu benutzen
	Es gibt also keinen Eulerweg und demzufolge auch keinen Eulerkreis
	Warum ist das so? Euler hat die folgende Gesetzmäßigkeit entdeckt: In einem Graph gibt es mindestens einen Eulerweg
	wenn dieser maximal 2 Knoten mit ungeradem Grad besitzt (wenn also nicht an mehr als zwei Knoten eine ungerade Anzahl Kanten angeschlossen sind)
	Beim Königsberger Brückengraphen gibt es vier Knoten mit ungeradem Grad (die Zahlen neben den Knoten geben hier deren Grad an)
	Deshalb ist der Stadtrundgang mit dem nur einmaligen Benutzen jeder Brücke unmöglich. [Bearbeiten]
"Das-ist-das-Haus-vom-Nikolaus"
	da sein Graph Knoten vom Grad 3 enthält. Ein Eulerweg ist z.B
	Das beliebte Kinderrätsel "Das ist das Haus vom Nikolaus" hingegen enthält einen Eulerweg
	aber keinen Eulerkreis
	1-2-4-3-1-4-5-3-2
	3
	Ein Quadrat mit Diagonalen enthält keinen Eulerweg
	2
	4 mit den verbindenden Kanten.) [Bearbeiten]
	da alle seine Knoten den Grad 3 haben. (Im Bild sind das nur die Punkte 1
Siehe auch
	Wege
	Zyklen und Kreise in Graphen en:Eulerian path ja:オイラー路 zh:欧拉图
	Pfade

Dieser Artikel basiert auf dem Artikel Eulerkreisproblem aus der freien Enzyklopädie wikipedia und steht unter der GNU Lizenz für freie Dokumentation. In der wikipedia ist eine Liste der Autoren verfügbar.