Eulerscher Pfad - Eulerian path

Multigraphen von Königsberg-Brücken und Fünf-Raum-Rätseln haben mehr als zwei ungerade Eckpunkte (in Orange), sind also nicht Eulersch und daher haben die Rätsel keine Lösungen.
Jeder Knoten dieses Graphen hat einen geraden Grad . Daher handelt es sich um einen Eulerschen Graphen. Das Folgen der Kanten in alphabetischer Reihenfolge ergibt einen Eulerschen Kreis/Zyklus.

In der Graphentheorie ist ein Euler-Pfad (oder Euler-Pfad ) ein Pfad in einem endlichen Graphen, der jede Kante genau einmal besucht (was das erneute Besuchen von Scheitelpunkten ermöglicht). In ähnlicher Weise ist ein Euler-Kreis oder Euler-Zyklus ein Euler-Weg, der auf demselben Scheitelpunkt beginnt und endet . Sie wurden erstmals von Leonhard Euler diskutiert , als er 1736 das berühmte Sieben-Brücken-von-Königsberg- Problem löste . Das Problem kann mathematisch wie folgt formuliert werden:

Ist es angesichts des Graphen im Bild möglich, einen Pfad (oder einen Zyklus ; dh einen Pfad, der auf demselben Scheitelpunkt beginnt und endet) zu konstruieren, der jede Kante genau einmal besucht?

Euler bewies, dass eine notwendige Bedingung für die Existenz von Eulerschen Kreisen darin besteht, dass alle Ecken im Graphen einen geraden Grad haben , und stellte ohne Beweis fest, dass zusammenhängende Graphen mit allen Ecken geraden Grades einen Eulerschen Kreis haben. Der erste vollständige Beweis dieser letzteren Behauptung wurde posthum 1873 von Carl Hierholzer veröffentlicht . Dies ist als Satz von Euler bekannt:

Ein zusammenhängender Graph hat genau dann einen Euler-Zyklus, wenn jeder Knoten geraden Grad hat.

Der Begriff Eulerscher Graph hat in der Graphentheorie zwei gängige Bedeutungen. Die eine Bedeutung ist ein Graph mit einem Eulerschen Kreis und die andere ist ein Graph mit jeder Ecke geraden Grades. Diese Definitionen stimmen für verbundene Graphen überein.

Für die Existenz von Eulerschen Spuren ist es notwendig, dass null oder zwei Knoten einen ungeraden Grad haben; Dies bedeutet, dass der Königsberg-Graphen nicht Eulersch ist. Wenn keine Knoten ungeraden Grades vorhanden sind, sind alle Eulerschen Spuren Kreise. Wenn es genau zwei Knoten ungeraden Grades gibt, beginnen alle Eulerschen Pfade an einem von ihnen und enden an dem anderen. Ein Graph, der eine Eulersche Spur, aber keinen Eulerschen Kreis hat, wird als Semi-Eulerian bezeichnet .

Definition

Eine Eulersche Spur oder Euler-Wanderung in einem ungerichteten Graphen ist eine Wanderung, die jede Kante genau einmal verwendet. Existiert ein solcher Walk, wird der Graph als traversierbar oder semi-eulerian bezeichnet .

Ein Euler-Zyklus , Euler-Kreis oder Euler-Tour in einem ungerichteten Graphen ist ein Zyklus , der jede Kante genau einmal verwendet. Existiert ein solcher Zyklus, heißt der Graph Eulerian oder Unicursal . Der Begriff "Eulerscher Graph" wird manchmal auch in einem schwächeren Sinne verwendet, um einen Graphen zu bezeichnen, bei dem jeder Knoten geraden Grad hat. Für endliche zusammenhängende Graphen sind die beiden Definitionen äquivalent, während ein möglicherweise unzusammenhängender Graph genau dann im abgeschwächten Sinne Eulersch ist, wenn jede Zusammenhangskomponente einen Eulerschen Kreis besitzt.

Bei gerichteten Graphen muss "Pfad" durch gerichteten Pfad und "Zyklus" durch gerichteten Zyklus ersetzt werden .

Die Definition und Eigenschaften von Eulerschen Pfaden, Zyklen und Graphen gelten auch für Multigraphen .

