Informatyka MIMUW

Wyobraźmy sobie sieć wodociągową, składającą się z rur o zadanej przepustowości, przystosowanych do przesyłania wody w określonym z góry kierunku oraz ze zbiorników połączonych tymi rurami. W przedstawionej sieci dwa zbiorniki są wyróżnione. Jeden z nich to źródło, w którym jest umieszczona pompa wpompowująca wodę, oraz ujście, czyli klient firmy wodociągowej lubiący nad wyraz zużywać wodę. Zadaniem firmy wodociągowej jest dostarczanie jak największej ilości wody klientowi. Ilość przesyłanej wody konkretną rurą nie może oczywiście przekraczać jej przepustowości. Pytanie, na które chciałby sobie odpowiedzieć właściciel firmy doprowadzającej wodę, to ile maksymalnie wody jest w stanie przesyłać w każdej chwili do klienta. Formalnym modelem dla tego typu zagadnień są sieci.

Sieć to trójka $\mathbf{N}=( V, A, {\sf c} )$, w której:

• $( V,A )$ jest pełnym digrafem (czyli $A=V\times V$),

• funkcja ${\sf c}:E \longrightarrow [0,+\infty)$, zwana przepustowością sieci, każdej krawędzi $vw$ przypisuje nieujemną liczbę rzeczywistą ${\sf c}\!(vw)$.

• Ponadto wyróżnia się dwa wierzchołki $s,t\in V$, które są odpowiednio źródłem oraz ujściem sieci.

Przepustowość ${\sf c}(vw)$ krawędzi $vw$ może być interpretowana jako wartość potencjalnie maksymalnego przepływu z wierzchołka $v$ do $w$. Jeśli przepustowość jakiejś krawędzi $e$ wynosi $0$, to krawędź $e$ jest pomijana w graficznym przedstawieniu sieci.

Przepływ w sieci $\mathbf{N}=( V, A, {\sf c} )$ to funkcja ${\sf f}:E \longrightarrow [0,+\infty)$ spełniająca warunki:

• $0\leq{\sf f}\!(vw)\leq{\sf c}\!(vw)$ dla każdej krawędzi $vw$. Wartość przepływu daną krawędzią nie może przekroczyć przepustowości tej krawędzi.

• $\displaystyle \sum_{x\in V}{\sf f}\!(xv)=\sum_{x\in V}{\sf f}\!(vx)$ dla każdego wierzchołka $v$ poza źródłem $s$ i ujściem $t$. Równość ta oznacza, że sumaryczna wartość tego, co wpływa do wierzchołka jest równa sumarycznej wartości tego, co zeń wypływa.

• $\displaystyle \sum_{x\in V}( {\sf f}\!(sx)-{\sf f}\!(xs) )=\sum_{x\in V}( {\sf f}\!(xt)-{\sf f}\!(tx) )$, tzn. sumaryczna wartość tego, co wypływa ze źródła musi być równa sumarycznej wartości tego, co wpływa do ujścia. Wartość ta będzie określana wartością przepływu ${\sf f}$.

Do analizy przepływów przydatne okazuje się pojęcie przekroju sieci. Można go sobie wyobrażać jako zbiór krawędzi $X\subseteq A$, usunięcie których z sieci $\mathbf{N}=( V, A, {\sf c} )$ rozspaja sieć na dwie części $S$ oraz $T$, przy czym $S$ zawiera źródło, a $T$ ujście. Warto zauważyć, że $X$ tworzy zbiór rozspajający w grafie szkieletowym digrafu $( V,A )$. Formalnie przekrój zdefiniujemy jako parę powstałych zbiorów wierzchołków. Taka definicja okaże się bardziej użyteczna w praktyce.

Przekrój sieci to para podzbiorów $( S,T )$ zbioru wierzchołków $V$, taka że:

• $S, T$ tworzą podział $V$, tzn. są rozłączne i w sumie dają cały zbiór $V$,

• źródło $s$ należy do $S$, a ujście $t$ należy do zbioru $T$.

Przepustowość przekroju $( S,T )$ to suma

$\displaystyle {\sf c}\!(S,T)=\sum_{v\in S,\ w\in T}{\sf c}\!(vw).$

Zależność między przepływem a przekrojem została podana w następującym Twierdzeniu o maksymalnym przepływie i minimalnym przekroju.

Twierdzenie 13.12 [Ford i Fulkerson 1956]

W dowolnej sieci wartość maksymalnego przepływu jest równa przepustowości minimalnego przekroju.

Dowód

