Euler-Pfad

In der Graphentheorie ist ein Eulerweg ein Pfad in einem endlichen Graphen , der jede Kante genau einmal besucht (wobei Knoten wieder besucht werden dürfen). Analog dazu ist ein Eulerkreis ein Eulerweg , der am selben Knoten beginnt und endet. Leonhard Euler diskutierte diese Konzepte erstmals 1736 im Zusammenhang mit der Lösung des berühmten Königsberger Brückenproblems. Mathematisch lässt sich das Problem wie folgt formulieren:

Ist es angesichts des im Bild dargestellten Graphen möglich, einen Pfad (oder einen Zyklus ; d. h. einen Pfad, der am selben Knoten beginnt und endet) zu konstruieren, der jede Kante genau einmal besucht?

Euler bewies , dass eine notwendige Bedingung für die Existenz von Eulerkreisen darin besteht, dass alle Knoten im Graphen einen geraden Grad haben , und behauptete ohne Beweis, dass zusammenhängende Graphen mit ausschließlich Knoten geraden Grades einen Eulerkreis besitzen. Der erste vollständige Beweis dieser letzteren Behauptung wurde 1873 posthum von Carl Hierholzer veröffentlicht . ^{[ 1 ]} Dies ist als Eulerscher Satz bekannt.

Ein zusammenhängender Graph besitzt genau dann einen Euler-Zyklus, wenn jeder Knoten eine gerade Anzahl von inzidenten Kanten hat.

Der Begriff Eulergraph hat in der Graphentheorie zwei gängige Bedeutungen. Zum einen bezeichnet er einen Graphen mit einem Eulerkreis, zum anderen einen Graphen, bei dem jeder Knoten geraden Grades hat. Diese Definitionen stimmen für zusammenhängende Graphen überein. ^{[ 2 ]}

Für die Existenz von Eulerwegen ist es erforderlich, dass null oder zwei Knoten einen ungeraden Grad haben; dies bedeutet, dass der Königsberger Graph nicht eulersch ist. Gibt es keine Knoten mit ungeradem Grad, sind alle Eulerwege Kreise. Gibt es genau zwei Knoten mit ungeradem Grad, beginnen alle Eulerwege an einem dieser Knoten und enden am anderen. Ein Graph, der einen Eulerweg, aber keinen Eulerkreis besitzt, wird als semi-eulersch bezeichnet .

An Eulerian trail,^{[note 1]} or Euler walk, in an undirected graph is a walk that uses each edge exactly once. If such a walk exists, the graph is called traversable or semi-eulerian.^[3]

An Eulerian cycle,^{[note 1]} also called an Eulerian circuit or Euler tour, in an undirected graph is a circuit that uses each edge exactly once. If such a cycle exists, the graph is called Eulerian or unicursal.^[4] The term "Eulerian graph" is also sometimes used in a weaker sense to denote a graph where every vertex has even degree. For finite connected graphs the two definitions are equivalent, while a possibly unconnected graph is Eulerian in the weaker sense if and only if each connected component has an Eulerian cycle.

For directed graphs, "path" has to be replaced with directed path and "cycle" with directed cycle.

The definition and properties of Eulerian trails, cycles and graphs are valid for multigraphs as well.

An Eulerian orientation of an undirected graph G is an assignment of a direction to each edge of G such that, at each vertex v, the indegree of v equals the outdegree of v. Such an orientation exists for any undirected graph in which every vertex has even degree, and may be found by constructing an Euler tour in each connected component of G and then orienting the edges according to the tour.^[5] Every Eulerian orientation of a connected graph is a strong orientation, an orientation that makes the resulting directed graph strongly connected.