Eine Eulersche Orientierung eines ungerichteten Graphen G ist eine Richtungszuweisung an jede Kante von G, so dass an jeder Ecke v der Ingrad von v gleich dem Outgrad von v ist . Eine solche Orientierung existiert für jeden ungerichteten Graphen, in dem jeder Knoten geraden Grad hat, und kann gefunden werden, indem man eine Euler-Tour in jeder zusammenhängenden Komponente von G konstruiert und dann die Kanten entsprechend der Tour ausrichtet . Jede Eulersche Orientierung eines zusammenhängenden Graphen ist eine starke Orientierung , eine Orientierung, die den resultierenden gerichteten Graphen stark zusammenhängend macht .

Eigenschaften

  • Ein ungerichteter Graph hat genau dann einen Eulerschen Kreis, wenn jeder Knoten geraden Grad hat und alle seine Knoten mit einem Grad ungleich null zu einer einzigen zusammenhängenden Komponente gehören .
  • Ein ungerichteter Graph kann genau dann in kantendisjunkte Kreise zerlegt werden, wenn alle seine Ecken geraden Grad haben. Ein Graph hat also genau dann einen Eulerschen Kreis, wenn er in kantendisjunkte Kreise zerlegt werden kann und seine Scheitelpunkte ungleich null zu einer einzigen zusammenhängenden Komponente gehören.
  • Ein ungerichteter Graph hat genau dann eine Eulersche Spur, wenn genau null oder zwei Knoten einen ungeraden Grad haben und alle seine Knoten mit einem Grad ungleich null zu einer einzigen zusammenhängenden Komponente gehören
  • Ein gerichteter Graph hat einen Eulerschen Kreis genau dann, wenn jeder Knoten den gleichen Innengrad und Außengrad hat und alle seine Eckpunkte mit einem Grad ungleich Null zu einer einzigen stark zusammenhängenden Komponente gehören . Äquivalent hat ein gerichteter Graph genau dann einen Eulerschen Kreis, wenn er in kantendisjunkte gerichtete Kreise zerlegt werden kann und alle seine Ecken mit Grad ungleich Null zu einer einzigen stark zusammenhängenden Komponente gehören.
  • Ein gerichteter Graph hat eine Eulersche Spur genau dann, wenn höchstens eine Ecke ( out-degree ) − ( in-degree ) = 1 hat, höchstens eine Ecke hat (in-degree) − (out-degree) = 1, every ein anderer Scheitelpunkt hat den gleichen Ein- und Auswärtsgrad, und alle seine Scheitel mit einem Grad ungleich Null gehören zu einer einzigen zusammenhängenden Komponente des zugrunde liegenden ungerichteten Graphen.

Bau von Eulerian Trails und Circuits

Verwenden von Eulerschen Pfaden zum Lösen von Rätseln, bei denen eine Form mit einem fortlaufenden Strich gezeichnet wird:
1. Da das Haus vom Nikolaus-Puzzle zwei ungerade Eckpunkte (orange) hat, muss der Pfad an einem beginnen und am anderen enden.
2. Annie Popes mit vier ungeraden Scheitelpunkten hat keine Lösung.
3. Wenn keine ungeraden Scheitelpunkte vorhanden sind, kann die Spur überall beginnen und bildet einen Eulerschen Kreis.
4. Lose Enden werden als Knoten vom Grad 1 betrachtet.

Fleurys Algorithmus

Fleurys Algorithmus ist ein eleganter, aber ineffizienter Algorithmus aus dem Jahr 1883. Betrachten Sie einen Graphen, von dem bekannt ist, dass er alle Kanten in derselben Komponente und höchstens zwei Ecken ungeraden Grades hat. Der Algorithmus beginnt an einer Ecke ungeraden Grades oder, falls der Graph keine hat, an einer willkürlich gewählten Ecke. Bei jedem Schritt wählt es die nächste Kante im Pfad als eine, deren Löschen den Graphen nicht trennen würde, es sei denn, es gibt keine solche Kante. In diesem Fall wird die verbleibende Kante am aktuellen Scheitelpunkt ausgewählt. Es bewegt sich dann zum anderen Endpunkt dieser Kante und löscht die Kante. Am Ende des Algorithmus gibt es keine Kanten mehr, und die Sequenz, aus der die Kanten ausgewählt wurden, bildet einen Eulerschen Kreis, wenn der Graph keine Ecken ungeraden Grades hat, oder eine Eulersche Spur, wenn es genau zwei Ecken ungeraden Grades gibt.

