k-Zusammenhang

Der k-Zusammenhang e​ines Graphen i​st ein wichtiger Begriff i​n der Graphentheorie u​nd eine Verallgemeinerung d​es Zusammenhangs. Anschaulich i​st der k-Zusammenhang e​in Maß dafür, w​ie schwierig e​s ist, e​inen Graphen d​urch Löschen v​on Knoten i​n zwei Komponenten z​u zerlegen. Ist d​er k-Zusammenhang groß, s​o müssen v​iele Knoten gelöscht werden.

Definition

Ungerichtete Graphen

Ein ungerichteter Graph ${\displaystyle G=(V,E)}$ (welcher auch ein Multigraph sein kann) heißt k-fach knotenzusammenhängend (oder auch einfach k-fach zusammenhängend oder k-zusammenhängend), wenn es keinen Trenner ${\displaystyle T=(X,Y)}$ in ${\displaystyle G}$ mit einer maximal ${\displaystyle (k-1)}$-elementigen Knotenmenge ${\displaystyle X}$ und leerer Kantenmenge ${\displaystyle Y=\emptyset }$ gibt. Äquivalent dazu ist, dass für alle Knotenmengen ${\displaystyle K}$ mit Mächtigkeit ${\displaystyle k-1}$ der von ${\displaystyle V\backslash K}$ induzierte Teilgraph zusammenhängend ist.

Ist ${\displaystyle U}$ eine Teilmenge der Knotenmenge ${\displaystyle V}$ mit der Eigenschaft, dass der von ${\displaystyle U}$ induzierte Teilgraph ${\displaystyle G[U]}$ ${\displaystyle k}$-zusammenhängend ist und ${\displaystyle G[W]}$ für jede Knotenmenge ${\displaystyle W\supset U,W\neq U}$ nicht ${\displaystyle k}$-zusammenhängend ist, so nennt man ${\displaystyle G[U]}$ eine k-Zusammenhangskomponente von ${\displaystyle G}$. Eine 2-Zusammenhangskomponente nennt man auch einen Block.

Als Knotenzusammenhangszahl ${\displaystyle \kappa (G)}$ (oft kurz Zusammenhangszahl oder Zusammenhang genannt) eines Graphen ${\displaystyle G}$ bezeichnet man das größte ${\displaystyle k}$, sodass ${\displaystyle G}$ ${\displaystyle k}$-zusammenhängend ist. Eine dazu äquivalente Definition ist, dass die Knotenzusammenhangszahl die kleinste Mächtigkeit eines Trenners von ${\displaystyle G}$ mit leerer Kantenmenge ist. Graphen, die k-zusammenhängend sind, haben Zusammenhangszahlen ${\displaystyle \kappa (G)}$, die größer gleich ${\displaystyle k}$ sind: ${\displaystyle \kappa (G)\geq k}$.

Gerichtete Graphen

Ein gerichteter Graph ${\displaystyle D=(V,A)}$ (welcher auch Mehrfachkanten enthalten kann) heißt k-fach stark zusammenhängend, wenn für jede Knotenmenge ${\displaystyle U}$ der Mächtigkeit ${\displaystyle k-1}$ der von ${\displaystyle V\backslash U}$ induzierte Teilgraph ${\displaystyle G\left[V\backslash U\right]}$ stark zusammenhängend ist.

Das größte ${\displaystyle k}$, so dass ${\displaystyle D}$ ${\displaystyle k}$-fach stark zusammenhängend ist, wird starke Zusammenhangszahl genannt und mit ${\displaystyle \sigma (D)}$ bezeichnet.

Beispiel

K-facher Zusammenhang

Das ist das Haus vom Nikolaus

Betrachte als Beispiel das rechts dargestellte Haus vom Nikolaus. Es ist 2-zusammenhängend, da keine Trenner existieren, die nur aus einem Knoten bestehen. Äquivalent dazu ist, dass keine Artikulation existiert. Betrachtet man aber nun z. B. die Knoten 3 und 4, so trennen diese das Haus in die Knotenmengen 5 sowie 1 und 2, da jeder Weg von 5 nach 1 oder 2 durch einen der Knoten 3 oder 4 gehen muss. Das Haus ist also einfach und zweifach knotenzusammenhängend und seine Knotenzusammenhangszahl ist ${\displaystyle \kappa (G)=2}$.

K-fach starker Zusammenhang

Der im Beispiel behandelte Digraph

Betrachte als Beispielgraph den rechts dargestellten Turniergraph. Der Graph ist stark zusammenhängend, also auf jeden Fall einfach stark zusammenhängend. Beginnt man mit dem Löschen von einelementigen Knotenmengen, so wird der starke Zusammenhang jedoch bald zerstört. Entfernt man z. B. den Knoten 3, so ist der Knoten 2 von Knoten 4 aus nicht mehr erreichbar. Somit ist der Digraph einfach stark zusammenhängend und ${\displaystyle \sigma (D)=1}$.

Eigenschaften

