Ungerichteter Graph/Wege/Zusammenhang/Textabschnitt

Aus Wikiversity
Zur Navigation springen Zur Suche springen


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.