Während die Graphendurchquerung im Fleury-Algorithmus linear in der Anzahl der Kanten ist , müssen wir auch die Komplexität der Brückenerkennung berücksichtigen . Wenn wir Tarjans linearen Zeitbrückenfindungsalgorithmus nach dem Entfernen jeder Kante erneut ausführen sollen , hat Fleurys Algorithmus eine Zeitkomplexität von . Ein dynamischer Brückenfindungsalgorithmus von Thorup (2000) ermöglicht eine Verbesserung auf , aber dies ist immer noch deutlich langsamer als alternative Algorithmen.

Hierholzer-Algorithmus

Hierholzers Aufsatz von 1873 bietet eine andere Methode zum Auffinden von Euler-Zyklen, die effizienter ist als der Fleury-Algorithmus:

  • Wählen Sie einen beliebigen Startscheitelpunkt v und folgen Sie einer Kantenspur von diesem Scheitelpunkt, bis Sie zu v zurückkehren . Es ist nicht möglich, an einem anderen Scheitelpunkt als v stecken zu bleiben , da der gerade Grad aller Scheitelpunkte sicherstellt, dass beim Eintritt der Spur in einen anderen Scheitelpunkt w eine ungenutzte Kante übrig bleiben muss, die w verlässt . Die auf diese Weise gebildete Tour ist eine geschlossene Tour, die jedoch möglicherweise nicht alle Ecken und Kanten des ursprünglichen Graphen abdeckt.
  • Solange es einen Scheitelpunkt u gibt , der zur aktuellen Tour gehört, aber benachbarte Kanten hat, die nicht Teil der Tour sind, starten Sie einen anderen Pfad von u , folgen Sie ungenutzten Kanten, bis Sie zu u zurückkehren , und schließen Sie die so gebildete Tour an die vorherige an Tour.
  • Da wir davon ausgehen, dass der ursprüngliche Graph zusammenhängend ist , werden alle Kanten des Graphen durch das Wiederholen des vorherigen Schrittes erschöpft.

Durch die Verwendung einer Datenstruktur wie einer doppelt verketteten Liste , um den Satz von unbenutzten Kanten beizubehalten, die zu jedem Scheitelpunkt gehören, um die Liste der Scheitelpunkte auf der aktuellen Tour mit ungenutzten Kanten zu verwalten und um die Tour selbst zu pflegen, können die einzelnen Operationen der Der Algorithmus (das Finden ungenutzter Kanten, die aus jedem Scheitelpunkt austreten, das Finden eines neuen Startscheitelpunkts für eine Tour und das Verbinden zweier Touren, die sich einen Scheitelpunkt teilen) kann jeweils in konstanter Zeit ausgeführt werden, so dass der Gesamtalgorithmus lineare Zeit benötigt , .

Dieser Algorithmus kann auch mit einem deque implementiert werden . Da es nur möglich ist, stecken zu bleiben, wenn die Deque eine geschlossene Tour darstellt, sollte man die Deque drehen, indem man Kanten vom Schwanz entfernt und sie am Kopf hinzufügt, bis sie sich lösen, und dann fortfahren, bis alle Kanten berücksichtigt sind. Dies erfordert auch lineare Zeit, da die Anzahl der durchgeführten Drehungen nie größer ist als (intuitiv werden alle "schlechten" Kanten zum Kopf verschoben, während neue Kanten zum Schwanz hinzugefügt werden)

Orthographische Projektionen und Schlegel-Diagramme mit Hamiltonschen Zyklen der Eckpunkte der fünf platonischen Körper – nur das Oktaeder hat eine Eulersche Bahn oder einen Kreis, indem es seinen Weg mit dem gepunkteten verlängert

Zählen von Eulerschen Kreisen

Komplexitätsprobleme

Die Anzahl der Eulersche Schaltungen in Digraphe kann mit dem sogenannten berechnet werden BEST Theorem , benannt nach de B ruijn , van Aardenne- E hrenfest , S mith und T Utte . Die Formel besagt, dass die Anzahl der Eulerschen Kreise in einem Digraphen das Produkt bestimmter Gradfaktorialien und der Anzahl verwurzelter Arboreszenzen ist . Letztere kann als Determinante nach dem Matrixbaumsatz berechnet werden , was einen polynomialen Zeitalgorithmus ergibt.