• Jeder ${\displaystyle k}$-zusammenhängende Graph ist auch ${\displaystyle (k-1)}$-zusammenhängend (da es keine ${\displaystyle (k-1)}$-elementige Knotenmenge gibt, die ${\displaystyle G}$ trennt, gibt es natürlich auch keine ${\displaystyle (k-2)}$-elementige).
• Ein einfacher Graph ist genau dann 2-zusammenhängend, wenn er keine Artikulation besitzt.
• Eine 1-Zusammenhangskomponente ist genau die klassische Zusammenhangskomponente.
• Ist ${\displaystyle |G|\geq 2}$, so gilt ${\displaystyle \delta (G)\geq \lambda (G)\geq \kappa (G)}$, wobei ${\displaystyle \lambda (G)}$ die Kantenzusammenhangszahl und ${\displaystyle \delta (G)}$ der Minimalgrad des Graphen ${\displaystyle G}$ ist. Hoher Zusammenhang setzt also hohen Minimalgrad voraus. Der Umkehrschluss gilt jedoch nicht.
• ${\displaystyle G}$ ist genau dann ${\displaystyle k}$-zusammenhängend, wenn ${\displaystyle G}$ zwischen je zwei Knoten ${\displaystyle k}$ disjunkte Wege enthält. Diese Aussage ist auch als die globale Version des Satzes von Menger bekannt.

Algorithmen

Bestimmung der Knotenzusammenhangszahl

Zur Berechnung der Knotenzusammenhangszahl gibt es polynomielle Algorithmen. Dazu kann man beispielsweise Flussalgorithmen verwenden. Hierfür berechnet man für alle Knotenpaare ${\displaystyle s,t}$ einen maximalen ${\displaystyle s}$-${\displaystyle t}$-Fluss. Der kleinste Wert, den der Fluss annimmt, ist dann nach dem Satz von Menger die Knotenzusammenhangszahl. Ist also ${\displaystyle F(n,m)}$ der benötigte Aufwand, einen ${\displaystyle s}$-${\displaystyle t}$-Fluss in einem Graphen mit n Knoten und m Kanten zu bestimmen, so liefert dieser naive Ansatz immerhin einen Aufwand von ${\displaystyle {\mathcal {O}}(n^{2}F(n,m))}$. Allerdings gibt es auch effizientere Algorithmen.

Ein s​ehr guter, a​ber komplizierter Algorithmus z​ur Berechnung d​es Kantenzusammenhangs e​ines gerichteten (und d​amit auch ungerichteten) Graphen m​it rationalen Gewichten w​urde von H. Gabow entwickelt (basierend a​uf der Matroid-Theorie, a​lso einer Menge v​on 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 a​uf Flussalgorithmen basierender Algorithmus für gerichtete Graphen w​urde von Hao/Orlin vorgestellt.

Test auf k-Zusammenhang

Ist man nicht an der Knotenzusammenhangszahl interessiert, sondern will man nur wissen, ob ein Graph k-zusammenhängend ist für vorgegebenes k, so gibt es schnelle Algorithmen. So kann der 2-Zusammenhang in linearer Zeit bestimmt werden. Für ungerichtete Graphen gibt es lineare Algorithmen, die einen 3-Zusammenhang überprüfen. Für 4-Zusammenhang in ungerichteten Graphen existieren Algorithmen mit Aufwand ${\displaystyle {\mathcal {O}}(n^{2})}$

Verwandte Begriffsbildungen

Der Kantenzusammenhang i​st ein z​um k-Zusammenhang ähnlicher Begriff, bloß d​ass nur Trenner m​it leerer Knotenmenge u​nd einer beliebigen Kantenmenge betrachtet werden. Der Kantenzusammenhang g​ibt also e​in Maß dafür an, w​ie viele Kanten a​us einem Graphen entfernt werden müssen, s​o dass dieser i​n verschiedene Komponenten zerfällt. Einen z​um Kantenzusammenhang analogen Begriff für gerichtete Graphen bildet d​er Bogenzusammenhang, welcher anstelle v​on ungerichteten Kanten gerichtete Kanten betrachtet.

Anzahl einfacher nicht-isomorpher unbenannter Graphen

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

${\displaystyle k}$ \ ${\displaystyle 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 ${\displaystyle n}$ Knoten und der Knotenzusammenhangszahl ${\displaystyle \kappa }$:

${\displaystyle \kappa }$ \ ${\displaystyle 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

• Reinhard Diestel: Graphentheorie. Springer, Berlin 2010, ISBN 978-3-642-14911-5 (354 Seiten).
• Lutz Volkmann: Fundamente der Graphentheorie, Springer (Wien) 1996, ISBN 3-211-82774-9 (neuere, Online-Version „Graphen an allen Ecken und Kanten“; PDF; 3,7 MB)
• Alexander Schrijver: Combinatorial optimization. polyhedra and efficiency. Springer, Berlin 2003, ISBN 978-3-540-44389-6 (3 Bände, 1881 Seiten).

Weblinks

• Wolfram Mathworld: „k-Connected Graph“