Zusammenhang (Graphentheorie)

Ein zusammenhängender Graph: Je zwei Knoten lassen sich durch eine Kantenfolge verbinden. Exemplarisch ist eine Kantenfolge zwischen den Knoten v und w rot hervorgehoben.

Der Zusammenhang ist ein mathematischer Begriff aus der Graphentheorie. Ein Graph heißt zusammenhängend, wenn die Knoten paarweise durch eine Kantenfolge des Graphen verbunden sind.

Definition

Ungerichtete Graphen

Dieser nicht zusammenhängende Graph hat zwei Komponenten. Die Knoten v und w können nicht verbunden werden.

Ein ungerichteter Graph $G=(V,E)$ heißt zusammenhängend, falls es zu je zwei beliebigen Knoten $v$,$w$ $\in V$ einen ungerichteten Weg in $G$ mit $v$ als Startknoten und $w$ als Endknoten gibt.

Einen maximalen zusammenhängenden Teilgraphen eines beliebigen Graphen nennt man eine Komponente oder Zusammenhangskomponente. Ein nicht zusammenhängender Graph wird durch seine Zusammenhangskomponenten partitioniert.

Gerichtete Graphen

Ein gerichteter Graph $G=(V,E)$ heißt (stark) zusammenhängend von einem Knoten $v$ aus, falls es zu jedem Knoten $w$ aus $V$ einen gerichteten Weg in $G$ von $v$ nach $w$ gibt. $G$ heißt stark zusammenhängend, falls $G$ von jedem Knoten aus stark zusammenhängend ist. Anders formuliert heißt $G$ stark zusammenhängend, falls es zwischen zwei beliebigen Knoten $u$ und $v$ aus $G$ sowohl einen gerichteten Weg von $u$ nach $v$ wie auch einen gerichteten Weg von $v$ nach $u$ in $G$ gibt.

Ein gerichteter Graph heißt (schwach) zusammenhängend, falls der zugehörige ungerichtete Graph (also der Graph, der entsteht, wenn man jede gerichtete Kante durch eine ungerichtete Kante ersetzt) zusammenhängend ist.

Ein induzierter Teilgraph $G[U]$ für eine Teilmenge $U\subset V$ heißt starke Zusammenhangskomponente von $G$, falls $G[U]$ stark zusammenhängend ist und nicht zu einem größeren stark zusammenhängenden Teilgraphen von $G$ erweitert werden kann.

Wichtige Aussagen und Sätze

Relativ leicht zeigt man folgende Aussagen:

1. Jeder zusammenhängende ungerichtete Graph mit $n$ Knoten enthält mindestens $n-1$ Kanten.
2. Jeder stark zusammenhängende gerichtete Graph mit $n$ Knoten enthält mindestens $n$ Kanten.
3. Ein ungerichteter Graph ist genau dann zusammenhängend, wenn er einen Spannbaum enthält.
4. Ein gerichteter Graph ist genau dann stark zusammenhängend, wenn seine Adjazenzmatrix irreduzibel ist. Damit ist auch ein ungerichteter Graph genau dann zusammenhängend, wenn seine Adjazenzmatrix irreduzibel ist.
5. Die Klasse aller zusammenhängenden Graphen ist nicht axiomatisierbar.

Verallgemeinerungen

Eine wesentliche Verallgemeinerung des Begriffs stellt der Begriff des k-fachen Knotenzusammenhangs, der Kantenzusammenhang und der Bogenzusammenhang dar.

Algorithmen

Mittels Tiefensuche lässt sich leicht ein linearer Algorithmus implementieren, der die Zusammenhangskomponenten eines Graphen berechnet und so einen einfachen Test impliziert, ob der Graph zusammenhängend ist. Der Test, ob ein gerichteter Graph von einem Knoten v aus zusammenhängend ist, funktioniert analog. Von Tarjan (1972) stammt ein linearer Algorithmus zur Bestimmung starker Zusammenhangskomponenten, der ebenfalls auf Tiefensuche basiert und in gerichteten Graphen die starken Zusammenhangskomponenten und leicht modifiziert in ungerichteten Graphen die Blöcke und Artikulationen berechnet. Siehe auch Union-Find-Struktur.

Die Fragestellung, ob zwei Knoten in einem Graphen verbunden sind, kann unter Verwendung eines Suchalgorithmus, wie beispielsweise der Breitensuche, effizient gelöst werden. Im Allgemeinen ist es einfach, mit einem Computer zu bestimmen, ob ein Graph verbunden ist, zum Beispiel unter Verwendung einer disjunkten Datenstruktur, oder die Anzahl der Zusammenhangskomponenten zu zählen. Ein einfacher Algorithmus kann wie folgt formuliert werden:

• Beginnen an einem beliebigen Knoten des Graphen.
• Fahre von diesem Knoten aus entweder mit der Tiefensuche oder der Breitensuche fort und zähle alle erreichten Knoten.
• Sobald der Graph vollständig durchlaufen wurde und die Anzahl der gezählten Knoten gleich der Anzahl der Knoten des Graphen ist, wird der Graph verbunden. Andernfalls wird die Verbindung getrennt.

Nach dem Satz von Menger können für zwei beliebige Knoten $u$ und $v$ in einem zusammenhängenden Graphen die Zahlen $\kappa (u,v)$ und $\lambda (u,v)$ unter Verwendung des Max-Flow-Min-Cut-Algorithmus effizient bestimmt werden. Der Zusammenhang und Kantenzusammenhang von Graphen kann dann als Minimalwerte von $\kappa (u,v)$ und $\lambda (u,v)$ berechnet werden.

Die Anzahl der zusammenhängenden ungerichteten Graphen mit $n$ Knoten steigt rasant mit der Anzahl der Knoten, und zwar etwa exponentiell zur Anzahl ${\tfrac {n\cdot (n-1)}{2}}$ der Kanten des vollständigen Graphen $K_{n}$, also etwa proportional zu $2^{\tfrac {n\cdot (n-1)}{2}}$. Wenn die Knoten nicht nummeriert sind, isomorphe Graphen also nicht mitgezählt werden, ist diese Anzahl etwa proportional zu ${\tfrac {1}{n!}}\cdot 2^{\tfrac {n\cdot (n-1)}{2}}$, weil für die meisten Isomorphieklassen alle $n!$ Graphen, die sich durch Permutation der nummerierten Knoten ergeben, verschieden sind. Die folgende Tabelle zeigt die mit Hilfe eines Computers bestimmten Anzahlen für $n\leq 8$:

Anzahl der zusammenhängenden ungerichteten Graphen
n	mit nummerierten Knoten	ohne nummerierte Knoten
2	1	1
3	4	2
4	38	6
5	728	21
6	26704	112
7	1866256	853
8	251548592	11117

Literatur

• Lutz Volkmann: Fundamente der Graphentheorie. Springer, Wien 2001, ISBN 3-211-82774-9.
• Reinhard Diestel: Graphentheorie. Springer 2006, ISBN 3-540-21391-0. (englische Version)

Weblinks

• Wolfram Mathworld: Connected Graph