Zusammenhang (Graphentheorie)

Der Zusammenhang ist ein mathematischer Begriff aus der Graphentheorie. Ein Graph, das heißt ein Gebilde aus Knoten und Kanten, heißt zusammenhängend, wenn je zwei Knoten durch eine Kantenfolge des Graphen verbunden werden können. Im folgenden Artikel werden weitere Präzisierungen und Verschärfungen sowie verwandte Begriffsbildungen behandelt.

Dieser Graph ist zusammenhängend, die Knoten v und w sind durch die rote Kantenfolge verbunden.

Definition

Ungerichtete Graphen

Dieser unzusammenhä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$ und $w$ aus $V$ einen ungerichteten Weg in $G$ gibt, mit $v$ als Startknoten und $w$ als Endknoten. Die Verbindbarkeit von Knoten durch eine Kantenfolge ist eine Äquivalenzrelation auf der Knotenmenge. Eine Äquivalenzklasse $U\subset V$ bzw. den dadurch definierten Teilgraphen nennt man eine Komponente oder Zusammenhangskomponente. Falls $G$ nicht zusammenhängend ist, nennt man $G$ unzusammenhängend, der Graph zerfällt dann in seine Zusammenhangskomponenten.

Es seien $A$ und $B$ Teilmengen der Knotenmenge $V$. Ein Paar $Z=(X,Y)$, bestehend aus einer Knotenmenge $X\subset V$ und einer Kantenmenge $Y\subset E$, heißt ein $A$-$B$-Trenner, wenn jeder $A$-$B$-Weg wenigstens einen Knoten aus $X$ oder eine Kante aus $Y$ enthält. Man sagt dann auch, dass $Z$ die Knotenmengen $A$ und $B$ trennt. In den meisten Anwendungsfällen ist $X=\emptyset$ oder $Y=\emptyset$. In diesem Fall verzichtet man auf die Erwähnung des leeren Bestandteils von $Z$ und sagt einfach, die Kantenmenge $Y$ bzw. die Knotenmenge $X$ trenne $A$ und $B$. Sind $A=\{a\}$ und $B=\{b\}$ einelementig, so spricht man auch von der Trennung von $a$ und $b$. Man nennt schließlich $Z=(X,Y)$ einen Trenner für $G$ oder sagte $Z$ trenne $G$, falls es Knoten $a,b\in V\setminus X$ gibt, die durch $Z$ getrennt werden.

$G$ heißt k-fach kantenzusammenhängend, wenn es keine maximal $(k-1)$-elementige Kantenmenge in $G$ gibt, die $G$ trennt (in Multigraphen kann man Kanten entsprechend ihrer Vielfachheit mehrfach entfernen). Als Kantenzusammenhangszahl eines Graphen $G$ bezeichnet man das größte $k$, sodass $G$ $k$-fach kantenzusammenhängend ist.

$G$ heißt k-fach knotenzusammenhängend, wenn es keine maximal $(k-1)$-elementige Knotenmenge in $G$ gibt, die $G$ trennt. Statt $k$-fach knotenzusammenhängend sagt man auch oft kürzer k-fach zusammenhängend oder k-zusammenhängend. Jeder $k$-zusammenhängende Graph ist auch $(k-1)$-zusammenhängend (da es keine $(k-1)$-elementige Knotenmenge gibt, die $G$ trennt, gibt es natürlich auch keine $(k-2)$-elementige). Als Knotenzusammenhangszahl $\kappa$ (oft kurz Zusammenhangszahl oder Zusammenhang genannt) eines Graphen $G$ bezeichnet man das größte $k$, sodass $G$ $k$-zusammenhängend ist. Graphen, die k-zusammenhängend sind, haben Zusammenhangszahlen $\kappa$, die größer gleich $k$ sind: $\kappa \geq k$.

