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.

K-facher Zusammenhang

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

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}$.

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

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})}$