Ausarbeitung

Transcript

Bäume und Wälder Seminar: Graphentheorie Sommersemester 2015 Dozent: Dr. Thomas Timmermann Ida Feldmann 2-Fach Bachelor Mathematik und Biologie 6. Fachsemester Inhaltsverzeichnis Einleitung 1 1. Bäume und Wälder 2 2. Ausspannende Bäume von Graphen 6 3. Satz von Cayley 9 Literatur 12 Einleitung In dieser Ausarbeitung zum Seminarvortrag im Seminar “Graphentheorie“ geht es um Bäume und Wälder. Dabei beziehe ich mich auf Graph theory von Béla Bollobás, Combinatorics and graph theory von John M. Harris, Jeffry L. Hirst, Michael J. Mossinghoff und Proofs from The Book von Martin Aigner and Günter M. Ziegler. 1. Bäume und Wälder Im ersten Teil geht es um die Definition und elementare Eigenschaften eines Baumes und eines Waldes. 1.1 Definition: Ein Wald ist ein Graph ohne Kreise. Abbildung 1: Ein Beispiel für einen Wald. 1.2. Definition: Ein Baum ist ein zusammenhängender Graph ohne Kreise. Abbildung 2: Ein Beispiel für einen Baum. 1.3. Definition: Ein Blatt ist ein Knoten mit Grad 1. Ein Wald ist also eine disjunkte Vereinigung von Bäumen. Wir können auch sagen, dass ein Wald aus einem oder mehreren Bäumen besteht. Einen Baum können wir auch als zusammenhängenden Wald bezeichnen. In vielen Anwendungsbereichen gibt es Beispiele für Modellierungen durch Bäume. Hier folgen drei kurze Beispiele. 1. Bäume und Wälder 3 1.4. Anwendungen: • Bäume sind nützlich, um die möglichen Ergebnisse eines Experiments zu modellieren. Das Experiment, bei dem zuerst eine Münze geworfen und dann ein 6-seitiger Würfel gewürfelt wird, kann durch den folgenden Baum dargestellt werden. Abbildung 3: Ergebnisse eines Münz/Würfel Experiments. • Programmierer können Bäume benutzen, um die Logik von Algorithmen zu modellieren. Zum Beispiel kann die Logik eines Programmes, welches die größte von vier Zahlen (w, x, y, z) bestimmt, durch den folgenden Baum dargestellt werden. Abbildung 4: Logik eines Programms. • Im Bereich der Chemie beschreiben Bäume die Struktur der gesättigten Kohlenwasserstoffe. Dabei entsprechen die Knoten den Atomen und die Kanten den Bindungen. Abbildung 5: Einige gesättigte Kohlenwasserstoffe. 1. Bäume und Wälder 4 1.5. Satz: Ein Graph G = (V, E) ist ein Baum, wenn er zu jedem Paar verschiedener Knoten x, y ∈ V genau einen einfachen Weg von x nach y enthält. Beweis: Sei G ein Baum. Da G zusammenhängend ist, gibt es einen einfachen Weg von x nach y. Gibt es mindestens zwei Wege von x nach y, enthält G einen Kreis. Dies ist ein Widerspruch zur Annahme, dass G ein Baum ist.  1.6. Satz: Die folgenden Aussagen sind äquivalent für einen Graphen G: 1. G ist ein Baum. 2. G ist ein minimal zusammenhängender Graph. 3. G ist ein maximal kreisfreier Graph. Beweis: 1. ⇒2. Angenommen, G ist ein Baum. Sei {x, y} ∈ E(G). Der Graph G − {x, y} kann keinen einfachen Weg x, z1 , ..., zk , y enthalten, da G sonst den Kreis x, z1 , ..., zk , y, x enthält. Daher ist G − {x, y} unzusammenhängend und so ist G ein minimal zusammenhängender Graph. 1. ⇒3. Wenn x und y nicht adjazente Knoten von einem Baum G sind, enthält G den einfachen Weg x, z1 , ..., zk , y und G + {x, y} enthält den Kreis x, z1 , ..., zk , y, x. Also enthält G + {x, y} einen Kreis und deshalb ist G ein maximal kreisfreier Graph. 2. ⇒1. Angenommen, G ist ein minimal zusammenhängender Graph. Wenn G einen Kreis x, z1 , ..., zk , y, x enthält, dann ist G − {x, y} immer noch zusammenhängend. Da dies der Annahme, dass G minimal zusammenhängend sein soll, widerspricht, folgern wir, dass G kreisfrei ist. Also ist G ein Baum. 3. ⇒1. Angenommen, G ist ein maximal kreisfreier Graph. Wäre G nicht zusammenhängend, würden mindestens zwei Komponenten existieren. Würden x und y zu zwei verschiedenen Komponenten gehören, würde das Hinzufügen von {x, y} zu G keinen Kreis x, z1 , ..., zk , y, x in G ergeben, da sonst der einfache Weg x, z1 , ..., zk , y in G wäre. Also ist G zusammenhängend und auch ein Kreis.  1.7. Satz: Ein Baum T mit n Knoten hat n − 1 Kanten. Beweis: Wir beweisen den Satz mittels Induktion über die Anzahl der Knoten von T . Für n = 1 besteht der Baum aus nur einem Knoten und hat daher 0 Kanten. Angenommen, der Satz ist wahr für alle Bäume mit weniger als k Knoten. Sei T ein Baum mit k Knoten. Wir wählen eine Kante von T und nennen sie e. Da T ein Baum ist, das heißt ein minimal zusammenhängender Graph, ist T − e unzusammenhängend und besteht aus zwei Bäumen, T1 und T2 . Die Bäume T1 und T2 haben jweils k1 und k2 Knoten. Es gilt k1 + k2 = k und da k1 < k, gilt die Induktionsvoraussetzung für T1 . Deshalb hat T1 k1 − 1 Kanten. Ebenso hat T2 k2 −1 Kanten. Da die Kanten von T aus der disjunkten 1. Bäume und Wälder Vereinigung der Kanten von T1 , T2 und der Kante e bestehen, gilt: |E(T )| = |E(T1 )| + |E(T2 )| + |{e}| = (k1 − 1) + (k2 − 1) + 1 = k1 + k2 − 1 = k − 1 Dies vollendet die Induktion.  1.8. Satz: Ein Baum mit mindestens zwei Knoten enthält mindestens zwei Blätter. Beweis: Der Beweis erfolgt mittels Induktion über die Anzahl der Knoten. Die Aussage ist wahr, falls n = 2, da in einem Baum, der aus zwei Knoten besteht, beide Knoten auch Blätter sind. Angenommen, der Satz gilt für alle Bäume mit 2 bis n − 1 Knoten. Sei T ein Baum mit n ≥ 3 Knoten. Aus Satz 1.7. wissen wir, dass T n − 1 Kanten hat, und da wir n ≥ 3 annehmen, hat T mindestens zwei Kanten. Wenn jede Kante von T mit einem Blatt verbunden ist, hat T mindestens zwei Blätter und der Beweis ist vollständig. Sonst gibt es eine Kante e = {u, v} von T , die nicht mit einem Blatt verbunden ist. Der Graph T −e enthält die beiden Bäume T1 und T2 mit jeweils n1 und n2 Knoten. Es sei ohne Beschränkung der Allgemeinheit u ∈ V (T1 ) und v ∈ V (T2 ). Da e nicht mit Blättern von T verbunden ist, ist n1 ≥ 2 und n2 ≥ 2. Deshalb ist die Induktionsvoraussetzung anwendbar auf T1 und T2 . Somit haben T1 und T2 je zwei Blätter. Das heißt, dass T1 und T2 jeweils mindestens ein Blatt haben, das nicht mit der Kante e verbunden ist. Deshalb hat der Graph (T − e) + e = T mindestens zwei Blätter.  5 2. Ausspannende Bäume von Graphen In dem zweiten Teil geht es um besondere Untergraphen, um aufspannende Bäume von Graphen. 2.1 Definition: Ein Untergraph T ist ein aufspannender Baum von einem Graphen G, wenn T ein Baum ist, der jeden Knoten von G enthält. Abbildung 6: Ein aufspannender Baum (markiert) von einem Graphen. 2.2 Satz: Jeder zusammenhängende Graph enthält einen aufspannenden Baum. Beweis: Sei G ein Graph mit n Knoten. Wir wählen x ∈ V (G). Sei T1 der Untergraph von G, der nur aus x besteht. Dann ist T1 ein Baum. Wir konstruieren die Bäume T1 ⊂ T2 ⊂ ... ⊂ Tk ⊂ G, wobei Ti i Knoten hat. Wenn k < n, dann gibt es einen Knoten y ∈ V (G) − V (Tk ), der in G adjazent ist zu einem Knoten z ∈ Tk . Sei Tk+1 der Baum, der aus Tk durch Hinzufügen des Knotens y und der Kante {y, z} entsteht. Dann ist Tk+1 zusammenhängend und, da {y, z} nicht die Kante eines Kreises in Tk+1 sein kann, auch kreisfrei. Daher ist Tk+1 auch ein Baum und die Folge T0 ⊂ T1 ⊂ ... kann bis Tn vollendet werden. Der Baum Tn enthält dann alle Knoten von G und ist ein aufspannender Baum von G.  2.3 Anwendung: Minimierung von Verbindungskosten Eine verbreitete Anwendung eines aufspannenden Baums von einem Graphen ist die Minimierung von Verbindungskosten. In dem folgenden Beispiel soll zwischen verschiedenen Städten in einem Gebiet ein Zugschienennetz verlegt werden. Einige dieser Städte sind bereits durch Straßen verbunden und die Schienen sollen neben den Straßen verlaufen. Da das Gebiet gebirgig ist, sind manche Straßen steil und kurvenreich, dort wäre das Verlegen der Schienen schwierig und teuer. Die Straßen werden bewertet entsprechend ihrer Länge, Steigung und Kurvigkeit. Dabei entspricht ein hoher Wert hohen Kosten. Ein Beispiel für einen solchen Graphen ist in der Abbildung 8 zu sehen. 2. Ausspannende Bäume von Graphen 7 Abbildung 7: Beispiel für einen Städte-Graphen. Das Ziel ist, dass jede Stadt von jeder anderen Stadt aus mit dem Zug erreichbar ist (aber nicht umbedingt direkt erreichbar). Da die Kosten minimiert werden sollen, wird die beste Lösung keinen Kreis von Schienen enthalten, da in einem Kreis mindestens entlang einer Strecke unnötigerweise Schienen verlegt werden. Um dieses Problem auf ein Problem der Graphentheorie zurückzuführen, sollen bei einem Graphen die Knoten den Städten entsprechen und die Kanten den Straßen dazwischen. Die Bewertung der Straßen kann durch eine Gewichtungsfunktion, die jeder Kante eine positive reelle Zahl zuordnet, umgesetzt werden. Dies motiviert die folgenden Definitionen. 2.4 Definition: Ein gewichteter Graph G = (V, E, w) wird durch einen Graphen (V, E) und eine Gewichtungsfunktion w : E → R+ gegeben. 2.5 Definition: Ein aufspannender Baum T = (V, E 0 ) von einem Graphen G = (V, E, w) heißt minimal, wenn w(T ) = X w({x, y}) {x,y}∈E 0 minimal ist. Das heißt, w(T ) ≤ w(T 0 ) für jeden aufspannenden Baum T 0 von G. Es gibt verschiedene Möglichkeiten, einen solchen minimal aufspannenden Baum zu finden. Eine Methode heißt Kruskals Algorithmus. 2.6 Kruskals Algorithmus: Gegeben ist ein zusammenhängender, gewichteter Graph G. 1. Finde eine Kante mit minimalem Gewicht und markiere sie. 2. Wähle aus den unmarkierten Kanten, die keinen Kreis mit einer der markierten Kanten bilden, eine Kante mit minimalem Gewicht und markiere diese. 3. Wenn die Menge der markierten Kanten einen aufspannenden Baum von G bildet, dann stoppe. Wenn nicht, dann wiederhole Schritt 2. 2. Ausspannende Bäume von Graphen 8 Wenn wir Kruskals Algorithmus auf den Graphen in Abbildung 7 anwenden, erhalten wir beispielsweise den folgenden minimal aufspannenden Baum, der in der Abbildung 8 markiert ist. Abbildung 8: Kruskals Algorithmus angewendet auf den Städte-Graphen aus Abbildung 7. 2.7 Satz: Kruskals Algorithmus produziert einen minimalen aufspannenden Baum von einem zusammenhängenden, gewichteten Graphen G. Beweis: Sei G ein zusammenhängender, gewichteter Graph mit n Knoten und sei T ein aufspannender Baum, der durch die Anwendung von Kruskals Algorithmus entstanden ist. Kruskals Algorithmus bildet einen aufspannenden Baum, indem nacheinander immer eine Kante hinzugefügt wird. Angenommen die Kanten, die T (in der folgenden Reihenfolge) hinzugefügt wurden, heißen e1 , e2 , ..., en−1 . Dann angenommen, dass T kein minimal aufspannender Baum von G ist. Unter allen minimal aufspannenden Bäumen wählen wir T 0 , welcher am längsten (das heißt für die meisten Anfangsschritte des Algorithmus) mit T übereinstimmt. Das bedeutet, dass ein k existiert, so dass T 0 e1 , ..., ek enthält und kein minimal aufspannender Baum alle e1 , ..., ek , ek+1 enthält. (Da T laut der Annahme nicht minimal ist, ist k < n − 1.) Da T 0 ein aufspannender Baum ist, muss T 0 + ek+1 einen Kreis K enthalten. Da T keine Kreise enthält, muss K eine Kante e0 enthalten, die nicht in T ist. Durch Entfernen der Kante e0 von T 0 + ek+1 wird der Kreis K unterbrochen und es bleibt ein aufspannender Baum von G. Deshalb ist T 0 + ek+1 − e0 ein aufspannender Baum von G und enthält die Kanten e1 , ..., ek , ek+1 . Da die Kante e0 verfügbar gewesen sein muss, als ek+1 vom Algorithmus ausgewählt wurde, muss w(ek+1 ) ≤ w(e0 ) gelten. Das heißt, dass T 0 + ek+1 − e0 ein aufspannender Baum ist, dessen Gewicht nicht mehr ist als das von T 0 , welcher die Kanten e1 , ..., ek+1 enthält, was der Annahme widerspricht.  3. Satz von Cayley In diesem Teil geht es um den Satz von Cayley. Dieser betrifft die Anzahl bezeichneter Bäume. Dafür betrachten wir die feste Knotenmenge {1, 2, ..., n}. Dann steht Tn für die Anzahl der bezeichneten Bäume auf dieser Menge. Für T1 , T2 , T3 , und T4 ergeben sich die folgenden Bäume. Abbildung 9: Bezeichnete Bäume auf 1, 2, 3 und 4 Knoten. Bei vier Knoten existieren vier nicht isomorphe Baumtypen, mit jeweils vier Möglichkeiten, die Knoten anzuordnen, also ist T4 = 16. Allgemein gilt der folgende Satz. 3.1 Satz von Cayley: Es gibt nn−2 bezeichnete Bäume auf n Ecken. Beweis: Der Satz wurde auf verschiedene Weisen bewiesen. In dem folgenden Beweis wird für die Lösung des Problems eine Rekursion gefunden und aus dieser dann die explizite Formel durch Induktion abgeleitet. Um die richtige Rekursion zu finden, betrachten wir ein etwas allgemeineres Problem. Sei A eine beliebige k-elementige Knotenmenge. Tn,k steht für die Anzahl der bezeichneten Wälder auf der Knotenmenge {1, ..., n}, die in A verwurzelt sind. Das heißt, die Wälder bestehen aus k Bäumen und jeder Baum muss genau einen Knoten aus A enthalten. Dabei ist die Menge A für die die Anzahl Tn,k nicht wichtig, sondern nur ihre Größe k. Als Beispiel betrachten wir T4,2 = 8 für A = {1, 2}. Abbildung 10: Beispiel: T4 , 2 = 8 für A = {1, 2} 3. Satz von Cayley 10 Sei also ein Wald F gegeben, der in A = {1, ..., k} verwurzelt ist. Dann gibt es Tn,k solche Bäume. Angenommen, der Knoten 1 hat genau i Nachbarn. Abbildung 11: Angedeutet: Wald F , der in {1, .., k} verwurzelt ist. Durch das Entfernen des Knotens 1 entsteht F 0 auf {2, ..., n}, der in {2, ..., n} ∪{die Nachbarn von 1} verwurzelt ist. Denn durch das Entfernen von Knoten 1 werden die i Nachbarn der Menge A hinzugefügt und damit ändert sich die Größe der Menge A von k zu k − 1 + i. Es gibt Tn−1,k−1+i solche Wälder. Umgekehrt können wir den Wald F konstruieren, indem wir erst i festlegen (0 ≤ i ≤ n − k) Dann wählen wir die i Nachbarn von Knoten 1 in {k + 1, ..., n}
aus. Dafür gibt es n−k Möglichkeiten. Dann wird der Wald F 0 bestimmt. i Damit wurde gezeigt, dass für 1 ≤ k ≤ n die Rekursion Tn,k = n−k X i=0 ! n−k Tn−1,k−1+i i (1) erfüllt ist, wenn T0,0 := 1 und Tn,0 := 0 für n > 0 gesetzt werden, um Tn,n = 1 sicherzustellen. Proposition: Es gilt Tn,k = knn−k−1 , (2) und insbesondere Tn,1 = Tn = nn−2 . Beweis: Wir beweisen die Proposition mittels Induktion, unter Verwendung von (1) und des Binomischen Lehrsatzes. Induktionsanfang: n = 1: T1,0 = 0 T1,1 = 1 = 1 ∗ 1−1 Induktionsvoraussetzung: (2) gilt für n − 1. 3. Satz von Cayley 11 Induktionsschritt: Tn,k = = = n−k X i=0 n−k X i=0 0 X i=n−k = = n−k X i=0 n−k X i=0 ! n−k Tn−1,k−1+i i ! n−k (k − 1 + i)(n − 1)n−1−k−i i ! n−k (n − 1 − i)(n − 1)i−1 |i → n − k − i n−k−i n−k X n−k n−k (n − 1)i − i(n − 1)i−1 i i i=0 ! ! n−k X n−k (n − k)! (n − 1)1n−k−1 − i(n − 1)i−1 i i!(n − k − i)! i=1 ! = (n − 1 + 1)n−k − (n − k) n−k X i=1 =n n−k =n n−k =n n−k − (n − k) − (n − k) n−k X ! n−k−1 (n − 1)i−1 i−1 i=1 n−k−1 X i=0 (n − k − 1)! (n − 1)i−1 (i − 1)!(n − k − i)! ! n−k−1 (n − 1)i 1n−k−1−i |i → i + 1 i − (n − k)(n − 1 + 1)n−k−1 = knn−k−1  Literatur [1] Martin Aigner and Günter M. Ziegler. Proofs from The Book. Springer-Verlag, Berlin, fourth edition, 2010. [2] Béla Bollobás. Graph theory, volume 63 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1979. An introductory course. [3] John M. Harris, Jeffry L. Hirst, and Michael J. Mossinghoff. Combinatorics and graph theory. Undergraduate Texts in Mathematics. Springer, New York, second edition, 2008.