Ist $U$ eine Teilmenge der Knotenmenge $V$ mit der Eigenschaft, dass der von $U$ induzierte Teilgraph $G[U]$ von $k$-zusammenhängend ist und $G[W]$ für jede Knotenmenge $W\supset U,W\neq U$ nicht $k$-zusammenhängend ist, so nennt man $G[U]$ eine k-Zusammenhangskomponente von $G$. Eine 1-Zusammenhangskomponente ist genau die bereits oben eingeführte Zusammenhangskomponente und eine 2-Zusammenhangskomponente nennt man Block.

Der Knoten a ist eine Artikulation, die Kante e ist eine Brücke.

Ein Knoten $a$ heißt Artikulation oder Gelenkpunkt von $G$, wenn $a$ ein Trenner für $G$ ist. Eine Kante heißt Brücke von $G$, wenn sie ihre beiden inzidenten Knoten trennt. Besitzt ein Graph einen Gelenkpunkt so ist seine Zusammenhangszahl 1 und er wird als separabel bezeichnet. Besitzt ein Graph eine Brücke so ist eine Kantenzusammenhangszahl gleich 1.

Man bezeichnet den Graphen, der

1. als Knotenmenge die Blöcke und Artikulationen von $G$ enthält,
2. eine Artikulation $a$ mit einem Block $B$ verbindet, falls $a$ in $G$ zu $B$ gehört und
3. sonst keine weiteren Kanten besitzt

als Blockgraph von $G$.

Gerichtete Graphen

Ein gerichteter Graph $G=(V,E)$ heißt (stark) zusammenhängend von einem Knoten $v$ aus, falls es zu jedem Knoten $w$ einen gerichteten Weg in $G$ mit $v$ als Startknoten und $w$ als Endknoten gibt. $G$ heißt stark zusammenhängend, falls $G$ von jedem Knoten aus stark zusammenhängend ist.

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 kein stark zusammenhängender induzierter Teilgraph von $G$ existiert, der $G[U]$ echt enthält.

Bemerkung: Es gibt genau dann einen Weg mit $v$ als Startknoten und $w$ als Endknoten, wenn es einen Pfad mit $v$ als Startknoten und $w$ als Endknoten gibt. In obigen Definitionen kann man Weg also auch durch Pfad ersetzen.

Wichtige Aussagen und Sätze

Relativ leicht zeigt man folgende Aussagen:

1. Ein ungerichteter Graph ist genau dann zusammenhängend, wenn er einen Spannbaum enthält.
2. Ein ungerichteter Graph ist genau dann stark zusammenhängend, wenn seine Adjazenzmatrix irreduzibel ist.
3. Ein ungerichteter zusammenhängender Graph ist genau dann 2-zusammenhängend, wenn er keine Artikulation besitzt.
4. Die Knotenzusammenhangszahl ist höchstens so groß wie Kantenzusammenhangszahl und die Kantenzusammenhangszahl ist höchstens so groß wie der Minimalgrad.
5. Der Blockgraph $G_{B}$ eines Graphen $G$ ist ein Wald. $G_{B}$ ist genau dann Baum (also zusammenhängend), wenn $G$ zusammenhängend ist.

Ist $G=(V,E)$ ein ungerichteter Graph und sind $A$ und $B$ Teilmengen von $V$, so ist die kleinste Mächtigkeit einer $A$ von $B$ trennenden Knotenmenge gleich der größten Mächtigkeit einer Menge disjunkter $A$-$B$-Wege. Dieser Satz von Menger (1927) ist eine Verallgemeinerung des Satzes von König (1916), wonach in bipartiten Graphen die Paarungszahl der Knotenüberdeckungszahl entspricht. Man folgert aus ihm leicht den Fächersatz:

Ist $B$ eine Teilmenge von $V$ und $a$ ein Element von $V\setminus B$, so ist die kleinste Mächtigkeit einer $a$ von $B$ trennenden Teilmenge $X\subset V\setminus \{a\}$ gleich der größten Mächtigkeit eines $a$-$B$-Fächers.

