Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 17/kontrolle
Schon in Beispiel 15.5 sind wir einer Situation begegnet, wo eine Kante in einem Graphen eine direkte Verbindung bedeutet, wo aber auch die passende Aneinanderreihung von Kanten eine naheliegende und sinnvolle Interpretation besitzt.
- Wege und Zusammenhang
Definition Definition 17.1 ändern
Ein Weg in einem Graphen ist eine Folge von Knoten derart, dass für alle eine Kante ist.
Statt Weg sagt man auch Kantenzug oder Pfad. heißt Anfangspunkt und heißt Endpunkt des Weges. Man sagt in dieser Situation auch, dass der angegebene Weg die Punkte und verbindet. Zu jedem Knotenpunkt gibt es den konstanten, kantenleeren Weg, der keine Kanten besitzt, und mit sich selbst verbindet. Bei einem Weg sind Wiederholungen erlaubt, und zwar sowohl von Punkten als auch von Kanten.
Gelegentlich wird ein Weg in der Form mit Kanten angeben, wobei dann vorauszusetzen ist, dass stets und koinzident sind und der Anfangspunkt eventuell explizit zu machen ist.
In einem Graphen ist die Verbundenheit zwischen Knotenpunkten
eine Äquivalenzrelation auf der Knotenmenge .
Jeder Knotenpunkt ist durch den leeren Kantenzug mit sich selbst verbunden. Dies sichert die Reflexivität. Wenn und durch den Kantenzug miteinander verbunden sind, so ist mit durch den umorientierten Kantenzug verbunden. Dies sichert die Symmetrie. Wenn mit durch den Kantenzug verbunden ist und mit durch den Kantenzug verbunden ist, so ist mit durch den zusammengesetzten Kantenzug verbunden. Dies sichert die Transitivität.
Die Zusammenhangskomponenten eines Graphen sind einfach die Äquivalenzklassen zur Äquivalenzrelation, miteinander verbunden zu sein. Ein isolierter Punkt eines Graphen ist dasselbe wie eine einpunktige Zusammenhangskomponente. Die verschiedenen Zusammenhangskomponenten eines Graphen haben nichts miteinander zu tun und daher studiert man vor allem zusammenhängende Graphen.
Es sei ein Graph und ein Blatt des Graphen.
Dann ist genau dann zusammenhängend, wenn zusammenhängend ist.
Es sei zusammenhängend und . Dann gibt es in einen verbindenden Weg von nach . Wenn in diesem Weg vorkommt, so jedenfalls nicht als Anfangs- oder als Endpunkt, da dies explizit ausgeschlossen ist. Wenn in der Mitte vorkommt, so in der Form , wobei die einzige Kante an bezeichne. Doch in diesem Fall kann man diesen Wegabschnitt herausnehmen und erhält einen kürzeren Weg von nach . Deshalb gibt es auch einen verbindenen Weg, wo gar nicht vorkommt.
Es sei nun zusammenhängend und seien . Wenn ist, so kann man direkt einen verbindenden Weg aus nehmen. Wenn ist, so ist mit einem weiteren Knotenpunkt verbunden, und einen Weg in von nach kann man durch die Kante zu einem Weg in von nach fortsetzverlämgern.
- Weglänge und Abstand
Dabei zählt man sich wiederholende Kanten mehrfach, d.h. der Weg hat die Länge , auch wenn in dem Weg die gleiche Kante mehrfach vorkommt.
Zu zwei Knotenpunkten und in einem zusammenhängenden Graphen versteht man unter dem Abstand die minimale Länge eines verbindenden Weges von nach .
In einem nicht zusammenhängenden Graphen setzt man manchmal den Abstand zwischen zwei Punkten, die zu verschiedenen Zusammenhangskomponenten gehören, als unendlich an.
Unter dem Durchmesser eines zusammenhängenden Graphen versteht man das Maximum über alle Abstände zu .
Unter dem Radius eines zusammenhängenden Graphen versteht man den Ausdruck
Der Durchmesser ist also das Maximum über alle Exzentrizitäten und der Radius ist das Minimum über alle Exzentrizitäten.
.png)
Wir betrachten das Metronetz von Lissabon. Es handelt sich um einen zusammenhängenden Graphen. Der durch die gelbe Linie beschriebene Weg hat die Länge . Der Abstand von São Sebastião zu Alameda ist , der kürzeste Weg ist über Sadanha (mit der roten Linie) gegeben. Es gibt natürlich auch deutlich längere Wege zwischen diesen beiden Stationen, beispielsweise über Marquês de Pompal mit der blauen Linie, dann nach Campo Grande mit der gelben Linie und dann mit der grünen Linie nach Alameda, der die Länge besitzt. Der Durchmesser des Netzgraphen ist , dieser wird im Abstand von Reboleira zu Aeroporto angenommen. Der Radius des Graphen ist , unz zwar haben sowohl Saldana als auch São Sebastião diese Exzentrizität. Die Exzentrizität von Cidada Universitária beträgt .
- Zyklen und Kreise
Den konstanten Weg und den einen Weg der Form betrachten wir als triviale Zyklen.
Mit der Formulierung ohne Wiederholungen meint man ohne Wiederholungen in der Knotenmenge, was insbesondere keine Wiederholungen in der Kantenmenge impliziert. Umgekehrt kann es aber Wege ohne Kantenwiederholungen geben, bei denen sich Knotenpunkte wiederholen, dies sind keine Kreise. Ein zyklischer Graph ist ein Graph mit zumindest einem Kreis.
.svg)
Die beiden folgenden Definition ergeben nur für zyklische Graphen Sinn.
Die Taille eines zyklischen Graphen ist die kürzeste Länge eines Kreises in .
Statt mit der kürzesten Länge eines Kreises kann man genauso gut mit der Länge eines nichttrivialen Zyklus arbeiten. Die Taille ist zumindest .
Der Umfang eines zyklischen Graphen ist die längste Länge eines Kreises in .
Hier kann man nicht mit beliebigen Zyklen arbeiten, da man diese ja mehrfach durchlaufen kann. Der Umfang ist durch die Knotenanzahl des Graphen beschränkt.
Das Blatt ist nur zu einem einzigen Knotenpunkt benachbart. Es kann in einem Zyklus nur in der Form vorkommen. In einem Kreis muss dann aber bereits das linke mit dem rechten als Punkt des Kreises übereinstimmen, was aber nach Definition auch kein Kreis ist, da er nur die Länge besitzt.
- Bäume und Wälder
Ein zusammenhängender Wald heißt Baum.
Wir betrachten die Menge aller Wege ohne Kantenwiederholungen. Da es in keine Kreise gibt, gibt es in einem solchen Weg auch keine Knotenwiederholung. Somit haben alle diese Wege eine (durch ) beschränkte Länge. Wir betrachten einen Weg, der unter diesen Wegen in maximale Länge besitzt. Dann sind die Endpunkte Blätter, da man andernfalls den Weg verlängern könnte.
Die Äquivalenz der Zusammenhangseigenschaft folgt aus Lemma 17.5. Ein Kreis in ist direkt ein Kreis in . Die Umkehrung folgt aus Lemma 17.17.
Es sei ein Graph mit nichtleerer Knotenmenge . Dann sind folgende Aussagen äquivalent.
- ist ein Baum.
- Zwischen je zwei Punkten gibt es einen eindeutigen Verbindungsweg ohne Wiederholung.
- ist zusammenhängend und es gilt .
Aus (1) folgt (2). Da nach Voraussetzung zusammenhängend ist, gibt es zu zumindest einen verbindenden Weg. Würde es zwei Wege geben, so könnte man daraus direkt einen Zyklus und dann auch einen Kreis konstruieren, was ausgeschlossen ist.
Aus (2) folgt (1). Die Zusammenhangseigenschaft ist klar. Würde es einen Kreis geben, so könnte man dies direkt als einen zweifachen Weg ohne Wiederholung zwischen zwei Punkten auffassen.
Aus (1) folgt (3). Wir führen Induktion über die Anzahl der Punkte von . Bei einem einzigen Punkt gibt es keine Kante und die Gleichung stimmt. Es sei also ein Baum mit Punkten. Nach Lemma 17.20 besitzt ein Blatt und nach Lemma 17.21 ist ebenfalls ein Baum. Dabei wird ein Punkt und eine Kante herausgenommen. Nach Induktionsvoraussetzung gilt die Gleichung für den verkleinerten Baum, also gilt sie auch für .
Von (3) nach (1). Wir führen wieder Induktion über die Knotenanzahl, bei einem Knoten ist alles klar. Aufgrund der Voraussetzung und Lemma 15.16 gilt
Wegen der Zusammenhangseigenschaft sind die Grade zumindest . Deshalb muss es (zumindest ) Punkte mit Grad , also Blätter geben. Es sei ein Blatt. Die Formel gilt dann auch für . Nach Induktionsvoraussetzung ist ein Baum, und daher ist nach Lemma 17.21 auch ein Baum.
