Eulerkreisproblem - LinkFang.de





Eulerkreisproblem


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. Ein offener Eulerzug (Eulerpfad oder auch Eulerweg) ist dann gegeben, wenn die Identität von Start- und Endknoten nicht verlangt wird, d. h. statt eines Zyklus wird lediglich eine Kantenfolge verlangt, welche jede Kante des Graphen genau einmal enthält. Einen zusammenhängenden Graphen, der einen Eulerkreis besitzt, bezeichnet man auch als eulerschen Graphen. Enthält ein Graph lediglich einen Eulerweg und keinen Eulerkreis, so nennt man ihn einen semieulerschen Graph.

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

Entgegen seinem Namen ist der Eulerkreis kein Kreis, zumindest wenn man der häufigen Definition folgt, nach der sich in einem Kreis kein Knoten wiederholen darf.

Charakterisierung

Nach dem Satz von Euler–Hierholzer kann man eulersche Graphen leicht charakterisieren.

Sei G ein Graph, bei dem höchstens eine Zusammenhangskomponente Kanten enthält.

Dann sind folgende Aussagen äquivalent:

  1. G ist eulersch,
  2. jeder Knoten in G hat geraden Grad.
  3. die Kantenmenge von G ist die Vereinigung aller Kanten von paarweise disjunkten Kreisen.

Analog sind für einen gerichteten Graphen G, bei dem höchsten eine starke Zusammenhangskomponente Kanten enthält folgende Aussagen äquivalent:

  1. G ist eulersch,
  2. für jeden Knoten in G sind Eingangsgrad und Ausgangsgrad gleich.
  3. die Kantenmenge von G ist die Vereinigung aller Kanten von paarweise disjunkten gerichteten Kreisen.

Verallgemeinerung: Eulerweg

Ein (ungerichteter zusammenhängender) Graph enthält genau dann einen Eulerweg, wenn zwei oder keiner seiner Knoten von ungeradem Grad sind; hat kein Knoten ungeraden Grad, handelt es sich bei dem Eulerweg um einen Eulerkreis.

Entscheidungsproblem

Die Frage, ob für einen gegebenen Graph ein Eulerkreis existiert, lässt sich algorithmisch relativ leicht lösen, da ein Graph genau dann eulersch ist, wenn er zusammenhängend ist und jeder Knoten geraden Grad besitzt. Mittels Tiefensuche lässt sich dies leicht in linearer Zeit feststellen.

Auffinden eines Eulerkreises

Zum Auffinden eines Eulerkreises existieren mehrere Verfahren. Der Algorithmus von Fleury stammt aus dem Jahr 1883 und verfolgt einen sehr einfachen Ansatz, weshalb er eine Laufzeit von der Größenordnung [math] \mathcal{O}(|E|^2) [/math] hat. Effizienter ist der Algorithmus von Hierholzer, der einen Eulerkreis in Linearzeit berechnet. Er basiert darauf, dass sich ein eulerscher Graph in paarweise kantendisjunkte Kreise zerlegen lässt.

Algorithmus von Hierholzer

Hauptartikel: Algorithmus von Hierholzer
  1. Wähle einen beliebigen Knoten [math]v_0[/math] des Graphen und konstruiere von [math]v_0[/math] ausgehend einen Unterkreis [math]K[/math] in [math]G[/math], der keine Kante in [math]G[/math] zweimal durchläuft.
  2. Wenn [math]K[/math] ein Eulerkreis ist, breche ab. Andernfalls:
  3. Vernachlässige nun alle Kanten des Unterkreises [math]K[/math].
  4. Am ersten Eckpunkt von [math]K[/math], dessen Grad größer 0 ist, lässt man nun einen weiteren Unterkreis [math]K'[/math] entstehen, der keine Kante in [math]K[/math] durchläuft und keine Kante in [math]G[/math] zweimal enthält.
  5. Füge in [math]K[/math] den zweiten Kreis [math]K'[/math] ein, indem der Startpunkt von [math]K'[/math] durch alle Punkte von [math]K'[/math] in der richtigen Reihenfolge ersetzt wird.
  6. Nenne jetzt den so erhaltenen Kreis [math]K[/math] und fahre bei Schritt 2 fort.

Algorithmus von Fleury

Im Algorithmus von Fleury spielen Brückenkanten eine wichtige Rolle. Das sind Kanten, ohne die der Graph in zwei Zusammenhangskomponenten zerfallen würde.

