Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 17/latex
\setcounter{section}{17}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Dsc 7112-large.jpg} }
\end{center}
\bildtext {So sah Vorli als Welpe aus.} }
\bildlizenz { Dsc 7112-large.jpg } {} {Odatrulle} {Commons} {CC-by-sa 4.0} {}
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.
\zwischenueberschrift{Wege und Zusammenhang}
\inputdefinition
{}
{
Ein
\definitionswort {Weg}{}
in einem
\definitionsverweis {Graphen}{}{}
ist eine Folge
\mathl{v_1,v_2 , \ldots , v_m}{} von Knoten derart, dass
\mathl{v_iv_{i+1}}{} für alle $i$ eine Kante ist.
}
Statt Weg sagt man auch \stichwort {Kantenzug} {} oder \stichwort {Pfad} {.} $v_1$ heißt \stichwort {Anfangspunkt} {} und $v_m$ heißt \stichwort {Endpunkt} {} des Weges. Man sagt in dieser Situation auch, dass der angegebene Weg die Punkte \mathkor {} {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
\mathl{e_1 , \ldots , e_{m-1}}{} mit Kanten
\mavergleichskette
{\vergleichskette
{e_i
}
{ \in }{E
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
angeben, wobei dann vorauszusetzen ist, dass stets
\mathkor {} {e_i} {und} {e_{i+1}} {}
\definitionsverweis {koinzident}{}{}
sind und der Anfangspunkt eventuell explizit zu machen ist.
\inputdefinition
{}
{
Ein
\definitionsverweis {Graph}{}{}
\mathl{(V,E)}{} heißt
\definitionswort {zusammenhängend}{,}
wenn es zu je zwei Punkten
\mavergleichskette
{\vergleichskette
{u,v
}
{ \in }{ G
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
einen
\definitionsverweis {Weg}{}{}
gibt, der
\mathkor {} {u} {und} {v} {}
verbindet.
}
\inputfaktbeweis
{Ungerichteter Graph/Verbunden/Äquivalenzrelation/Fakt}
{Lemma}
{}
{
\faktsituation {In einem
\definitionsverweis {Graphen}{}{}
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist die
\definitionsverweis {Verbundenheit}{}{}
zwischen Knotenpunkten}
\faktfolgerung {eine
\definitionsverweis {Äquivalenzrelation}{}{}
auf der Knotenmenge $V$.}
\faktzusatz {}
\faktzusatz {}
}
{
Jeder Knotenpunkt ist durch den leeren Kantenzug mit sich selbst verbunden. Dies sichert die Reflexivität. Wenn
\mathkor {} {u} {und} {v} {}
durch den Kantenzug
\mathl{u=v_1,v_2 , \ldots , v_{r-1}, v_r=v}{} miteinander verbunden sind, so ist $v$ mit $u$ durch den umorientierten Kantenzug
\mathl{v_r,v_{r-1} , \ldots , v_2,v_1}{} verbunden. Dies sichert die Symmetrie.
Wenn $u$ mit $v$ durch den Kantenzug
\mathl{u=v_1,v_2 , \ldots , v_r=v}{} verbunden ist und $v$ mit $w$ durch den Kantenzug
\mathl{v=w_1,w_2 , \ldots , w_s=w}{} verbunden ist, so ist $v$ mit $w$ durch den zusammengesetzten Kantenzug
\mathl{u=v_1,v_2 , \ldots , v_r=v=w_1 ,w_2 , \ldots , w_s=w}{} verbunden. Dies sichert die Transitivität.
\inputdefinition
{}
{
Zu einem Punkt
\mavergleichskette
{\vergleichskette
{v
}
{ \in }{V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
in einem
\definitionsverweis {Graphen}{}{}
nennt man
\mavergleichskettedisp
{\vergleichskette
{Z(v)
}
{ =} { { \left\{ u \in V \mid \text{es gibt einen Weg, der } u \text{ und } v \text{ verbindet } \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
die
\definitionswort {Zusammenhangskomponente}{}
von $v$.
}
Die Zusammenhangskomponenten eines Graphen sind einfach die \definitionsverweis {Ä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.
\inputfaktbeweis
{Ungerichteter Graph/Blatt/Hinwegnahme/Zusammenhang/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {Graph}{}{}
und
\mavergleichskette
{\vergleichskette
{b
}
{ \in }{V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {Blatt}{}{}
des Graphen.}
\faktfolgerung {Dann ist $G$ genau dann
\definitionsverweis {zusammenhängend}{}{,}
wenn
\mathl{G \setminus b}{} zusammenhängend ist.}
\faktzusatz {}
\faktzusatz {}
}
{
Es sei $G$ zusammenhängend und
\mavergleichskette
{\vergleichskette
{u,v
}
{ \in }{ G \setminus \{b\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann gibt es in $G$ einen verbindenden Weg von
\mathkor {} {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
\mathl{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 verbindenen Weg, wo $b$ gar nicht vorkommt.
Es sei nun
\mathl{G \setminus \{b\}}{} zusammenhängend und seien
\mavergleichskette
{\vergleichskette
{u,v
}
{ \in }{ G
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Wenn
\mavergleichskette
{\vergleichskette
{u,v
}
{ \neq }{b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist, so kann man direkt einen verbindenden Weg aus
\mathl{G \setminus \{b\}}{} nehmen. Wenn
\mavergleichskette
{\vergleichskette
{u
}
{ = }{b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist, so ist $b$ mit einem weiteren Knotenpunkt $w$ verbunden, und einen Weg in
\mathl{G \setminus \{b\}}{} von $w$ nach $v$ kann man durch die Kante
\mathl{\{b,w\}}{} zu einem Weg in $G$ von $b$ nach $v$ fortsetzverlämgern.
\zwischenueberschrift{Weglänge und Abstand}
\inputdefinition
{}
{
Unter der \definitionswort {Länge}{} eines \definitionsverweis {Weges}{}{} in einem \definitionsverweis {Graphen}{}{} versteht man die Anzahl seiner Kanten.
}
Dabei zählt man sich wiederholende Kanten mehrfach, d.h. der Weg
\mathl{v_1 , \ldots , v_m}{} hat die Länge $m-1$, auch wenn in dem Weg die gleiche Kante mehrfach vorkommt.
\inputdefinition
{}
{
Zu zwei Knotenpunkten
\mathkor {} {u} {und} {v} {}
in einem
\definitionsverweis {zusammenhängenden}{}{}
\definitionsverweis {Graphen}{}{}
versteht man unter dem
\definitionswort {Abstand}{}
\mathl{d(u,v)}{} die minimale
\definitionsverweis {Länge}{}{}
eines verbindenden
\definitionsverweis {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.
\inputdefinition
{}
{
Unter dem
\definitionswort {Durchmesser}{}
eines
\definitionsverweis {zusammenhängenden}{}{}
\definitionsverweis {Graphen}{}{}
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
versteht man das Maximum über alle
\definitionsverweis {Abstände}{}{}
\mathl{d(u,v)}{} zu
\mavergleichskette
{\vergleichskette
{u,v
}
{ \in }{V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
\inputdefinition
{}
{
Unter dem
\definitionswort {Radius}{}
eines
\definitionsverweis {zusammenhängenden}{}{}
\definitionsverweis {Graphen}{}{}
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
versteht man den Ausdruck
\mathdisp {\operatorname{min} \left( \operatorname{max} \left( d(u,v) {{|}} u \in V \right) {{|}} v \in V \right)} { . }
}
\inputdefinition
{}
{
Zu einem Knotenpunkt
\mavergleichskette
{\vergleichskette
{v
}
{ \in }{V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eines
\definitionsverweis {zusammenhängenden}{}{}
\definitionsverweis {Graphen}{}{}
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
nennt man
\mavergleichskettedisp
{\vergleichskette
{e(v)
}
{ =} { \operatorname{max} \left( d(u,v) {{|}} u \in V \right)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
die
\definitionswort {Exzentrizität}{}
von $v$.
}
Der Durchmesser ist also das Maximum über alle Exzentrizitäten und der Radius ist das Minimum über alle Exzentrizitäten.
\inputbeispiel{}
{
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Metro_Lisboa_Route_Map_(only_with_routes_in_operation).png} }
\end{center}
\bildtext {} }
\bildlizenz { Metro_Lisboa_Route_Map_(only_with_routes_in_operation).png } {} {} {Commons} {} {}
Wir betrachten das Metronetz von Lissabon. Es handelt sich um einen \definitionsverweis {zusammenhängenden Graphen}{}{.} Der durch die gelbe Linie beschriebene \definitionsverweis {Weg}{}{} hat die \definitionsverweis {Länge}{}{} $12$. Der \definitionsverweis {Abstand}{}{} von São Sebastião zu Alameda ist $2$, der kürzeste Weg ist über Sadanha \zusatzklammer {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 $12$ besitzt. Der \definitionsverweis {Durchmesser}{}{} des Netzgraphen ist $21$, dieser wird im Abstand von Reboleira zu Aeroporto angenommen. Der \definitionsverweis {Radius}{}{} des Graphen ist $11$, unz zwar haben sowohl Saldana als auch São Sebastião diese \definitionsverweis {Exzentrizität}{}{.} Die Exzentrizität von Cidada Universitária beträgt $14$.
}
\zwischenueberschrift{Zyklen und Kreise}
\inputdefinition
{}
{
Ein
\definitionsverweis {Weg}{}{}
\mathl{v_1 , \ldots , v_m}{} in einem
\definitionsverweis {Graphen}{}{}
\mathl{(V,E)}{} heißt
\definitionswort {Zyklus}{,}
wenn
\mavergleichskette
{\vergleichskette
{v_1
}
{ = }{v_m
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist.
}
Den konstanten Weg und den einen Weg der Form
\mathl{u,v,u}{} betrachten wir als triviale Zyklen.
\inputdefinition
{}
{
Ein \definitionswort {Kreis}{} in einem \definitionsverweis {Graphen}{}{} ist ein \definitionsverweis {Zyklus}{}{} der \definitionsverweis {Länge}{}{} $\geq 3$ 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 \stichwort {zyklischer Graph} {} ist ein Graph mit zumindest einem Kreis.
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Circle_Line_(old).svg} }
\end{center}
\bildtext {Die Circle line von London ist für sich genommen ein Rundgang.} }
\bildlizenz { Circle_Line_(old).svg } {} {DavidCane, James D. Forrester} {Commons} {CC-by-sa 3.0} {}
\inputdefinition
{}
{
Ein
\definitionsverweis {Graph}{}{}
$G$ heißt
\definitionswort {Rundgang}{,}
wenn es in ihm einen
\definitionsverweis {Kreis}{}{}
\mathl{v_1,v_2 , \ldots , v_m = v_1}{} gibt, der alle Knotenpunkte und alle Kanten genau einmal durchläuft.
}
Die beiden folgenden Definition ergeben nur für zyklische Graphen Sinn.
\inputdefinition
{}
{
Die \definitionswort {Taille}{} eines \definitionsverweis {zyklischen Graphen}{}{} ist die kürzeste \definitionsverweis {Länge}{}{} eines \definitionsverweis {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$.
\inputdefinition
{}
{
Der \definitionswort {Umfang}{} eines \definitionsverweis {zyklischen Graphen}{}{} $G$ ist die längste \definitionsverweis {Länge}{}{} eines \definitionsverweis {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.
\inputfaktbeweis
{Ungerichteter Graph/Kreis/Kein Blatt/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {Graph}{}{}
und
\mavergleichskette
{\vergleichskette
{b
}
{ \in }{V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {Blatt}{}{}
des Graphen.}
\faktfolgerung {Dann ist $b$ in keinem
\definitionsverweis {Kreis}{}{}
von $G$ enthalten.}
\faktzusatz {}
\faktzusatz {}
}
{
Das Blatt $b$ ist nur zu einem einzigen Knotenpunkt $c$ benachbart. Es kann in einem Zyklus nur in der Form
\mathl{...-c-b-c-...}{} 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.
\zwischenueberschrift{Bäume und Wälder}
\inputdefinition
{}
{
Ein \definitionsverweis {Graph}{}{} ohne \definitionsverweis {Kreis}{}{} heißt \definitionswort {Wald}{}
}
\inputdefinition
{}
{
Ein \definitionsverweis {zusammenhängender}{}{} \definitionsverweis {Wald}{}{} heißt \definitionswort {Baum}{.}
}
\inputfaktbeweis
{Baum/Blatt/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei $G$ ein
\definitionsverweis {Baum}{}{}
mit zumindest zwei Knotenpunkten.}
\faktfolgerung {Dann besitzt $G$ ein
\definitionsverweis {Blatt}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Wir betrachten die Menge aller \definitionsverweis {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 \zusatzklammer {durch ${ \# \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.
\inputfaktbeweis
{Baum/Blatt/Hinwegnahme/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {Graph}{}{}
und
\mavergleichskette
{\vergleichskette
{b
}
{ \in }{V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {Blatt}{}{}
des Graphen.}
\faktfolgerung {Dann ist $G$ genau dann ein
\definitionsverweis {Baum}{}{,}
wenn
\mathl{G \setminus b}{} ebenfalls ein Baum ist.}
\faktzusatz {}
\faktzusatz {}
}
{
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.
\inputfaktbeweis
{Graph/Baum/Charakterisierung/Fakt}
{Satz}
{}
{
\faktsituation {Es sei
\mavergleichskette
{\vergleichskette
{G
}
{ = }{ (V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {Graph}{}{}
mit nichtleerer Knotenmenge $V$.}
\faktuebergang {Dann sind folgende Aussagen äquivalent.}
\faktfolgerung {\aufzaehlungdrei{$G$ ist ein
\definitionsverweis {Baum}{}{.}
}{Zwischen je zwei Punkten
\mavergleichskette
{\vergleichskette
{u,v
}
{ \in }{V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt es einen eindeutigen
\definitionsverweis {Verbindungsweg}{}{}
ohne Wiederholung.
}{$G$ ist
\definitionsverweis {zusammenhängend}{}{}
und es gilt
\mavergleichskette
{\vergleichskette
{ { \# \left( E \right) }
}
{ = }{ { \# \left( V \right) } -1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}}
\faktzusatz {}
\faktzusatz {}
}
{
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
\mavergleichskette
{\vergleichskette
{n
}
{ \geq }{2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
Punkten. Nach
Lemma 17.20
besitzt $G$ ein
\definitionsverweis {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
\mavergleichskettedisp
{\vergleichskette
{ \sum_{v \in V} d(v)
}
{ =} { 2 \cdot { \left( { \# \left( V \right) } -1 \right) }
}
{ =} { 2{ \# \left( V \right) } -2
}
{ } {
}
{ } {
}
}
{}{}{.}
Wegen der Zusammenhangseigenschaft sind die Grade zumindest $1$. Deshalb muss es
\zusatzklammer {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.
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Tetrapod Cladogram.png} }
\end{center}
\bildtext {Ein Kladogramm der Tetrapoden (Landwirbeltiere)} }
\bildlizenz { Tetrapod Cladogram.png } {} {Ceballosvg} {Commons} {CC-by-sa 4.0} {}