Zarówno drzewo, jak i klika są grafami spójnymi. W drzewie jednak, usunięcie jakiegokolwiek wierzchołka nie będącego liściem rozspaja go. Z drugiej strony, klika pozostaje spójna po usunięciu dowolnej liczby wierzchołków. Aby rozróżnić te różne rodzaje spójności rozważa się następujące uogólnienia spójności.
Graf \( k \)-spójny to graf, który po usunięciu dowolnie wybranych \( k-1 \) wierzchołków (i incydentnych z nimi krawędzi) pozostaje spójny.
Graf \( k \)-spójny krawędziowo to graf, który po usunięcie dowolnie wybranych \( k-1 \) krawędzi (bez usuwania wierzchołków) pozostaje spójny.
Przykład
Z pojęciami wielospójności związane są następujące pojęcia:
Zbiór rozdzielający wierzchołki \( u,v \) to zbiór wierzchołków \( S\subseteq V- \lbrace u,v \rbrace \) taki, że każda droga z \( u \) do \( v \) przechodzi przez któryś element ze zbioru \( S \).
Ponadto powiemy, że \( S \) jest zbiorem rozdzielającym, jeśli \( S \) jest zbiorem rozdzielającym jakichś dwu wierzchołków \( u,v \).
Zbiór rozspajający wierzchołki \( u,v \) to zbiór krawędzi \( F\subseteq E \) taki, że każda droga z \( u \) do \( v \) zawiera jakąś krawędź z \( F \).
Rozcięcie wierzchołków \( u,v \) to zbiór rozspajający wierzchołki \( u,v \), którego żaden podzbiór właściwy nie rozspaja \( u \) z \( v \).
Zbiór krawędzi \( F \) będziemy nazywać rozcięciem, jeśli \( F \) jest rozcięciem jakichś dwu wierzchołków \( u,v \)
Most to taka krawędź \( e \), że zbiór \( \lbrace e \rbrace \) tworzy rozcięcie.
Uwaga
Jeżeli graf jest \( k \)-spójny, to każdy jego zbiór rozdzielający musi mieć co najmniej \( k \) wierzchołków. Analogicznie jeśli \( \mathbf{G} \) jest \( k \)-spójny krawędziowo, to każde jego rozcięcie musi mieć co najmniej \( k \) krawędzi.
Przykład
Przykładowymi zbiorami rozdzielającymi wierzchołki \( u,w \) w grafie z rysunku Grafy menger są zbiory \( \lbrace x,y,z \rbrace \) i \( \lbrace s,t \rbrace \). Zbiory \( \lbrace xs,xy,ys,ys,zt \rbrace \) jest rozspajający, a zbiór \( \lbrace xs,xy,uy,uz \rbrace \) jest rozcięciem. Graf ten jest \( 2 \)-spójny oraz \( 2 \)-spójny krawędziowo.
Okazuje się, że dla dwu różnych wierzchołków istnieje powiązanie - między wielkością rozcięcia, a liczbą dróg pomiędzy nimi - silniejsze niż to wynikające z definicji.
Twierdzenie 13.8 [Menger 1927]
Największa możliwa liczba krawędziowo rozłącznych dróg łączących dwa różne niesąsiednie wierzchołki grafu spójnego, jest równa najmniejszej liczbie krawędzi w zbiorze rozspajającym te wierzchołki.
Dowód
Niech \( w,u \) będą dwoma różnymi i niesąsiednimi wierzchołkami grafu spójnego \( \mathbf{G}=( V,E ) \). Przez \( k \) oznaczmy najmniejszą możliwą liczność zbioru krawędzi rozspajającego \( w,u \). Oczywiście każda droga łącząca \( w \) z \( u \) musi przejść przez każdy zbiór rozspajający. A zatem dróg krawędziowo rozłącznych łączących \( w \) z \( u \) nie może być więcej niż \( k \). Tak więc wystarczy pokazać, że istnieje \( k \) rozłącznych krawędziowo dróg z \( w \) do \( u \).
Dowód przeprowadzimy indukcyjnie ze względu na liczbę krawędzi w grafie \( \mathbf{G} \) rozważając dwa przypadki.
1. Pewien zbiór rozspajający \( X \) mocy \( k \) ma krawędź nie incydentną z \( w \) oraz ma krawędź (być może inną) nie incydentną z \( u \).
Graf \( G \), po usunięciu wszystkich krawędzi z \( X \), podzieli się na dwie spójne składowe \( W \) oraz \( U \), do których odpowiednio należą \( w \) i \( u \).
Przez \( \mathbf{W}' \) oznaczmy graf powstały z grafu \( \mathbf{G} \) poprzez ściągnięcie \( U \) w jeden wierzchołek \( u' \). Wtedy \( u' \) jest połączony z tymi wierzchołkami \( t\in W \), z którymi połączony był jakiś wierzchołek \( s\in U \). Warto zauważyć, że wtedy musiało być \( st\in X \). Krawędzie łączące wierzchołki wewnątrz \( W \) pozostały niezmienione. Graf \( \mathbf{U}' \) definiujemy analogicznie, poprzez ściągnięcie zbioru \( W \) do wierzchołka \( w' \).
W grafie \( \mathbf{W}' \) zbiór krawędzi incydentnych z \( u' \), których jest \( k \), tworzy minimalny zbiór rozspajający wierzchołki \( w,u' \). Ponieważ założyliśmy, że w \( X \) istnieje krawędź nieincydentna z \( u \), to \( U \) ma co najmniej dwa wierzchołki, a zatem graf \( \mathbf{W}' \) ma mniej krawędzi niż \( \mathbf{G} \). Tak więc możemy skorzystać z założenia indukcyjnego otrzymując \( k \) rozłącznych krawędziowo dróg łączących \( w \) z \( u' \). Analogicznie w grafie \( \mathbf{U}' \) otrzymujemy \( k \) rozłącznych krawędziowo dróg łączących \( w' \) z \( u \). Sklejając obie te rodziny dróg otrzymujemy \( k \) rozłącznych ścieżek łączących \( w \) z \( u \) w grafie \( \mathbf{G} \).
2. W każdym zbiorze rozspajającym \( X \) o mocy \( k \) każda krawędź jest incydentna do \( w \) lub do \( u \).
Możemy wtedy założyć, że \( \mathbf{G} \) zawiera jedynie krawędzie należące do któregoś zbioru rozspajającego \( w,u \) o liczności \( k \). Gdyby tak nie było i istniałaby jakaś inna krawędź \( e \), to moglibyśmy \( e \) usunąć i, na mocy założenia indukcyjnego, otrzymać natychmiast \( k \) rozłącznych dróg łączących \( w,u \). Tak więc pozostały nam jedynie te krawędzie, które są w minimalnych zbiorach rozspajających \( w,u \). To zaś, zgodnie z założeniem przypadku 2 oznacza, że każda krawędź jest incydentna z \( w \) lub z \( u \). W ten sposób drugi przypadek sprowadziliśmy do sytuacji, w której każda ścieżka z \( w \) do \( u \) ma co najwyżej dwie krawędzie. Wśród takich ścieżek nietrudno jest już wskazać \( k \) rozłącznych krawędziowo.
Jako ćwiczenie 9 pozostawiamy dowód twierdzenia analogicznego do Twierdzenia 13.8, a wiążącego tym razem zbiory rozdzielające z drogami rozłącznymi wierzchołkowo.
Twierdzenie 13.9
Największa możliwa liczba wierzchołkowo rozłącznych dróg łączących dwa różne niesąsiednie wierzchołki grafu spójnego, jest równa najmniejszej liczbie wierzchołków w zbiorze rozdzielającym te wierzchołki.
Z Twierdzenia 13.9, można w łatwy sposób wywnioskować Twierdzenia 13.7, o skojarzeniach w grafach dwudzielnych. Wyprowadzenie to pozostawiamy jako ćwiczenie 10.
W grafie \( k \)-spójnym usunięcie jakichś \( k-1 \) punktów nie rozspaja go. A zatem zbiór rozdzielający jakieś dwa wierzchołki \( w,u \) ma co najmniej \( k \) wierzchołków. Tym samym między \( u \) a \( w \) musi istnieć co najmniej \( k \) dróg. Pisząc zwięźlej możemy powiedzieć, że:
Wniosek 13.10
Graf z co najmniej \( k+1 \) wierzchołkami jest \( k \)-spójny wtedy i tylko wtedy, gdy dowolne dwa wierzchołki są połączone przynajmniej \( k \) drogami wierzchołkowo rozłącznymi.
Analogiczne rozumowanie przeprowadzone dla ścieżek rozłącznych krawędziowo prowadzi do następującego wniosku.
Wniosek 13.11
Graf z co najmniej \( k-1 \) krawędziami jest \( k \)-spójny krawędziowo wtedy i tylko wtedy, gdy dowolne dwa wierzchołki są połączone przynajmniej \( k \) drogami krawędziowo rozłącznymi.