Przepływy w sieciach

W sieci $S$ może być wyróżniony pewien wierzchołek $s$, nazywany źródłem i inny wierzchołek, powiedzmy $t$, który nazywać będziemy odpływem.
Niech $S=(V,A,c)$ będzie siecią o źródla $s$ i odpływie $t$ oraz nieujemnej funkcji przepustowości $c$. O nieujemnej funkcji $f:A \rightarrow {\bf R}$ mówimy, że jest przepływem z $s$ do $t$ w $S$ jeżeli spełnia następujące warunki:

$$f(x,y) \leq c(x,y) \ \ \ \mbox{dla każdego } (x,y) \in A$$ (8.2)

$$\sum_{y\in N^+(x)} f(x,y) - \sum_{z \in N^-(x)}f(z,x)= 0 \ \ \ \mbox{dla każdego } x\neq s,t$$ (8.3)

Liczbę

$$w(f) = \sum_{y\in N^+(s)} f(s,y) - \sum_{z \in N^-(s)}f(z,s)= 0$$

nazywamy wartością przepływu $f$.

Przykład 8.2   Niech $S$ będzie siecią jak na rysunku 8.3. Liczby wypisane obok łuków w kwadracikach oznaczają przepustowości łuków, a te bez kwadracików przepływy. Jest bardzo łatwym sprawdzenie, że na rysunku poprawnie zdefiniowany jest przepływ (spełnia warunki () i ()), a wartoć tego przepływu wynosi $5$. $\Box$

Rys. 8.3

Problem optymalizacyjny narzuca się teraz sam.
Problem maksymalnego przepływu.
Dla danej sieci $S=(V,A;c)$ o źródle $s$ i odpływie $t$ znaleźć przepływ o maksymalnej wartości.
W dalszym ciągu będzie nam wygodnie będzie nam przyjąć zamiast $(x,y) \notin A$, $c(x,y)=0$ i istnienie wszystkich możliwych łuków w sieci. Interpretacja takiej umowy jest oczywista: nie ma przepływu (a raczej jest przepływ zerowy) na nieistniejących łukach^8.6. Wtedy warunki () i () można zapisać, odpowiednio,

$$f(x,y) \leq c(x,y) \ \ \ \mbox{dla wszystkich } x,y \in V$$ (8.4)

$$\sum_{y\in V}f(x,y) - \sum_{z\in V}f(z,x) = 0 \ \ \ \mbox{dla każdego } x \neq s,t$$ (8.5)

a wzór na wartość przepływu

$$w(f) = \sum_{y \in V}f(s,y) - \sum_{z \in V}f(z,s)$$ (8.6)