• An undirected graph has an Eulerian cycle if and only if every vertex has even degree, and all of its vertices with nonzero degree belong to a single connected component.^[6]
• An undirected graph can be decomposed into edge-disjoint cycles if and only if all of its vertices have even degree. So, a graph has an Eulerian cycle if and only if it can be decomposed into edge-disjoint cycles and its nonzero-degree vertices belong to a single connected component.
• Ein ungerichteter Graph besitzt genau dann einen Eulerweg, wenn genau null oder zwei Knoten einen ungeraden Grad haben und alle seine Knoten mit von Null verschiedenem Grad zu einer einzigen Zusammenhangskomponente gehören. ^{[ 6 ]}
• Ein gerichteter Graph besitzt genau dann einen Eulerkreis, wenn jeder Knoten den gleichen Eingangs- und Ausgangsgrad hat und alle seine Knoten mit Grad ungleich null zu einer einzigen starken Zusammenhangskomponente gehören . Äquivalent dazu besitzt ein gerichteter Graph genau dann einen Eulerkreis, wenn er in kantendisjunkte gerichtete Kreise zerlegt werden kann und alle seine Knoten mit Grad ungleich null zu einer einzigen starken Zusammenhangskomponente gehören. ^{[ 6 ]}
• Ein gerichteter Graph besitzt genau dann einen Eulerweg, wenn höchstens ein Knoten ( Ausgangsgrad ) − ( Eingangsgrad ) = 1 hat, höchstens ein Knoten (Eingangsgrad) − (Ausgangsgrad) = 1 hat, alle anderen Knoten gleichen Eingangs- und Ausgangsgrad besitzen und alle Knoten mit Grad ungleich null zu einer einzigen Zusammenhangskomponente des zugrunde liegenden ungerichteten Graphen gehören. ^{[ 6 ]}

Der Fleury-Algorithmus ist ein eleganter, aber ineffizienter Algorithmus aus dem Jahr 1883. ^{[ 7 ]} Gegeben sei ein Graph, dessen Kanten alle zur selben Komponente gehören und der höchstens zwei Knoten ungeraden Grades besitzt. Der Algorithmus beginnt an einem Knoten ungeraden Grades oder, falls der Graph keinen solchen Knoten besitzt, an einem beliebig gewählten Knoten. In jedem Schritt wird die nächste Kante auf dem Pfad so gewählt, dass der Graph durch deren Löschung nicht getrennt wird. Existiert keine solche Kante, wird die verbleibende Kante am aktuellen Knoten gewählt. Anschließend wird zum anderen Endpunkt dieser Kante gesprungen und die Kante gelöscht. Am Ende des Algorithmus sind keine Kanten mehr vorhanden. Die Folge der Kantenauswahl bildet einen Eulerkreis, falls der Graph keine Knoten ungeraden Grades besitzt, oder einen Eulerweg, falls genau zwei Knoten ungeraden Grades vorhanden sind.

Während die Traversierung des Graphen in Fleurys Algorithmus linear mit der Anzahl der Kanten skaliert, muss auch die Komplexität der Brückenerkennung berücksichtigt werden . Führt man Tarjans linearen Brückenfindungsalgorithmus ^{[ 8 ]} nach dem Entfernen jeder Kante erneut aus, ergibt sich für Fleurys Algorithmus eine Zeitkomplexität von O(n²) . Ein dynamischer Brückenfindungsalgorithmus von Thorup (2000) ermöglicht eine Verbesserung auf O(n²) , ist aber immer noch deutlich langsamer als alternative Algorithmen. ${\displaystyle O(|E|)}$${\displaystyle O(|E|^{2})}$${\displaystyle O(|E|\cdot \log ^{3}|E|\cdot \log \log |E|)}$

Hierholzers Arbeit aus dem Jahr 1873 bietet eine andere Methode zur Bestimmung von Euler-Zyklen, die effizienter ist als Fleurys Algorithmus:

• Wähle einen beliebigen Startknoten v und folge einer Kantenkette von diesem Knoten aus zurück zu v . Es ist nicht möglich, an einem anderen Knoten als v stecken zu bleiben , da der gerade Grad aller Knoten sicherstellt, dass beim Eintritt in einen anderen Knoten w eine ungenutzte Kante von w ausgeht . Die so erzeugte Tour ist eine geschlossene Tour, umfasst aber möglicherweise nicht alle Knoten und Kanten des ursprünglichen Graphen.
• Solange es einen Knoten u gibt , der zur aktuellen Tour gehört, aber angrenzende Kanten hat, die nicht Teil der Tour sind, beginne einen neuen Pfad von u aus , folge ungenutzten Kanten, bis du wieder bei u ankommst , und verbinde den so entstandenen Pfad mit der vorherigen Tour.
• Da wir davon ausgehen, dass der ursprüngliche Graph zusammenhängend ist , werden durch Wiederholung des vorherigen Schritts alle Kanten des Graphen erfasst.

