next up previous contents index
Next: �wiczenia Up: Metody sieciowe Previous: Przepustowo�� wierzcho�k�w   Spis rzeczy   Indeks

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

\begin{displaymath}P=(x_1,e_1,x_2,e_2,...,x_k,e_k,x_{k+1})\end{displaymath}

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


Subsections
next up previous contents index
Next: �wiczenia Up: Metody sieciowe Previous: Przepustowo�� wierzcho�k�w   Spis rzeczy   Indeks