Zauważmy, że przepływ w przykładzie nie jest maksymalny. Zwiększając przepływ na łukach: $(s,a), (a,c), (c,b)$ i $(c,t)$ o $1$ otrzymamy przepływ (warunki () i () są dalej spełnione) i wartość tego przepływu wynosi $6$. Okaże się, że ten prosty pomysł znajdowania ścieżki prowadzącej z $s$ do $t$ wzdłóż której można zwiększyć przepływ na poszczególnych łukach o stałą wartość, jest kluczową ideą prowadzącą do rozwiązania problemu maksymalnego przepływu w sieciach.
Jest najzupełniej oczywiste, że problem maksymalnego przepływu jest problemem programowania liniowego. Wierzchołki sieci nazwiemy $v_0,v_1,...,v_n$, z $v_0=s, v_n=t$, a przepływ na łuku $(v_i,v_j)$ oznaczymy przez $x_{ij}$ (zamiast $f(v_i,v_j)$ a przepustowość łuku $(v_i,v_j)$ przez $c_{ij}$. Nasz problem maksymalnego przepływu jest PPL:

$$% latex2html id marker 10038 \left\{\begin{array}{l} \b... ...j}, \ \ i,j: (v_i,v_j) \in A \end{array} \end{array}\right.$$ (8.7)

Zauważmy, że jeśli zbiór wierzchołków sieci jest skończony (a tylko takie sieci tu rozważamy) a przepustowości łuków są liczbami skończonymi, to problem () jest ograniczony, posiada więc rozwiązanie optymalne. Z powyższego oraz twierdzenia wynika następujący wniosek.

Wniosek 8.2   Jeśli funkcja przepustowości łuków przyjmuje wartości całkowite, to problem maksymalnego przepływu w tej sieci ma całkowite rozwiązanie optymalne.

Ważnym pojęciem dla problemu maksymalnego przepływu są przekrój i jego wartość.
Niech będzie dana sieć $S=(V,A,c)$ ze źródłem $s$ i odpływem $t$ i niech $W$ będzie takim podzbiorem $V$, że $s \in W$ i $t\notin W$. Zbiór $W-W$ oznaczmy przeż $\bar{W}$. Zbiór łuków

$$(W,\bar{W})=\{ (x,y): x \in W, y \in \bar{W}\}$$

nazywamy przekrojem rozdzielającym $s$ od $t$ lub krótko przekrojem. Liczbę

$$c(W,\bar{W}) = \sum_{(x,y)\in (W,\bar{W})}c(x,y)$$

nazywamy przepustowością przekroju $(W,\bar{W})$.

Twierdzenie 8.3   Niech $S=(V,A,c)$ będzie siecią o źródle $s$ i odpływie $t$. Dla dowolnego przepływu $f$ i dla dowolnego przekroju $(W,\bar{W})$ zachodzi nierówność

$$w(f) \leq c(W,\bar{W})$$

Dowód. Sumując odpowiednio wzory () i () po wszystkich $x \in W$ i pamiętając, że $s\in W, W \cap \bar{W} = \emptyset , W \cup \bar{W} = V$, otrzymamy

$$w(f) = \sum_{u \in V} f(s,u) - \sum_{v \in V} f(v,s) +\sum... ...\left( \sum_{y \in V} f(x,y) - \sum_{z \in V}f(z,x) \right) =$$

$$= \sum_{x \in W, y\in V} f(x,y) - \sum_{x \in W, z \in V}f(z,x) =$$

$$= \left( \sum_{x \in W, y \in W} f(x,y) + \sum_{x \in W, y \in \bar{W}} f(x,y) \right)$$

$$- \left( \sum_{x \in W, z\in W} f(z,x) + \sum_{x \in W, z \in \bar{W}}f(z,x) \right)$$

Zauważmy, że $\sum_{x\in W, y \in W}f(x,y) = \sum_{x \in W, z \in W} f(z,x)$, a wobec tego

$$w(f) = \sum_{x \in W, y\in \bar{W}} f(x,y) - \sum_{x \in W, z \in \bar{W}} f(z,x)$$ (8.8)

Wartości $f(z,x)$ są nieujemne, uwzględniając więc nierówności () otrzymujemy

$$w(f) \leq \sum_{x \in W, y\in \bar{W}} f(x,y) \leq \sum_{x \in X, y \in \bar{W}} c(x,y) =c(W,\bar{W})$$ (8.9)

co kończy dowód.

Uwaga 8.1   Jeżeli uda nam się znaleźć przepływ $f$ i przekrój $(W,\bar{W})$ takie, że

$$w(f) = c(W,\bar{W})$$

to na mocy twierdzenia $f$ jest przepływem maksymalnym (a przekrój $(W,\bar{W})$ ma minimalną przepustowość).

Niejako po drodze w dowodzie twierdzenia otrzymaliśmy ważną równość () którą teraz zapiszemy nieco inaczej.

Uwaga 8.2   Dla każdego przepływu $f$ i przekroju $(W,\bar{W})$ zachodzi wzór

$$w(f) = \sum_{x \in W, v \in \bar{W}} f(x,v) - \sum_{y \in W, w \in \bar{W}}f(w,y)$$ (8.10)

Wniosek 8.4   Dla każdego przepływu $f$ zachodzi wzór

$$\sum_{x \in V} f(x,t) - \sum_{x\in V}f(t,x) = w(f)$$

Wniosek oznacza, że w przyrodzie nic nie ginie, to co wypłynęło ze źródła wpływa do odpływu!
Dowód wniosku . Wystarczy zastosować wzór () do $\bar{W} = \{ t \}$. Twierdzenie da nam możliwość udowodnienia twierdzenia o maksymalnym przepływie i minimalnym przekroju, odkrytego niezależnie przez Forda i Fulkersona [8] oraz Eliasa, Feinsteina i Shannona [7].

Twierdzenie 8.5 (Max flow min cut theorem)   Maksymalna wartość
przepływu ze źródła $s$ do odpływu $t$ w sieci jest równa wartości minimalnego przekroju rozdzielającego $s$ od $t$:

$$% latex2html id marker 11043 \mbox{max}\{ w(f)\vert f \mbox... ...} = \mbox{min}\{ c(W,\bar{W}) \vert s\in W, t \in \bar{W} \}$$

Dowód twierdzenia polega de facto na wskazaniu algorytmu pozwalającego znależć maksymalny przepływ w sieci, tzw. algorytm ścieżki powiększającej Forda-Fulkersona (p. [9]). Formalnie algorytm ten zostanie przedstawiony później.
Niech $f$ będzie przepływem maksymalnym w sieci $G=(V,A,c)$ ze źródła $s$ do odpływu $t$. Utwórzmy rekurencjnie zbiór $W$ w następujący sposób:

1. $s \in W$
2. jeśli $x \in W, (x,y) \in A, f(x,y)<c(x,y)$ to $y \in W$
3. jeśli $x \in W, (y,x) \in A$ i $f(y,x)> 0$ to $y \in W$.

Kluczową ideą dowodu jest obserwacja, że dla każdego wierzchołka $x \in W$ istnieje ścieżka

$$P = (x_0,e_1,x_1,...,x_{k-1},e_k,x_k)$$

taka, że $x_0=t, x_k = x$ i dla każdego $e_i$ zachodzi albo

$$e_i = (x_{i-1},x_i) \mbox{ i } f(e_i) < c(e_i)$$ (8.11)

albo

$$e_i = (x_i,x_{i-1}) \mbox{ i } f(e_i)>0$$ (8.12)

Inaczej mówiąc: wartość przepływu jest mniejsza od przepustowości na wszystkich łukach zgodnych i dodatnia na niezgodnych łukach ścieżki $P$.
Gdyby $t$ należało do $W$, to istniałaby ścieżka $P$ z $s$ do $t$ (tj. taka, że $x_0=s$ i $x_k=t$) spełniająca warunki ()-(). Niech

$$\varepsilon_1=\mbox{min}\{ c(e_i)-f(e_i) \vert e_i - \mbox{ łuk zgodny } P \}$$

$$\varepsilon_2 = \mbox{min}\{ c(e_i) \vert e_i - \mbox{ łuk niezgodny } P \}$$

oraz

$$\varepsilon = \mbox{min}\{ \varepsilon_1,\varepsilon_2\}$$

Jest oczywistym, że $\varepsilon > 0$, i że dodając $\varepsilon$ do funkcji przepływu na łukach ścieżki $P$ zgodnych i odejmując $\varepsilon$ na łukach ścieżki $P$ niezgodnych, inaczej mówiąc: definiując funkcję

$$\tilde{f}(e) = \left\{ \begin{array}{ll} f(e) & \mbox{ je... ...{ jeślo $e$\ jest łukiem niezgodnym } P \end{array} \right.$$

otrzymalibyśmy nową funkcję przepływu której wartość wynosiłaby $w(\tilde{f})=w(f)+\varepsilon > w(f)$ co byłoby sprzeczne z maksymalnościa przepływu $f$.
Stąd wynika, że $t$ nie jest elementem zbioru $W$ i zbiór $W$ ma następujące własności:

1. $s \in W$
2. $t\notin W$
3. jeśli $(x,y) \in A, x \in W, y \in \bar{W}$ to $f(x,t)=c(x,y)$
4. jeśli $(x,y) \in A, x \in \bar{W}, y \in W$ to $f(x,y)=0$

Wobec (1) i (2) $(W,\bar{W})$ jest przekrojem rozdzielającym $s$ i $t$. Łuki spełniające (3) nazywają sie nasyconymi , a takie które spełniają (4) wyschniętymi. Wobec (3) i (4) mamy

$$c(W,\bar{W})=\sum_{x\in W, y\in \bar{W}}c(x,y) = \sum_{x \in W, y\in \bar{W}}f(x,y)$$

$$= \sum_{x \in W, y \in \bar{W}}f(x,y) - \sum_{x \in \bar{W},y \in W}f(x,y) = w(f)$$

co wobec twierdzenia dowodzi, że $(W,\bar{W})$ jest przekrojem o przepustowości minimalnej.