Zusammenhang (Graphentheorie)
# Zusammenhang (Graphentheorie)

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

## Definition

### Ungerichtete Graphen

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 Graphen nennt man eine Komponente oder Zusammenhangskomponente. Ein nicht zusammenhängender Graph wird durch seine Zusammenhangskomponenten partitioniert. Die größte Zusammenhangskomponente eines Graphen spielt im Erdős-Rényi-Modell eine wichtige Rolle.

### Gerichtete Graphen

Ein gerichteter Graph $G=(V,E)$ heißt 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 zusammenhängend ist. Anders formuliert heißt $G$ stark zusammenhängend, falls es zwischen zwei beliebigen Knoten $v$ und $w$ aus $V$ sowohl einen gerichteten Weg von $v$ nach $w$ als auch einen gerichteten Weg von $w$ nach $v$ in $G$ gibt.

Ein induzierter Teilgraph $G[U]$ für eine Knotenmenge $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.

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.

## Wichtige Aussagen und Sätze

Relativ leicht zeigt man folgende Aussagen:

* Jeder zusammenhängende ungerichtete Graph mit $n$ Knoten enthält mindestens $n-1$ Kanten.
* Jeder stark zusammenhängende gerichtete Graph mit $n$ Knoten enthält mindestens $n$ Kanten.
* Ein ungerichteter Graph ist genau dann zusammenhängend, wenn er einen Spannbaum enthält.
* 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.
* 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 ein linearer Algorithmus implementieren, der die Zusammenhangskomponenten eines ungerichteten Graphen berechnet und somit auch testet, 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 zum Bestimmen der starken Zusammenhangskomponenten in gerichteten Graphen. Leicht modifiziert findet dieser Algorithmus in ungerichteten Graphen die Blöcke und Artikulationen ebenfalls in linearer Zeit.

Ein einfacher Algorithmus, der prüft, ob ein Graph zusammenhängend ist, kann wie folgt formuliert werden:

* Beginne an einem beliebigen Knoten des Graphen.
* Durchsuche von diesem Knoten aus entweder mit Tiefensuche oder mit Breitensuche den Graphen weiter, solange noch unbesuchte Nachbarknoten existieren.
* Der Graph ist genau dann zusammenhängend, wenn am Ende die Anzahl der von der Suche erreichten Knoten gleich der Anzahl der Knoten des Graphen ist.

## Kombinatorik

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 |

## Programmierung

Das folgende Beispiel in der Programmiersprache C# zeigt die Implementierung eines ungerichteten Graphen mit Adjazenzlisten. Der ungerichtete Graph wird als Klasse UndirectedGraph deklariert. Bei der Ausführung des Programms wird die Methode Main verwendet, die die Anzahl der Komponenten des Graphen auf der Konsole ausgibt.