Durch die Verwendung einer Datenstruktur wie einer doppelt verketteten Liste zur Verwaltung der Menge ungenutzter Kanten, die mit jedem Knoten verbunden sind, zur Verwaltung der Liste der Knoten der aktuellen Tour mit ungenutzten Kanten und zur Verwaltung der Tour selbst können die einzelnen Operationen des Algorithmus (Finden ungenutzter Kanten , die von jedem Knoten ausgehen, Finden eines neuen Startknotens für eine Tour und Verbinden zweier Touren, die einen gemeinsamen Knoten haben) jeweils in konstanter Zeit ausgeführt werden, sodass der Gesamtalgorithmus lineare Zeit benötigt . ^{[ 9 ]}${\displaystyle O(|E|)}$

Dieser Algorithmus lässt sich auch mit einer Deque implementieren . Da ein Blockieren nur dann möglich ist, wenn die Deque eine geschlossene Tour darstellt, rotiert man die Deque, indem man Kanten vom Ende entfernt und sie dem Anfang hinzufügt, bis man nicht mehr blockiert ist. Anschließend wiederholt man den Vorgang, bis alle Kanten berücksichtigt wurden. Auch dies benötigt lineare Zeit, da die Anzahl der Rotationen nie größer als n ist (intuitiv werden alle „schlechten“ Kanten an den Anfang verschoben, während neue Kanten dem Ende hinzugefügt werden). ${\displaystyle |E|}$

Die Anzahl der Eulerkreise in einem gerichteten Graphen lässt sich mithilfe des sogenannten BEST-Theorems berechnen , benannt nach de Bruijn , van Aardenne - Ehrenfest , Smith und Tutte . Die Formel besagt, dass die Anzahl der Eulerkreise in einem Digraphen das Produkt bestimmter Gradfakultäten und der Anzahl der Wurzelbäume ist . Letztere kann mithilfe des Matrixbaum-Theorems als Determinante berechnet werden, was einen polynomiellen Algorithmus ergibt.

Der Satz von BEST wurde erstmals in dieser Form in einer „Beweisnotiz“ der Arbeit von Aardenne-Ehrenfest und de Bruijn (1951) formuliert. Der ursprüngliche Beweis war bijektiv und verallgemeinerte die de-Bruijn-Folgen . Er stellt eine Variation eines früheren Ergebnisses von Smith und Tutte (1941) dar.

Die Anzahl der Eulerkreise in ungerichteten Graphen zu bestimmen , ist deutlich schwieriger. Dieses Problem ist bekanntermaßen #P-vollständig . ^{[ 10 ]} Positiv betrachtet liefert ein Markov-Chain-Monte-Carlo -Ansatz mittels der Kotzig-Transformationen (eingeführt von Anton Kotzig im Jahr 1968) vermutlich eine scharfe Näherung für die Anzahl der Eulerkreise in einem Graphen, obwohl es dafür bisher keinen Beweis gibt (selbst für Graphen mit beschränktem Grad).

Eine asymptotische Formel für die Anzahl der Eulerkreise in den vollständigen Graphen wurde von McKay und Robinson (1995) bestimmt : ^{[ 11 ]}

${\displaystyle \operatorname {ec} (K_{n})=2^{\frac {(n+1)}{2}}\pi ^{\frac {1}{2}}e^{{\frac {-n^{2}}{2}}+{\frac {11}{12}}}n^{\frac {(n-2)(n+1)}{2}}{\bigl (}1+O(n^{-{\frac {1}{2}}+\epsilon }){\bigr )}.}$

Eine ähnliche Formel wurde später von MI Isaev (2009) für vollständige bipartite Graphen erhalten : ^{[ 12 ].}

${\displaystyle \operatorname {ec} (K_{n,n})=\left({\frac {n}{2}}-1\right)!^{2n}2^{n^{2}-n+{\frac {1}{2}}}\pi ^{-n+{\frac {1}{2}}}n^{n-1}{\bigl (}1+O(n^{-{\frac {1}{2}}+\epsilon }){\bigr )}.}$