Das BEST-Theorem wird erstmals in dieser Form in einer "note add in proof" zum Aardenne-Ehrenfest und de Bruijn Paper (1951) angegeben. Der ursprüngliche Beweis war bijektiv und verallgemeinerte die de Bruijn-Folgen . Es ist eine Variation eines früheren Ergebnisses von Smith und Tutte (1941).

Das Zählen der Anzahl der Eulerschen Kreise auf ungerichteten Graphen ist viel schwieriger. Dieses Problem ist als #P-vollständig bekannt . In positiver Richtung wird angenommen, dass ein Markov-Ketten-Monte-Carlo- Ansatz über die Kotzig-Transformationen (eingeführt von Anton Kotzig 1968) eine scharfe Näherung für die Anzahl der Eulerschen Kreise in einem Graphen liefert, obwohl es dafür noch keinen Beweis gibt Tatsache (auch für Graphen mit beschränktem Grad).

Sonderfälle

Die asymptotische Formel für die Anzahl der Eulerschen Kreise in den vollständigen Graphen wurde von McKay und Robinson (1995) bestimmt:

Eine ähnliche Formel wurde später von MI Isaev (2009) für vollständige zweiteilige Graphen erhalten :

Anwendungen

Eulersche Spuren werden in der Bioinformatik verwendet, um die DNA-Sequenz aus ihren Fragmenten zu rekonstruieren . Sie werden auch im CMOS- Schaltungsdesign verwendet, um eine optimale Anordnung der Logikgatter zu finden . Es gibt einige Algorithmen zum Verarbeiten von Bäumen , die auf einer Euler-Tour des Baums beruhen (wobei jede Kante als ein Bogenpaar behandelt wird). Die de Bruijn - Folgen können als Eulersche Spuren von de Bruijn - Graphen konstruiert werden .

In unendlichen Graphen

Ein unendlicher Graph mit allen Eckengraden gleich vier, aber ohne Eulersche Linie

In einem unendlichen Graphen ist das entsprechende Konzept einer Eulerschen Spur oder eines Eulerschen Zyklus eine Eulersche Linie, eine doppelt unendliche Spur, die alle Kanten des Graphen bedeckt. Es reicht für die Existenz einer solchen Spur nicht aus, dass der Graph zusammenhängend ist und alle Eckengrade gerade sind; zum Beispiel hat der gezeigte unendliche Cayley-Graphen , bei dem alle Scheitelgrade gleich vier sind, keine Eulersche Linie. Die unendlichen Graphen, die Eulersche Linien enthalten, wurden von Erdõs, Grünwald & Weiszfeld (1936) charakterisiert . Damit ein unendlicher Graph oder Multigraph G eine Eulersche Gerade hat, ist es notwendig und ausreichend, dass alle der folgenden Bedingungen erfüllt sind:

  • G ist verbunden.
  • G hat abzählbare Mengen von Ecken und Kanten.
  • G hat keine Ecken (endlichen) ungeraden Grades.
  • Das Entfernen eines endlichen Teilgraphen S aus G hinterlässt höchstens zwei unendliche Zusammenhangskomponenten im verbleibenden Graphen, und wenn S einen geraden Grad an jeder seiner Ecken hat, dann hinterlässt das Entfernen von S genau eine unendliche Zusammenhangskomponente.

Siehe auch

  • Eulersches Matroid , eine abstrakte Verallgemeinerung von Eulerschen Graphen
  • Fünf-Zimmer-Puzzle
  • Handshaking-Lemma , bewiesen von Euler in seiner Originalarbeit, das zeigt, dass jeder ungerichtete zusammenhängende Graph eine gerade Anzahl von Knoten ungeraden Grades hat
  • Hamilton-Pfad – ein Pfad, der jeden Scheitelpunkt genau einmal besucht.
  • Routeninspektionsproblem , Suche nach dem kürzesten Pfad, der alle Kanten besucht, möglicherweise wiederholende Kanten, wenn kein Euler-Pfad existiert.
  • Satz von Veblen , dass Graphen mit geradem Scheitelgrad unabhängig von ihrer Konnektivität in kantendisjunkte Zyklen unterteilt werden können

Anmerkungen

Verweise

Externe Links