Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenSamstag, 15. August 2020 

Eulerkreis-Problem


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Ein Eulerkreis oder (geschlossener) Euler-Zug (auch Eulertour oder Eulersche Linie ) ist in der Graphentheorie ein Zyklus der alle Kanten eines Graphen genau einmal enthält. Ein offener Euler-Zug oder Eulerweg ist dann gegeben wenn die Identität Start- und Endknoten nicht verlangt wird d.h. eines Zyklus wird lediglich ein Weg verlangt der jede Kante des Graphen einmal enthält. Einen Graph der einen Eulerkreis besitzt bezeichnet man auch als eulersch .

Die Aufgabe zu einem gegebenen Graph bestimmen ob dieser eulersch ist oder nicht man als Eulerkreis-Problem . 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

Beispiel

Eigenschaften

Für ungerichtete Graphen sind folgende Aussagen

  1. G ist eulersch
  2. G ist zusammenhängend und jeder Knoten hat geraden Grad (Graphentheorie) .
  3. G ist zusammenhängend und die Kantenmenge von G ist die Vereinigung aller Kanten von disjunkten Kreisen.

Analog sind für gerichtete Graphen folgende äquivalent:

  1. G ist eulersch
  2. G ist stark zusammenhängend und für jedem Knoten sind Eingangsgrad und Ausgangsgrad äquivalent.
  3. G ist stark zusammenhängend und die Kantenmenge G ist die Vereinigung aller Kanten von disjunkten gerichteten Kreisen.

Lösung

Das Problem lässt sich relativ leicht lösen da ein Graph genau dann eulersch wenn er zusammenhängend ist und jeder Knoten Grad besitzt. Mittels Tiefensuche lässt sich dies in linearer Zeit feststellen. Zu einem eulerschen einen Eulerkreis zu finden erfordert dagegen einen komplizierteren Algorithmus der auch auf Tiefensuche basiert dieses Problem ebenfalls in Linearzeit lösen kann. ersten Linearzeit-Algorithmus dafür konnte Hierholzer angeben der dass eulersche Graphen auch dadurch charakterisiert werden dass sie aus kantendisjunkten Kreisen zusammengesetzt werden

Anwendungsbeispiele

Das Königsberger Brückenproblem

Das Königsberger Brückenproblem lässt sich in Graphen ausdrücken:

Die roten Punkte ( Knoten ) sind die jeweiligen Stadtteile bzw. Standpunkte. blauen Linien ( Kanten ) sind die Brücken. Durch Probieren wird herausfinden dass es nicht möglich ist alle hintereinander zu besuchen und jede Brücke nur einziges Mal zu benutzen. Es gibt also Eulerweg und demzufolge auch keinen Eulerkreis. Warum das so?

Euler hat die folgende Gesetzmäßigkeit entdeckt: einem Graph gibt es mindestens einen Eulerweg dieser maximal 2 Knoten mit ungeradem Grad (wenn also nicht an mehr als zwei eine ungerade Anzahl Kanten angeschlossen sind). Beim Brückengraphen gibt es vier Knoten mit ungeradem (die Zahlen neben den Knoten geben hier Grad an). Deshalb ist der Stadtrundgang mit nur einmaligen Benutzen jeder Brücke unmöglich.

"Das-ist-das-Haus-vom-Nikolaus"

Das beliebte Kinderrätsel "Das-ist-das-Haus-vom-Nikolaus" hingegen enthält Eulerweg aber keinen Eulerkreis da sein Graph vom Grad 3 enthält.

Ein Eulerweg ist z.B. 1-2-4-3-1-4-5-3-2.

Ein Quadrat mit Diagonalen enthält keinen da alle seine Knoten den Grad 3 (Im Bild sind das nur die Punkte 2 3 4 mit den verbindenden Kanten.)

Siehe auch



Bücher zum Thema Eulerkreis-Problem

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Eulerscher_Graph.html">Eulerkreis-Problem </a>