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

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 $v_1,v_2,\dots ,v_m$ von Knoten derart, dass $v_i{v}_{i+1}$ für alle $i$ eine Kante ist.

Statt Weg sagt man auch Kantenzug oder Pfad. $v_1$ heißt Anfangspunkt und $v_m$ heißt Endpunkt des Weges. Man sagt in dieser Situation auch, dass der angegebene Weg die Punkte $v_1$ und $v_m$ verbindet. Zu jedem Knotenpunkt $v$ gibt es den konstanten, kantenleeren Weg, der keine Kanten besitzt, und $v$ 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 $e_1,\dots ,e_{m-1}$ mit Kanten  $e_i\in E$  angegeben, wobei dann vorauszusetzen ist, dass die Kanten $e_i$ und $e_{i+1}$ stets koinzident sind und der Anfangspunkt eventuell explizit zu machen ist.

Definition

Ein Graph $(V,E)$ heißt zusammenhängend, wenn es zu je zwei Punkten  $u,v\in V$  einen Weg gibt, der $u$ und $v$ verbindet.

Lemma

In einem Graphen  $G=(V,E)$  ist die Verbundenheit zwischen Knotenpunkten

eine Äquivalenzrelation auf der Knotenmenge $V$.

Beweis

Jeder Knotenpunkt ist durch den leeren Kantenzug mit sich selbst verbunden. Dies sichert die Reflexivität. Wenn $u$ und $v$ durch den Kantenzug $u=v_1,v_2,\dots ,v_{r-1},v_r=v$ miteinander verbunden sind, so ist $v$ mit $u$ durch den umorientierten Kantenzug $v_r,v_{r-1},\dots ,v_2,v_1$ verbunden. Dies sichert die Symmetrie. Wenn $u$ mit $v$ durch den Kantenzug $u=v_1,v_2,\dots ,v_r=v$ verbunden ist und $v$ mit $w$ durch den Kantenzug $v=w_1,w_2,\dots ,w_s=w$ verbunden ist, so ist $u$ mit $w$ durch den zusammengesetzten Kantenzug $u=v_1,v_2,\dots ,v_r=v=w_1,w_2,\dots ,w_s=w$ verbunden. Dies sichert die Transitivität.

$◻$

Definition

Zu einem Punkt  $v\in V$  in einem Graphen nennt man

$Z(v)=\{u\in V\mid \text{es gibt einen Weg, der }u\text{ und }v\text{ verbindet}\}$

die Zusammenhangskomponente von $v$.

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  $G=(V,E)$  ein Graph und  $b\in V$  ein Blatt des Graphen.

Dann ist $G$ genau dann zusammenhängend, wenn $G\setminus b$ zusammenhängend ist.

Beweis

Es sei $G$ zusammenhängend und  $u,v\in G\setminus \{b\}$.  Dann gibt es in $G$ einen verbindenden Weg von $u$ nach $v$. Wenn in diesem Weg $b$ vorkommt, so jedenfalls nicht als Anfangs- oder als Endpunkt, da dies explizit ausgeschlossen ist. Wenn $b$ in der Mitte vorkommt, so in der Form $w,b,w$, wobei $\{b,w\}$ die einzige Kante an $b$ bezeichne. Doch in diesem Fall kann man diesen Wegabschnitt herausnehmen und erhält einen kürzeren Weg von $u$ nach $v$. Deshalb gibt es auch einen verbindenden Weg, in dem $b$ gar nicht vorkommt.

Es sei nun $G\setminus \{b\}$ zusammenhängend und seien  $u,v\in G$.  Wenn  $u,v\ne b$  ist, so kann man direkt einen verbindenden Weg aus $G\setminus \{b\}$ nehmen. Wenn  $u=b$  ist, so ist $b$ mit einem weiteren Knotenpunkt $w$ verbunden, und einen Weg in $G\setminus \{b\}$ von $w$ nach $v$ kann man durch die Kante $\{b,w\}$ zu einem Weg in $G$ von $b$ nach $v$ verlängern.

$◻$

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 $v_1,\dots ,v_m$ hat die Länge $m-1$, auch wenn in dem Weg die gleiche Kante mehrfach vorkommt.

Definition

Zu zwei Knotenpunkten $u$ und $v$ in einem zusammenhängenden Graphen versteht man unter dem Abstand $d(u,v)$ die minimale Länge eines verbindenden Weges von $u$ nach $v$.

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  $G=(V,E)$  versteht man das Maximum über alle Abstände $d(u,v)$ zu  $u,v\in V$. 

Definition

Unter dem Radius eines zusammenhängenden Graphen  $G=(V,E)$  versteht man

$\min (\max (d(u,v)|u\in V)|v\in V).$

Definition

Zu einem Knotenpunkt  $v\in V$  eines zusammenhängenden Graphen  $G=(V,E)$  nennt man

$e(v)=\max (d(u,v)|u\in V)$

die Exzentrizität von $v$.

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

