Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 17

Aus Wikiversity
Zur Navigation springen Zur Suche springen
So sah Vorli als Welpe aus.

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  

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.


Definition  

Ein Graph heißt zusammenhängend, wenn es zu je zwei Punkten einen Weg gibt, der und verbindet.



Lemma  

In einem Graphen ist die Verbundenheit zwischen Knotenpunkten

eine Äquivalenzrelation auf der Knotenmenge .

Beweis  

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.



Definition  

Zu einem Punkt in einem Graphen nennt man

die Zusammenhangskomponente von .

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.



Lemma  

Es sei ein Graph und ein Blatt des Graphen.

Dann ist genau dann zusammenhängend, wenn zusammenhängend ist.

Beweis  

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.

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

Definition  

Unter der Länge eines Weges in einem Graphen versteht man die Anzahl seiner Kanten.

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.


Definition  

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.


Definition  

Unter dem Durchmesser eines zusammenhängenden Graphen versteht man das Maximum über alle Abstände zu .


Definition  

Unter dem Radius eines zusammenhängenden Graphen versteht man den Ausdruck


Definition  

Zu einem Knotenpunkt eines zusammenhängenden Graphen nennt man

die Exzentrizität von .

Der Durchmesser ist also das Maximum über alle Exzentrizitäten und der Radius ist das Minimum über alle Exzentrizitäten.


Beispiel  

Metro Lisboa Route Map (only with routes in operation).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

Definition  

Ein Weg in einem Graphen heißt Zyklus, wenn ist.

Den konstanten Weg und den einen Weg der Form betrachten wir als triviale Zyklen.


Definition  

Ein Kreis in einem Graphen ist ein Zyklus der Länge ohne Wiederholungen.

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.

Die Circle line von London ist für sich genommen ein Rundgang.

Definition  

Ein Graph heißt Rundgang, wenn es in ihm einen Kreis gibt, der alle Knotenpunkte und alle Kanten genau einmal durchläuft.

Die beiden folgenden Definition ergeben nur für zyklische Graphen Sinn.


Definition  

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 .


Definition  

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.



Lemma  

Es sei ein Graph und ein Blatt des Graphen.

Dann ist in keinem Kreis von enthalten.

Beweis  

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

Definition  

Ein Graph ohne Kreis heißt Wald




Lemma  

Es sei ein Baum mit zumindest zwei Knotenpunkten.

Dann besitzt ein Blatt.

Beweis  

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.




Lemma  

Es sei ein Graph und ein Blatt des Graphen.

Dann ist genau dann ein Baum, wenn ebenfalls ein Baum ist.

Beweis  

Die Äquivalenz der Zusammenhangseigenschaft folgt aus Lemma 17.5. Ein Kreis in ist direkt ein Kreis in . Die Umkehrung folgt aus Lemma 17.17.




Satz  

Es sei ein Graph mit nichtleerer Knotenmenge . Dann sind folgende Aussagen äquivalent.

  1. ist ein Baum.
  2. Zwischen je zwei Punkten gibt es einen eindeutigen Verbindungsweg ohne Wiederholung.
  3. ist zusammenhängend und es gilt .

Beweis  

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. 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. 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.


Ein Kladogramm der Tetrapoden (Landwirbeltiere)



<< | Kurs:Diskrete Mathematik (Osnabrück 2020) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)