Niech $\mathbf{N}=( V, A, {\sf c} )$ będzie siecią o źródle $s$ i ujściu $t$. Oczywiście wartość maksymalnego przepływu nie może przekraczać przepustowości minimalnego przekroju. Wystarczy więc wskazać przekrój, którego przepustowość równa się wartości maksymalnego przepływu ${\sf f}$ w sieci $\mathbf{N}$.

Niech $S\subseteq V$ będzie zbiorem zawierającym źródło $s$ oraz te wierzchołki $w$, które w grafie szkieletowym digrafu $( V,A )$ połączone są ze źródłem pewną ścieżką $s=v_1\to\ldots\to v_k=w$, w której łuk $v_i v_{i+1}$ ma niepełny przepływ (tzn. ${\sf f}\!(v_i v_{i+1}) < {\sf c}\!(v_i v_{i+1})$) lub też łuk $v_{i+1} v_i$ ma niezerowy przepływ ${\sf f}\!(v_{i+1} v_i)>0$. W języku firmy wodociągowej $S$ jest zbiorem wierzchołków, do których można jeszcze przepchnąć choć trochę wody.

Załóżmy przez chwilę, że $t\in S$. Istnieje wtedy ścieżka $s=v_0\to\ldots\to v_k=t$, w której dla każdej pary kolejnych wierzchołków $v_i,v_{i+1}$ można byłoby zwiększyć przepływ na łuku $v_i v_{i+1}$ lub zmniejszyć na łuku $v_{i+1} v_i$. Niech $\varepsilon>0$ będzie jakąś wartością zmian przepływu możliwych do wykonania na każdej parze $v_i,v_{i+1}$ kolejnych wierzchołków ścieżki. Wtedy, modyfikując odpowiednio łuki pomiędzy wierzchołkami $v_i, v_{i+1}$ uzyskalibyśmy przepływ o wartości ${\sf f}+\epsilon$, co przeczy maksymalności przepływu ${\sf f}$.

Udowodniliśmy właśnie, że $S, T$ tworzy przekrój sieci $\mathbf{N}$, gdzie $T=V- S$. Pokażmy, że przepustowość tego przekroju równa się wartości przepływu ${\sf f}$. Z definicji $S$ wynika, że jeżeli rozważymy dwa elementy $v\in S$ oraz $w\in T$, to przepływ ${\sf f}\!(vw)={\sf c}\!(vw)$ oraz ${\sf f}\!(wv)=0$.Tak więc przepustowość przekroju równa jest

$\displaystyle \sum_{v\in S,\ w\in T}{\sf c}\!(vw)=\sum_{v\in S,\ w\in T}( {\sf f}\!(vw)-{\sf f}\!(wv) ).\qquad (1)$

Z faktu, że dla $u\in S-\lbrace s \rbrace$ wartość tego co wpływa jest równa temu co wypływa, czyli innymi słowy

$\sum_{x\in V}( {\sf f}\!(ux)-{\sf f}\!(xu) )=0,$

otrzymujemy następującą równość:

$\sum_{x\in T}( {\sf f}\!(ux)-{\sf f}\!(xu) )= \sum_{x\in S-\lbrace u \rbrace}( {\sf f}\!(xu)-{\sf f}\!(ux) ).$

Prawą stronę równości (1) można więc przekształcić w następujący sposób:

$\begin{align*} \sum_{v\in S}\sum_{w\in T}( {\sf f}\!(vw)-{\sf f}\!(wv) ) & =\sum_{v\in S-\lbrace u \rbrace}\sum_{w\in T}( {\sf f}\!(vw)-{\sf f}\!(wv) )+\sum_{x\in T}( {\sf f}\!(ux)-{\sf f}\!(xu) ) \\ & =\sum_{v\in S-\lbrace u \rbrace}\sum_{w\in T}( {\sf f}\!(vw)-{\sf f}\!(wv) )+\sum_{x\in S-\lbrace u \rbrace}( {\sf f}\!(xu)-{\sf f}\!(ux) ) \\ & =\sum_{v\in S-\lbrace u \rbrace}\sum_{w\in T\cup\lbrace u \rbrace}( {\sf f}\!(vw)-{\sf f}\!(wv) ) \end{align*}$

Powtarzając wielokrotnie przekładanie kolejnych punktów $u$ z $S$ do $T$ otrzymamy w konsekwencji

$\displaystyle \sum_{v\in S}\sum_{w\in T}( {\sf f}\!(vw)-{\sf f}\!(wv) )=\sum_{w\in V-\lbrace v \rbrace}( {\sf f}\!(sw)-{\sf f}\!(ws) ),$

co na mocy (1) oznacza, że wartość przepływu z wierzchołka $s$ do wierzchołka $t$ jest równa przepustowości przekroju wyznaczonego przez zbiory $S,T$.