Beispiel

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 $12$. Der Abstand von São Sebastião zu Alameda ist $2$, der kürzeste Weg ist über Saldanha (mit der roten Linie) gegeben. Es gibt natürlich auch deutlich längere Wege zwischen diesen beiden Stationen, beispielsweise über Marquês de Pombal 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 $12$ besitzt. Der Durchmesser des Netzgraphen ist $21$, dieser wird im Abstand von Reboleira zu Aeroporto angenommen. Der Radius des Graphen ist $11$, und zwar haben sowohl Saldanha als auch São Sebastião diese Exzentrizität. Die Exzentrizität von Cidade Universitária beträgt $14$.

Zyklen und Kreise

Definition

Ein Weg $v_1,\dots ,v_m$ in einem Graphen $(V,E)$ heißt Zyklus, wenn  $v_1=v_m$  ist.

Den konstanten Weg und einen Weg der Form $u,v,u$ betrachten wir als triviale Zyklen.

Definition

Ein Kreis in einem Graphen ist ein Zyklus der Länge $\ge 3$ ohne Wiederholungen.

Mit der Formulierung ohne Wiederholungen meint man ohne Wiederholungen in der Knotenmenge mit Ausnahme der Endpunkte. Dies schließt insbesondere Wiederholungen in der Kantenmenge aus. 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. Andernfalls nennt man ihn zyklenfrei.

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

Definition

Ein Graph $G$ heißt Rundgang, wenn es in ihm einen Kreis $v_1,v_2,\dots ,v_m=v_1$ gibt, der alle Knotenpunkte und alle Kanten genau einmal durchläuft.

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

Definition

Die Taille eines zyklischen Graphen $G$ ist die kürzeste Länge eines Kreises in $G$.

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

Definition

Der Umfang eines zyklischen Graphen $G$ ist die längste Länge eines Kreises in $G$.

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  $G=(V,E)$  ein Graph und  $b\in V$  ein Blatt des Graphen.

Dann ist $b$ in keinem Kreis von $G$ enthalten.

Beweis

Das Blatt $b$ ist nur zu einem einzigen Knotenpunkt $c$ benachbart. Es kann in einem Zyklus nur in der Form $\mathrm{...}-c-b-c-\mathrm{...}$ vorkommen. In einem Kreis muss dann aber bereits das linke mit dem rechten $c$ als Punkt des Kreises übereinstimmen, was aber nach Definition auch kein Kreis ist, da er nur die Länge $2$ besitzt.

$◻$

Bäume und Wälder

Definition

Ein Graph ohne Kreis heißt Wald.

Definition

Ein zusammenhängender Wald heißt Baum.

Lemma

Es sei $G$ ein Baum mit zumindest zwei Knotenpunkten.

Dann besitzt $G$ ein Blatt.

Beweis

Wir betrachten die Menge aller Wege ohne Kantenwiederholungen. Da es in $G$ keine Kreise gibt, gibt es in einem solchen Weg auch keine Knotenwiederholung. Somit haben alle diese Wege eine (durch $\mathrm{\#}\left(V\right)$) beschränkte Länge. Wir betrachten einen Weg, der unter diesen Wegen in $G$ maximale Länge besitzt. Dann sind die Endpunkte Blätter, da man andernfalls den Weg verlängern könnte.

$◻$

Lemma

Es sei  $G=(V,E)$  ein Graph und  $b\in V$  ein Blatt des Graphen.

Dann ist $G$ genau dann ein Baum, wenn $G\setminus b$ ebenfalls ein Baum ist.

Beweis

Die Äquivalenz der Zusammenhangseigenschaft folgt aus Lemma 17.5. Ein Kreis in $G\setminus b$ ist direkt ein Kreis in $G$. Die Umkehrung folgt aus Lemma 17.17.

$◻$

Satz

Es sei  $G=(V,E)$  ein Graph mit nichtleerer Knotenmenge $V$. Dann sind folgende Aussagen äquivalent.

1. $G$ ist ein Baum.
2. Zwischen je zwei Punkten  $u,v\in V$  gibt es einen eindeutigen Verbindungsweg ohne Wiederholung.
3. $G$ ist zusammenhängend und es gilt  $\mathrm{\#}\left(E\right)=\mathrm{\#}\left(V\right)-1$. 

Beweis

Aus (1) folgt (2). Da $G$ nach Voraussetzung zusammenhängend ist, gibt es zu $u,v$ 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 $G$. Bei einem einzigen Punkt gibt es keine Kante und die Gleichung stimmt. Es sei also $G$ ein Baum mit  $n\ge 2$  Punkten. Nach Lemma 17.20 besitzt $G$ ein Blatt und nach Lemma 17.21 ist $G\setminus b$ 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 $G$.

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

$\sum _{v\in V}d(v)=2\cdot (\mathrm{\#}\left(V\right)-1)=2\mathrm{\#}\left(V\right)-2.$

Wegen der Zusammenhangseigenschaft sind die Grade zumindest $1$. Deshalb muss es (zumindest $2$) Punkte mit Grad $1$, also Blätter geben. Es sei $b$ ein Blatt. Die Formel gilt dann auch für $G\setminus b$. Nach Induktionsvoraussetzung ist $G\setminus b$ ein Baum, und daher ist nach Lemma 17.21 auch $G$ ein Baum.

$◻$

Ein Kladogramm der Tetrapoden (Landwirbeltiere)

<< | Kurs:Diskrete Mathematik (Osnabrück 2020) | >> PDF-Version dieser Vorlesung Arbeitsblatt zur Vorlesung (PDF)