Ungerichteter Graph/Wege/Zusammenhang/Textabschnitt

Definition

Ein Weg in einem Graphen ist eine Folge ${}v_{1},v_{2},\ldots ,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},\ldots ,e_{m-1}$ mit Kanten ${}e_{i}\in E$ angeben, wobei dann vorauszusetzen ist, dass stets ${}e_{i}$ und ${}e_{i+1}$ 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 G$ 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},\ldots ,v_{r-1},v_{r}=v$ miteinander verbunden sind, so ist ${}v$ mit ${}u$ durch den umorientierten Kantenzug ${}v_{r},v_{r-1},\ldots ,v_{2},v_{1}$ verbunden. Dies sichert die Symmetrie. Wenn ${}u$ mit ${}v$ durch den Kantenzug ${}u=v_{1},v_{2},\ldots ,v_{r}=v$ verbunden ist und ${}v$ mit ${}w$ durch den Kantenzug ${}v=w_{1},w_{2},\ldots ,w_{s}=w$ verbunden ist, so ist ${}v$ mit ${}w$ durch den zusammengesetzten Kantenzug ${}u=v_{1},v_{2},\ldots ,v_{r}=v=w_{1},w_{2},\ldots ,w_{s}=w$ verbunden. Dies sichert die Transitivität.

$\Box$

Definition

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

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

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 verbindenen Weg, wo ${}b$ gar nicht vorkommt.

Es sei nun ${}G\setminus \{b\}$ zusammenhängend und seien ${}u,v\in G$. Wenn ${}u,v\neq 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$ fortsetzverlämgern.

$\Box$