Ganz ähnlich folgert man: Sind $a$ und $b$ zwei verschiedene Knoten von $G$, so gilt:

1. Sind $a$ und $b$ nicht benachbart, so ist die kleinste Mächtigkeit einer $a$ von $b$ trennenden Teilmenge von $V\setminus \{a,b\}$ gleich der größten Mächtigkeit einer Menge disjunkter $a$-$b$-Wege in $G$.
2. Die kleinste Mächtigkeit einer $a$ von $b$ trennenden Kantenmenge $Y\subset E$ ist gleich der größten Mächtigkeit einer Menge kantendisjunkter $a$-$b$-Wege in $G$.

Daraus lässt sich nun die globale Version des Satzes von Menger ableiten:

1. $G$ ist genau dann $k$-zusammenhängend, wenn $G$ zwischen je zwei Ecken $k$ disjunkte Wege enthält.
2. $G$ ist genau dann $k$-fach kantenzusammenhängend, wenn $G$ zwischen je zwei Ecken $k$ kantendisjunkte Wege enthält.

Wichtige 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.

Zur Berechnung von Knoten- und Kantenzusammenhangszahl gibt es polynomielle Algorithmen. Dazu kann man beispielsweise Flussalgorithmen verwenden. Allerdings gibt es auch effizientere Algorithmen.

Ein sehr guter, aber komplizierter Algorithmus zur Berechnung des Kantenzusammenhangs eines gerichteten (und damit auch ungerichteten) Graphen mit rationalen Gewichten wurde von H. Gabow entwickelt. (basierend auf der Matroid-Theorie, also einer Menge von Teilbäumen)

Ein leichter und auch für reelle Gewichte geeigneter Algorithmus existiert, entdeckt von Stoer/Wagner und zeitgleich Nagamotchi/Ibaraki. Dieser funktioniert mittels Knotenkontraktion und nur für ungerichtete Graphen.

Ein auf Flussalgorithmen basierender Algorithmus für gerichtete Graphen wurde von Hao/Orlin vorgestellt.

Anzahl einfacher nicht-isomorpher unbenannter Graphen

Anzahl der verschiedenen nicht-isomorphen einfachen unbenannten $k$-zusammenhängenden Graphen mit $n$ Knoten für $n$ von 1 bis 9, inklusive der Referenz OEIS (einfache Graphen umfassen sowohl zusammenhängende, wie auch nicht zusammenhängende):

$k$ \ $n$	1	2	3	4	5	6	7	8	9	OEIS
einfach	1	2	4	11	34	156	1044	12346	274668	A000088
1	1	1	2	6	21	112	853	11117	261080	A001349
2	0	1	1	3	10	56	468	7123	194066	A002218
3	0	0	1	1	3	17	136	2388	80890	A006290
4	0	0	0	1	1	4	25	384	14480	A086216
5	0	0	0	0	1	1	4	39	1051	A086217
6	0	0	0	0	0	1	1	5	59
7	0	0	0	0	0	0	1	1	5

Anzahl der verschiedenen nicht-isomorphen einfachen unbenannten Graphen mit $n$ Knoten und der Knotenzusammenhangszahl $\kappa$:

$\kappa$ \ $n$	1	2	3	4	5	6	7	8	9	OEIS
0	0	1	2	5	13	44	191	1229	13588
1	1	0	1	3	11	56	385	3994	67014	A052442
2	0	1	0	2	7	39	332	4735	113176	A052443
3	0	0	1	0	2	13	111	2004	66410	A052444
4	0	0	0	1	0	3	21	345	13429	A052445
5	0	0	0	0	1	0	3	34	992
6	0	0	0	0	0	1	0	4	54

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 online-Version)

Weblinks

• Wolfram Mathworld: "Connected Graph"
• Wolfram Mathworld: "k-Connected Graph"