Eulerwege werden in der Bioinformatik verwendet , um die DNA-Sequenz aus ihren Fragmenten zu rekonstruieren. ^{[ 13 ]} Sie werden auch im CMOS -Schaltungsdesign eingesetzt, um eine optimale Anordnung von Logikgattern zu finden . ^{[ 14 ]} Es gibt einige Algorithmen zur Verarbeitung von Bäumen , die auf einer Euler-Tour des Baums basieren (wobei jede Kante als Paar von Bögen behandelt wird). ^{[ 15 ] [ 16 ]} De -Bruijn-Sequenzen lassen sich als Eulerwege von De-Bruijn-Graphen konstruieren . ^{[ 17 ]}

In einem unendlichen Graphen entspricht der Begriff „Eulerweg“ oder „Eulerkreis“ einer Eulergeraden, einem doppelt unendlichen Weg, der alle Kanten des Graphen abdeckt. Für die Existenz einer solchen Geraden ist es nicht hinreichend, dass der Graph zusammenhängend ist und alle Knotengrade gerade sind; beispielsweise besitzt der dargestellte unendliche Cayley-Graph mit Knotengraden von jeweils vier keine Eulergeraden. Die unendlichen Graphen, die Eulergeraden enthalten, wurden von Erdős, Grünwald & Weiszfeld (1936) charakterisiert . Damit ein unendlicher Graph oder Multigraph G eine Eulergeraden besitzt, müssen alle folgenden Bedingungen erfüllt sein: ^{[ 18 ] [ 19 ]}

• G ist verbunden.
• G besitzt abzählbare Mengen von Knoten und Kanten.
• G hat keine Knoten von (endlichem) ungeradem Grad.
• Entfernt man einen beliebigen endlichen Teilgraphen S aus G , so bleiben im verbleibenden Graphen höchstens zwei unendliche Zusammenhangskomponenten zurück. Hat S an jedem seiner Knoten einen geraden Grad, so bleibt nach dem Entfernen von S genau eine unendliche Zusammenhangskomponente übrig.

Euler gab als notwendige Bedingung für einen endlichen Graphen an, dass er eulersch ist: Alle Knoten müssen einen geraden Grad haben. Hierholzer bewies in einer 1873 veröffentlichten Arbeit, dass dies auch eine hinreichende Bedingung ist. Daraus ergibt sich die folgende notwendige und hinreichende Aussage darüber, was ein endlicher Graph erfüllen muss, um eulersch zu sein: Ein ungerichteter, zusammenhängender, endlicher Graph ist genau dann eulersch, wenn jeder Knoten von G einen geraden Grad hat. ^{[ 20 ]}

Das folgende Ergebnis wurde 1912 von Veblen bewiesen: Ein ungerichteter, zusammenhängender Graph ist genau dann eulersch, wenn er die disjunkte Vereinigung von Zyklen ist. ^{[ 20 ]}

Hierholzer entwickelte einen Algorithmus mit linearer Laufzeit zur Konstruktion einer Euler-Tour in einem ungerichteten Graphen.

Es ist möglich, einen gerichteten Graphen zu haben , dessen Ausgänge alle gerade sind, der aber nicht eulersch ist. Da ein Eulerkreis einen Knoten genauso oft verlässt, wie er ihn betritt, ist eine notwendige Bedingung für die Existenz eines Eulerkreises, dass Eingangs- und Ausgangsgrad an jedem Knoten gleich sind. Zusammenhang ist offensichtlich ebenfalls notwendig. König bewies, dass diese Bedingungen auch hinreichend sind. Das heißt, ein gerichteter Graph ist genau dann eulersch, wenn er zusammenhängend ist und Eingangs- und Ausgangsgrad an jedem Knoten gleich sind. ^{[ 20 ]}

In diesem Theorem spielt es keine Rolle, ob „zusammenhängend“ „schwach zusammenhängend“ oder „stark zusammenhängend“ bedeutet, da beides für Euler-Graphen äquivalent ist.

Hierholzers Algorithmus mit linearer Laufzeit zur Konstruktion einer Euler-Tour ist auch auf gerichtete Graphen anwendbar. ^{[ 20 ]}

Alle gemischten Graphen, die sowohl gerade als auch symmetrisch sind, sind garantiert eulersch. Dies ist jedoch keine notwendige Bedingung, da es möglich ist, einen nicht-symmetrischen, geraden Graphen zu konstruieren, der eulersch ist. ^{[ 20 ]}

