2 Eulertouren Und Eulersche Graphen

Transcript

Westfählische Wilhelms-Universität Eulersche Graphen Autor: Jan-Hendrik Hoffeld 21. Mai 2015 Inhaltsverzeichnis 1 Das Königsberger Brückenproblem 1 2 Eulertouren und Eulersche Graphen 2 3 Auffinden eines eulerschen Zyklus 4 I Eulersche Graphen Jan-Hendrik Hoffeld 1 Das Königsberger Brückenproblem Abbildung 1: Die Brücken Königsbergs Im 18. Jahrhundert kam kaum ein Mathematiker, der sich in Königsberg wiederfand, darum herum sich zu fragen, ob es ihm gelänge, einen Weg durch die Stadt zu finden, sodass er jede Brücke genau einmal überquerte und dort endete, wo er gestartet war. 1736 nahm sich der schweizer Mathematiker Leonhard Euler, der zu der Zeit Professor der Mathematik in St. Petersburg war, des Problems an. Euler gelang es zu beweisen, dass ein solcher Rundweg nicht existiert. 1.1 Euler und das Königsberger Brückenproblem Bei der Suche nach einem Rundweg durch Königsberg, bei dem jede der sieben Brücken genau einmal überquert werden muss, schrieb Euler, dass eine Möglichkeit der Problemlösung sei, alle nur möglichen Wege durch Königsberg zu betrachten und zu überprüfen, ob einer den Ansprüchen genügt. Dieses Vorgehen sei jedoch zu aufwändig und nicht auf allgemeine Problemstellungen mit mehr Brücken anwendbar. Stattdessen wolle er erst eine Methode entwickeln, die ihm verrät, ob ein solcher Rundweg existiert.1 Um zu überprüfen, ob ein solcher Rundweg existiert, vereinfachte Euler zuerst die Darstellung der Lage der Brücken von Königsberg wie in Abb. 2 zu sehen. Mithilfe einer Buchstabensequenz, bestehend aus A,B,C und D ließ sich nun einfach ein Weg durch Königsberg beschreiben. 1 Norman L. Biggs, E. Keith Lloyd und Robin J. Wilson. Graph Theory 1736-1936. Oxford University Press, 1976. 1 Eulersche Graphen Jan-Hendrik Hoffeld Abbildung 2: Anordnung der Brücken von Königsberg Zum Beispiel beschrieb die Sequenz ADCABAC den Weg, der bei A startete, dann über eine Brücke zu D, dann zurück zu A usw. führte. Dieser Weg überquert sechs der sieben Brücken, die mit den Buchstabenpaaren AD, DC, CA, AB, BA und AC identifiziert werden können. Durch diese Schreibweise vereinfachte sich das Problem dahingehend, dass nur noch eine Sequenz von acht Buchstaben (da es sieben Brücken sind) gesucht werden musste, in denen die einzelnen Buchstaben entsprechend oft auftauchen. Bevor Euler jedoch eine solche Sequenz suchte, wollte er überprüfen, ob eine solche Sequenz zu finden sei.2 Euler argumentierte, dass D in der Sequenz genau zwei mal auftauchen müsse, da D mit drei Brücken verbunden ist. Würde D nur einmal in der Sequenz stehen, würden maximal zwei der drei Brücken überquert. Würde D dreimal in der Sequenz erscheinen, müsste D mit mindestens vier Brücken verbunden sein. Analog müssen auch C und B zweimal auftauchen und A dreimal. Insgesamt braucht die Sequenz daher neun Buchstaben. Dies ist allerdings nicht möglich, da nur sieben Brücken zur Verfügung stehen. Damit ist gezeigt, dass kein solcher Rundweg existiert. Durch diesen Überlegungen begründete Euler die Graphentheorie, auch wenn er noch keine Begriffe wie Knoten, Kanten oder Graphen verwendete. 2 Eulertouren und Eulersche Graphen Definition 1. Ein Weg W innerhalb eines zusammenhängenden Graphens G heißt Eulertour, wenn jede Kante von G in W liegt. Definition 2. Ein zusammenhängender Graph G heißt eulersch, wenn er eine geschlossene Eulertour enthält. Eine geschlossene Eulertour nennen wir Eulerschen Zyklus. 2 Biggs, Lloyd und Wilson, s. Anm. 1. 2 Eulersche Graphen Jan-Hendrik Hoffeld Satz 1. Für einen zusammenhängenden Graph G sind folgende Aussagen äquivalent: 1. G ist eulersch. 2. Jeder Knoten von G hat einen geraden Grad. 3. Die Kanten von G lassen sich disjunkt in Kreise zerlegen. Beweis. Der Satz wird mittels Kreisschluss bewiesen. 1.→ 2. Angenommen G enthält einen Eulerschen Zyklus C. Sei v ein beliebiger Knoten von G. Jedes Mal wenn C durch v läuft, muss C zwei Kanten durchlaufen, die inzident zu v sind. Wenn jede Kante, die inzident zu v ist, genau einmal von C durchlaufen werden muss, muss v einen geraden Grad haben. 2. → 3. Angenommen, jeder Knoten von G hat einen geraden Grad. Wir zeigen die Implikation durch Induktion über die Anzahl der Kreise in G. Da G zusammenhängend ist und keine Knoten vom Grad 1 hat, ist G kein Baum und besitzt somit mindestens einen Kreis. Hat G genau einen Kreis, so ist G ein Kreisgraph Cn für ein n und die Zerlegung besteht allein aus diesem Kreis. Angenommen, die Implikation gelte nun für Graphen, die nicht mehr als k Kreise beinhalten und G bestehe aus k + 1 Kreisen. Sei C ein beliebiger Kreis in G und sei G0 der Graph, der aus G hervorgeht, wenn die Kanten von C gelöscht werden. Durch das Löschen der Kanten von C verringert sich der Grad aller Knoten von C um 2. Daher hat jeder Knoten von G0 einen geraden Grad. Weiterhin hat jede zusammenhängende Komponente von G0 nicht mehr als k Kreise. Jede Komponente von G0 erfüllt nun die Induktionsannahme. Also lassen sich die Kanten von G0 disjunkt in Kreise zerlegen. Zusammen mit C liefert das die Zerlegung für G. 3. → 1. Angenommen, die Kanten von G lassen sich disjunkt in Kreise zerlegen. Wir nennen diese Kreise S1 , S2 , ..., Sk . Sei C der längste Zyklus in G, sodass die Menge der Kanten von C gerade E(C) = E(Sj1 ) ∪ E(Sj2 ) ∪ ... ∪ E(Sjm ) für einige Sj1 , Sj2 , ..., Sjm ist. Sei nun e eine Kante, die nicht in C liegt, aber inzident mit einem Knoten v von C ist, dann müssen e und v in einem Kreis Si für ein i liegen, der keine gemeinsame Kante mit C hat. Sei nun C 0 der Zyklus, der entsteht, wenn man C und Si in v verknüpft. Da C 0 aus den Kanten von C und von Si besteht, ist das ein Widerspruch dazu, dass C maximal ist. Daher enthält C bereits alle Kanten von G und ist somit ein Eulerscher Zyklus. Somit ist G eulersch. Korollar 1. Ein zusammenhängender Graph G enthält genau dann eine Eulertour, wenn keiner oder genau zwei seiner Knote einen ungeraden Grad haben. 3 Eulersche Graphen Jan-Hendrik Hoffeld Beweis. Haben alle Knoten von G einen geraden Grad, ist G ein eulerscher Graph und die Aussage folgt trivialer Weise aus Satz 1. Angenommen, genau zwei Knoten v1 und v2 von G haben einen ungeraden Grad. Sei G0 der Graph, der aus G hervorgeht, indem eine Kante e hinzugefügt wird, die v1 und v2 verbindet. Dann hat jeder Knoten von G0 einen geraden Grad und ist somit ein Eulerscher Graph. G0 enthält daher eine geschlossene Eulertour C. Der Weg, der entsteht wenn die Kante e aus C entfernt wird, ist dann eine Eulertour in G. 3 Auffinden eines eulerschen Zyklus Jetzt, da wir wissen, ob ein Graph G eulersch ist, gilt es einen Eulerschen Zyklus in G zu finden. Der Algorithmus von Hierholzer bietet einen einfachen Weg solch einen Zyklus ausfindig zu machen. 3.1 Algorithmus von Hierholzer Gegeben sei ein Eulerscher Graph G. 1. Finde einen Zyklus in G und nenne ihn R1 . Markiere seine Kanten. Sei i=1. 2. Falls Ri alle Kanten von G enthält, ist Ri schon ein eulerscher Zyklus. 3. Enthält Ri nicht alle Kanten von G, sei vi ein Knoten in Ri , der inzident mit einer nicht markierten Kante ei ist. 4. Finde einen Zyklus Qi , der nur aus nicht markierten Kanten besteht, sowie vi und ei enthält. Markiere die Kanten von Qi . 5. Erstelle einen neuen Zyklus Ri+1 , indem Ri und Qi in vi verknüpft werden. 6. Erhöhe i um 1 und fahre fort mit Schritt 2. Dass der Algorithmus von Hierholzer zu einem Eulerschen Zyklus führt, folgt direkt aus der Bedingung 3 von Satz 1. Definition 3. Sei G ein Graph und e ∈ E(G). Falls durch das Entfernen von e die Anzahl der Komponenten von G erhöht wird, so nennen wir e eine Brücke von G. 3.2 Algorithmus von Fleury Sei G ein zusammenhängender Eulerscher Graph, in dem alle Kanten unmarkiert sind. 1. Wähle einen Knoten und nenne ihn ”Hauptknoten” 4 Eulersche Graphen Jan-Hendrik Hoffeld Abbildung 3: Die Schritte des Algorithmus von Hierholz 2. Falls alle Kanten von G markiert sind, sind wir fertig. Andernfalls fahre fort mit Schritt 3. 3. Wähle von den unmarkierten Kanten, die inzident zum ”Hauptknoten” sind, wenn möglich eine, die keine Brücke des Untergraphens von G, der von den unmarkierten Kanten gebildet wird, ist. Ist das nicht möglich, wähle eine beliebige inzidente Kante des ”Hauptknotens”. Markiere die Kante und nenne den anderen inzidenten Knoten den neuen ”Hauptknoten”. 4. Fahre fort mit Schritt 2. Beweis. Um zu zeigen, dass der Algorithmus von Fleury tatsächlich einen Eulerschen Zyklus ausgibt, muss gefragt werden, wo der Algorithmus stecken bleiben könnte. Da jeder Knoten von G einen geraden Grad hat, können wir uns aus jedem Knoten wieder herausbewegen, es sei denn, es handelt sich um den Startknoten v. Angenommen der Algorithmus bleibt in v stecken. Die nicht markierten Kanten bilden zusammenhängende Komponenten, die alle eulersch sind, da alle Knoten einen geraden Grad besitzen. Angenommen, das letzte Mal, dass der Algorithmus den Knoten w, der Teil einer zusammenhängenden Komponente ist, durchlaufen hat, wurde w durch die Kante wv1 verlassen. Sei der Rest des Weges v1 v2 ...vk = v. Die Kante wv1 ist also eine Brücke in Feury’s 5 Eulersche Graphen Jan-Hendrik Hoffeld Algorithmus. Der Knoten w ist allerdings inzident zu mindestens zwei Kanten, die keine Brücken sind. Daher hätte der Algorithmus die Kante wv1 erst gar nicht ausgewählt. Im Gegensatz zum Algorithmus von Hierholzer lässt sich mit dem Algorithmus von Fleury auch eine Eulertour in solchen Graphen finden, die genau zwei Knoten mit ungeradem Grad haben. Hierzu wählt man einen dieser beiden Knoten als den ersten ”Hauptknoten” und verfährt wie oben. 6 Eulersche Graphen Literatur Jan-Hendrik Hoffeld Literatur Biggs, Norman L., E. Keith Lloyd und Robin J. Wilson. Graph Theory 1736-1936. Oxford University Press, 1976. Bollobás, Béla. Graph Theory - an introductory course. Bd. 63. Graduated Texts in Mathematics. Springer, 1979. Diestel, Reinhard. Graph Theory. 3. Edition. Bd. 173. Graduated Texts in Mathematics. Springer, 2005. Harris, John M., Jeffry L. Hirst und Michael J. Mossinghoff. Combinatorics and graph theory. 2. Edition. Undergraduate Texts in Mathematics. Springer, 2008. 7