Twierdzenie Mengera

W niniejszym podrozdziale będzie mowa o spójności grafu i parametrze $\kappa(G)$ który jest w pewien sposób miarą spójności grafu $G$. Zarówno spójność jak parametr $\kappa$ są podstawowymi, bardzo ważnymi pojęciami teorii grafów.
Dla grafu $G=(V;E)$ i podzbioru $S\subset V$ przez $G-S$ oznaczamy graf $G'=(V-S;E')$, gdzie $E'=\{ e \in E: e \subset V-S\}$. Inaczej mówiąc, zbiór krawędzi grafu $G-S$ to te krawędzie grafu $G$ których żaden z końców nie jest w $S$.
Ścieżką z $x$ do $y$ w grafie $G=(V;E)$ nazywamy ciąg wierzchołków i krawędzi

$$P=(x_1,e_1,x_2,e_2,...,x_k,e_k,x_{k+1})$$

( $x_i \in V, i=1,...,k+1, e_j \in E, j=1,...,k$) taki, że $e_i=x_ix_{i+1}$.
Mówimy, że graf $G$ jest spójny jeśli dla dowolnych wierzchołków $x$ i $y$ grafu $G$ istnieje ścieżka z $x$ do $y$ (mówimy także ścieżka łącząca $x$ z $y$).
Minimalną liczbę $k$ taką, że w grafie $G$ istnieje zbiór wierzchołków $S$ spełniający warunki

1. $\mid S \mid = k$
2. $G-S$ nie jest grafem spójnym lub ma tylko jeden wierzchołek

nazywamy liczbą spójności grafu $G$ , lub spójnością grafu i oznaczamy przez $\kappa(G)$.

Przykład 8.7   Czytelnik zechce sprawdzić, że graf $G$ przedstawiony na rysunku 8.5.1 ma liczbę spójności równą $2$ ($\kappa (G)=2$).

O grafie $G$ dla którego $\kappa (G)=k$ mówimy, że jest $l-$spójny, dla każdego $l \leq \kappa (G)$.

Przykład 8.8   Graf $G$ z rysunku 8.5.1 jest $1-$spójny i $2-$spójny.

Oczywiście grafy spójne są $1-$spójne.
Niech $G$ będzie grafem spójnym ( $\kappa (G) \geq 1$). Zbiór $S$ taki, że $G-S$ nie jest spójny nazywamy separatorem grafu $G$. Separator $S$ o minimalnej liczbie wierzchołków (a więc taki, że $\mid S \mid = \kappa (G))$ nazywamy separatorem minimalnym. Niech $P$ i $P'$ będą dwoma ścieżkami łączącymi dwa różne wierzchołki $x$ i $y$. Mówimy, że $P$ i $P'$ są wewnętrznie rozłączne jeżeli jedynymi wspólnymi wierzchołkami tych ścieżek są $x$ i $y$.

Twierdzenie 8.10   Maksymalna liczba ścieżek wewnętrznie rozłącznych łączących dwa wierzchołki $x$ i $x$ grafu $G$ jest równa liczności minimalnego separatora rozdzielającego $x$ i $y$.

Dowód. Z grafem $G=(V;E)$ skojarzmy sieć $S$ o zbiorze wierzchołków $V$, oraz źródle, odpływie, zbiorze łuków $A$ i funkcjami przepustowości łuków i wierzchołków zdefiniowanymi w sposób następujący:

1. $x$ jest źródłem sieci $S$,
2. $y$ jest odpływem $S$,
3. każdej krawędzi $ab$ w grafie $G$ odpowiadają dwa łuki w $S$: $(a,b)$ i $(b,a)$,
4. przepustowość każdego łuku wynosi $+\infty$,
5. przepustowości wszystkich wierzchołków różnych od $x$ i $y$ wynoszą $1$,
6. przepustowości $x$ i $y$ wynoszą $+\infty$.

Maksymalny całkowitoliczbowy przepływ z $x$ do $y$ wyznaczy nam oczywiście maksymalną luiczbę ścieżek wewnątrznie rozłącznych z $x$ do $y$. Przekrój o minimalnej przepustowości w sieci $S$ wyznaczy z kolei minimalny separator $x$ od $y$. Z twierdzenia o maksymalnym przepływie i minimalnym przekroju wynika teraz twierdzenie . Z twierdzenia wynika natychmiast twierdzenie Mengera:

Wniosek 8.11 (Twierdzenie Mengera)   W dowolnym grafie $G$ każde dwa wierzchołki są połączone $\kappa(G)$ ścieżkami wewnętrznie rozłącznymi.

Czytelnik zechce samodzielnie zastanowić się jak udowodnić następny wniosek, który jest uogólnieniem twierdzenia Mengera (por. ćwiczenie ).

Wniosek 8.12   Niech $A$ i $B$ będą dwoma rozłącznymi zbiorami wierzchołków grafu $G$ takimi, że $\mid A \mid, \ \mid B \mid \geq \kappa (G)$. Wtedy istnieje w $G$ $\kappa(G)$ wierzchołkowo rozłącznych ścieżek z $A$ do $B$.