Ford und Fulkerson bewiesen 1962 in ihrem Buch Flows in Networks ^{[ 21 ]} eine notwendige und hinreichende Bedingung dafür, dass ein Graph eulersch ist, nämlich dass jeder Knoten gerade sein und die Gleichgewichtsbedingung erfüllen muss, d. h. für jede Teilmenge von Knoten S muss die Differenz zwischen der Anzahl der Kanten, die von S ausgehen und in S hineinführen, kleiner oder gleich der Anzahl der Kanten sein, die mit S inzident sind. ^{[ 20 ]}

Die Überprüfung, ob ein gemischter Graph eulersch ist, ist schwieriger als die Überprüfung, ob ein ungerichteter oder gerichteter Graph eulersch ist, da die Bedingung der balancierten Menge jede mögliche Teilmenge von Knoten betrifft.

Ein Eulergraph ist ein Graph mit einem Eulerkreis. Jeder Eulergraph ist brückenlos . Das liegt daran, dass in einem Eulergraphen jede Kante Teil eines Eulerkreises ist. Wird eine Kante entfernt, bleiben ihre Endpunkte im restlichen Kreis verbunden. Umgekehrt gilt dies jedoch nicht.

Ein fast-eulerscher Graph ist ein Graph, der durch Hinzufügen einer einzigen Kante eulersch gemacht werden kann (äquivalent dazu: ein Graph, der einen Eulerweg enthält). Jeder fast-eulersche Graph ist fast brückenlos, das Umgekehrte gilt jedoch nicht.

Die Klassen der brückenlosen Graphen und der fast-eulerschen Graphen besitzen einen nichtleeren Schnitt (die eulerschen Graphen sind sowohl brückenlos als auch fast-eulersch), aber sie enthalten einander nicht. ^{[ 22 ] : Anhang B}

• Eulersche Matroide , eine abstrakte Verallgemeinerung von Euler-Graphen
• Fünf-Zimmer-Puzzle
• Das Handshake-Lemma , das Euler in seiner Originalarbeit bewies, zeigt, dass jeder ungerichtete, zusammenhängende Graph eine gerade Anzahl von Knoten mit ungeradem Grad besitzt.
• Hamiltonscher Pfad – ein Pfad, der jeden Knoten genau einmal besucht.
• Routeninspektionsproblem : Suche nach dem kürzesten Pfad, der alle Kanten besucht, gegebenenfalls auch Kanten wiederholen, falls kein Eulerweg existiert.
• Der Satz von Veblen besagt, dass Graphen mit geradem Knotengrad unabhängig von ihrer Konnektivität in kantendisjunkte Zyklen zerlegt werden können.

• Erdős, Pál ; Grünwald, Tibor ; Weiszfeld, Endre (1936), „Végtelen gráfok Euler vonalairól“ [Über Euler-Linien unendlicher Graphen] (PDF) , Mat. Fix. Lapok ( auf Ungarisch), 43 : 129–140. Übersetzt als Erdős, P. ; Grünwald, T. ; Vázsonyi, E. (1938), „Über Euler- Linien unendlicher Graphen “ (PDF) , J. Math. Physik. (auf Deutsch), 17 ( 1– 4): 59– 75, doi : 10.1002/sapm193817159Die
• Euler, L., „ Solutio problematis ad geometriam situs pertinentis “, Kommentar. Academiae Sci. I. Petropolitanae 8 (1736), 128–140.
• Hierholzer, Carl (1873), „Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren“ , Mathematische Annalen , 6 (1): 30–32 , doi : 10.1007/BF01442866 , S2CID  119885172Die
• Lucas, E., Récréations Mathématiques IV , Paris, 1921.
• Fleury, „Deux problemes de geometrie de situation“, Journal de mathematiques elementaires (1883), 257–261.
• T. van Aardenne-Ehrenfest und NG de Bruijn (1951) „Schaltungen und Bäume in orientierten linearen Graphen“, Simon Stevin 28: 203–217.
• Thorup, Mikkel (2000), „Nahezu optimale vollständig dynamische Graphkonnektivität“, Proc. 32nd ACM Symposium on Theory of Computing , S.  343–350 , doi : 10.1145/335305.335345 , S2CID  128282
• WT Tutte und CAB Smith (1941) „Über Unikursale Pfade in einem Netzwerk vom Grad 4“, American Mathematical Monthly 48: 233–237.

• Diskussion über frühe Erwähnungen von Fleurys Algorithmus .
• Euler-Tour in der Enzyklopädie der Mathematik .