Der Algorithmus fügt einer anfangs leeren Kantenfolge alle Kanten eines Graphen hinzu, sodass ein Eulerkreis entsteht.

  1. Wähle einen beliebigen Knoten als aktuellen Knoten.
  2. Wähle unter den unmarkierten, mit dem aktuellen Knoten inzidenten Kanten eine beliebige Kante aus. Dabei sind zuerst Kanten zu wählen, die im unmarkierten Graphen keine Brückenkanten sind.
  3. Markiere die gewählte Kante und füge sie der Kantenfolge hinzu.
  4. Wähle den anderen Knoten der gewählten Kante als neuen aktuellen Knoten.
  5. Wenn noch unmarkierte Kanten existieren, dann gehe zu Schritt 2.

Ob eine Kante eine Brückenkante ist, kann mittels Tiefensuche in Laufzeit [math] \mathcal{O}(|E|) [/math] überprüft werden. Da pro Schritt eine Kante entfernt wird, benötigt man [math] \left| E \right| [/math] Iterationen. Die Anzahl der pro Iteration geprüften Kanten entspricht dem Grad des aktuellen Knotens. Insgesamt kann man die gesamte Anzahl überprüfter Kanten durch [math] \mathcal{O}(|E|) [/math] beschränken. Die gesamte Laufzeit ist damit von der Größenordnung [math] \mathcal{O}(|E|^2) [/math].

Geschichte

Leonhard Euler fragte in seiner Arbeit 1736 zum Königsberger Brückenproblem, ob der durch die Brücken der Stadt gegebene Graph ein Euler-Graph ist, das heißt, ob ein Eulerweg existiert, und verneinte dies, da der Graph ungerade Ecken hatte. Euler bewies, dass ein Eulergraph nur gerade Ecken haben kann. Er vermutete auch (bzw. gab ohne Beweis an), dass dies eine hinreichende Bedingung sei: Ein zusammenhängender Graph, in dem jede Ecke gerade ist, ist ein Euler-Graph. Ein Beweis des Satz wurde zuerst von Carl Hierholzer 1873 veröffentlicht [1]. Darin gab er auch den Algorithmus von Hierholzer zum Auffinden des Eulerwegs an.

Anwendungsbeispiele

Das Königsberger Brückenproblem

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

Die Kreise (Knoten) sind die jeweiligen Stadtteile bzw. Standpunkte. Die Linien (Kanten) sind die Brücken. Durch Probieren wird man herausfinden, dass es nicht möglich ist, einen Rundgang durch die Stadt zu finden, bei dem jede Brücke genau ein einziges Mal benutzt wird. Es gibt also keinen Eulerweg und demzufolge auch keinen Eulerkreis. Warum ist das so?

Euler hat die folgende Gesetzmäßigkeit entdeckt: Wenn in einem Graphen G ein Eulerweg existiert, dann haben maximal 2 Knoten ungeraden Grad (Anzahl angeschlossener Kanten). 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.

Ein ungerader Knoten ist entweder Anfang oder Ende des Weges über die Brücken: null ungerade Knoten würde bedeuten, dass Anfang und Ende des Weges in Königsberg identisch sind. Ein Weg mit Anfang und Ende hätte maximal zwei ungerade Knoten. Ergo ist es in Königsberg nicht möglich gewesen, alle Brücken in einem Wege nur jeweils einmal zu begehen.

Das Haus vom Nikolaus

Das beliebte Kinderrätsel „Das ist das Haus vom Nikolaus“ hingegen enthält einen Eulerweg, aber keinen Eulerkreis, da sein Graph zwei Knoten vom Grad 3 enthält.

Ein Eulerweg ist z. B. 1-2-4-3-1-4-5-3-2. Knoten 1 und 2 haben jeweils 3 Nachbarn, ihr Grad ist ungerade. Um das Haus in einem Zug zeichnen zu können, muss man daher an einem dieser beiden Punkte beginnen.

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

Siehe auch

  • Hamiltonkreisproblem – ähnliches Problem, bei dem alle Knoten statt Kanten genau einmal durchlaufen werden müssen.

Literatur

Einzelnachweise

  1. Hierholzer Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren, Mathematische Annalen, Bd. 6, 1873, S.30-32, Online

Kategorien: Problem (Graphentheorie)

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Eulerkreisproblem (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.