Zaawansowane algorytmy i struktury danych/Wykład 9

Abstrakt

Wykład ten poświęcony będzie problemowi znajdowania maksymalnego przepływu w grafie. Zaczniemy od wprowadzenia potrzebnych pojęć, a następnie przestawimy metodę Forda-Fulkersona znajdowania maksymalnego przepływu w grafie.

Podstawowe pojęcia

Siecią przepływową, bądź krótko siecią, nazywamy skierowany graf $G=(V,E)$, w którym z każdą krawędzią $(u,v)\in E$ wiążemy jej nieujemną przepustowość $c(u,v)=0$. W sieci przepływowej wyróżniamy dwa wierzchołki: źródło oznaczane jako $s$ oraz ujście oznaczane jako $t$.

Niech $G$ będzie siecią oraz niech $c:E\to {{ℛ}}_{+}$ będzie dla niej funkcją przypisującą przepustowości. Przepływem w $G$ nazwiemy funkcję $f:V\times V\to {ℛ}$ spełniającą następujące właściwości:

• Dla wszystkich $u,v\in V$ zachodzi $f(u,v)\le c(u,v)$ - warunek ten nazywamy warunkiem ograniczenia przepustowości.
• Dla wszystkich $u,v\in V$ zachodzi $f(u,v)=-f(v,u)$ - jest to warunek skośnej symetrii.
• Dla wszystkich $u\in V-\{s,t\}$ żądamy aby zachodził warunek zachowania przepływu:

$\sum _{v\in V}f(u,v)=0.$

O wartości $f(u,v)$ mówimy, że jest to wielkość przepływu z $u$ do $v$. Wartość przepływu $f$, oznaczamy $|f|$ i definiujemy jako sumaryczną wielkość przepływu wypływającego z $s$ wszystkimi krawędziami, tzn.:

$|f|=\sum _{u\in V}f(s,u).$

W problemie maksymalnego przepływu dla danej sieci chcemy znaleźć przepływ o największej wartości.

W dalszej części wykładu używać będziemy następującej notacji sumacyjnej, w której argument funkcji $f:X\to Y$ może być podzbiorem $A$ dziedziny $X$. W takim wypadku przyjmujemy, że wartością funkcji $f$ jest suma jej wartości dla zbioru $A$, tzn.:

$f(X,Y)=\sum _{x\in X}\sum _{y\in Y}f(x,y).$

Używając tej notacji, możemy zapisać warunek zachowania przepływu dla wierzchołka $v$ jako $f(v,V)=0$. W poniższym lemacie używamy tej notacji do zapisania podstawowych właściwości przepływu.

Lemat 1

Niech $G=(V,E)$ będzie siecią przepływową oraz $f$ przepływem w niej. Wtedy:

1. Dla wszystkich $X\subseteq V$ mamy $f(X,X)=0$.
2. Dla wszystkich $X,Y\subseteq V$ mamy $f(X,Y)=-f(Y,X)$.
3. Dla wszystkich $X,Y,Z\subseteq V$ zachodzi:
   Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \begin{array}{r@{}c@{}l} f(X \cup Y,Z) &=& f(X,Z) + f(Y,Z) - f(X \cap Y,Z) \mbox{ i } f(Z, X \cup Y)=\\ &=& f(Z,X) + f(Z,Y) - f(Z,X \cap Y). \end{array}}
4. $|f|=f(s,V)=f(V,t)$.

Dowód tego lematu pozostawiony jest jako Zadanie 1 do tego wykładu.

Sieć rezydualna

Intuicyjnie, dla danej sieci przepływowej $G$ i przepływu $f$, sieć rezydualna składa się z krawędzi, którymi można przesłać większy przepływ. Bardziej formalnie, przypuśćmy, że mamy sieć przepływową $G=(V,E)$ ze źródłem $s$ i ujściem $t$ oraz niech $f$ będzie przepływem w $G$. Rozważmy teraz parę wierzchołków $u,v\in V$. Ilość dodatkowego przepływu $c_f(u,v)$, którą możemy przesłać z $u$ do $v$, zanim przekroczymy przepustowość $c(u,v)$, wynosi

$c_f(u,v)=c(u,v)-f(u,v).$

Na przykład, jeśli $c(u,v)=16$ i $f(u,v)=11$, wtedy możemy zwiększyć $f(u,v)$ o $c_f(u,v)=5$ jednostek, zanim przekroczymy ograniczenie przepustowości krawędzi $(u,v)$.

Dla danej sieci $G=(V,E)$ i przepływu $f$, sieć rezydualna $G$ zaindukowana przez $f$ to graf $G_f=(V,E_f)$, gdzie:

$E_f=\{(u,v)\in V\times V:c_f(u,v)>0\}.$

To znaczy, tak jak napisaliśmy powyżej, że każdą krawędzią sieci rezydualnej lub krawędzią rezydualną można przepuścić przepływ, który jest większy niż 0.

Krawędzie w $E_f$ są albo krawędziami w $E$, albo krawędziami o odwróconym kierunku. Jeśli zachodzi $f(u,v)<c(u,v)$ dla krawędzi $(u,v)\in E$, to wtedy $c_f(u,v)=c(u,v)-f(u,v)>0$ i $(u,v)\in E_f$. Jeśli $f(u,v)>0$ dla krawędzi $(u,v)\in E$, to wtedy $f(v,u)<0$. W tym przypadku, $c_f(v,u)=c(v,u)-f(v,u)>0$, i dlatego $(v,u)\in E_f$. Jeśli ani $(u,v)$ ani $(v,u)$ nie pojawiają się w pierwotnej sieci, to wówczas $c(u,v)=c(v,u)=0$ i $f(u,v)=f(v,u)=0$, a zatem też $c_f(u,v)=c_f(v,u)=0$. Podsumowując, krawędź $(u,v)$ może się pojawić w sieci rezydualnej tylko wtedy, kiedy co najmniej jedna z krawędzi $(u,v)$ i $(v,u)$ jest w pierwotnej sieci. Dlatego też $|E_f|\le 2|E|$. Należy zauważyć, że sieć rezydualna $G_f$ jest także siecią przepływową o przepustowości krawędzi zadanej przez $c_f$. Następujący lemat pokazuje, jak przepływ w rezydualnej sieci powiązany jest z przepływem w pierwotnej sieci przepływów.

Lemat 1

Niech $G=(V,E)$ będzie siecią przepływową ze źródłem $s$ i ujściem $t$ i niech $f$ będzie przepływem w $G$. Niech $G_f$ będzie siecią rezydualną dla $G$, indukowaną przez $f$, i niech $f^{\prime }$ będzie przepływem w $G_f$. Wtedy suma przepływów $f+f^{\prime }$ jest przepływem w $G$ o wartości $|f+f^{\prime }|=|f|+|f^{\prime }|$.

Dowód

Po pierwsze musimy pokazać, że dla sumy przepływów warunki, symetrii skośnej, ograniczenia przepustowości jak i zachowania przepływu są spełnione. W przypadku symetrii skośnej zauważmy, że dla wszystkich $u,v\in V$, mamy:

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \begin{array}{r@{}c@{}l} (f + f')(u, v) &=& f(u, v) + f'(u, v) = -f(v, u) - f'(v, u) =\\&=& -(f(v, u) + f'(v, u))= -(f + f')(v, u). \end{array}}

W przypadku ograniczenia przepustowości zauważmy, ze $f^{\prime }(u,v)\le c_f(u,v)$ dla wszystkich $u,v\in V$ i dlatego:

$(f+f^{\prime })(u,v)=f(u,v)+f^{\prime }(u,v)\le f(u,v)+(c(u,v)-f(u,v))=c(u,v).$

W przypadku warunku zachowania przepływu, należy zauważyć, że dla wszystkich $u\in V-s,t$, mamy:

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \begin{array}{r@{}c@{}l}\sum_{v \in V}(f+f')(u,v) &=& \sum_{v \in V}(f(u,v) + f'(u,v)) =\\&=& \sum_{v\in V}f(u,v) + \sum_{v\in V}f(u,v) = 0 + 0 = 0.\end{array}}

Ostatecznie otrzymujemy, że wartość $f+f^{\prime }$ wynosi:

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \begin{array}{r@{}c@{}l}|f + f'| &=& \sum_{v \in V}(f + f')(s,v) = \sum_{v \in V}(f(s,v) + f'(s,v)) =\\&=& \sum_{v \in V}f(s,v) + \sum_{v\in V}f'(s,v) = |f| + |f'|.\end{array}}

Ścieżki powiększające

Jeśli dana jest sieć przepływowa $G=(V,E)$ i przepływ $f$, wówczas ścieżka powiększająca $p$ jest ścieżką prostą z $s$ do $t$ w rezydualnej sieci $G_f$. Z definicji sieci rezydualnej, każda krawędź $(u,v)$ na ścieżce powiększającej pozwala na przesłanie pewnego dodatkowego przepływu z $u$ do $v$ bez naruszenia ograniczenia przepustowości krawędzi. Znajdowanie ścieżki powiększającej w sieci rezydualnej, a następnie powiększenie przy jej pomocy przepływu zobrazowane jest na następującej animacji.

<flash>file=Zasd_ilustr_l.swf |width=800|height=300</flash>

Najwyższą wartość, o jaką można zwiększyć przepływ przy użyciu ścieżki $p$, nazywamy rezydualną przepustowością $p$. Wielkość ta jest dana przez:

$c_f(p)=\min \{c_f(u,v):(u,v)\text{ jest na }p\}.$

Zdefiniujmy tę zmianę przepływu związaną ze ścieżką $p$ jako funkcję $f_p:V\times V\to R$ równą:

$f_p(u,v)=\{\begin{array}{ll}{c}_f(p)& \text{jeżeli }(u,v)\text{ jest na }p,\\ -c_f(p)& \text{jeżeli }(v,u)\text{ jest na }p,\\ 0& \text{w przeciwnym przypadku}.\end{array}$      (1)

Wówczas $f_p$ jest przepływem w $G_f$ o wartości $|f_p|=c_f(p)>0$. Dodając $f_p$ do $f$, otrzymamy kolejny przepływ w $G$, którego wartość jest bliższa maksimum, co sformułowane jest w tym wniosku.

Wniosek 2

Niech $G=(V,E)$ będzie siecią przepływową, niech $f$ będzie przepływem w $G$ i niech $p$ będzie ścieżką powiększającą w $G_f$. Niech $f_p$ będzie zdefiniowane jak we wzorze 1. Zdefiniujmy funkcję $f^{\prime }:V\times V\to {ℛ}$ jako $f^{\prime }=f+f_p$, wówczas $f^{\prime }$ jest przepływem w $G$ o wartości $|f^{\prime }|=|f|+|f_p|>|f|$.

Przekroje w sieci

Twierdzenie o maksymalnym przepływie i minimalnym przekroju, które za chwilę udowodnimy, pokazuje że przepływ jest maksymalny wtedy i tylko wtedy, kiedy jego sieć rezydualna nie zawiera żadnej ścieżki powiększającej. Jednak, aby udowodnić to twierdzenie, musimy wpierw wprowadzić pojęcie przekroju sieci przepływowej. Przekrój $(S,T)$ sieci przepływowej $G=(V,E)$ jest podziałem $V$ na $S$ i $T=V-S$ tak, że $s\in S$ i $t\in T$. Jeśli $f$ jest przepływem, wtedy przepływ netto poprzez przekrój $(S,T)$ jest zdefiniowany jako $f(S,T)$. Przepustowość przekroju $(S,T)$ definiujemy jako $c(S,T)$. Minimalnym przekrojem sieci jest przekrój, którego przepustowość jest najmniejsza ze wszystkich przekrojów w sieci.

Poniższa ilustracja pokazuje przekrój $(\{s,v_1,v_2\},\{v_3,v_4,t\})$ w sieci przepływów. Przepływ netto poprzez ten przekrój wynosi: $f(v_1,v_3)+f(v_2,v_3)+f(v_2,v_4)=12+(-4)+11=19$, a jego przepustowość wynosi $c(v_1,v_3)+c(v_2,v_4)=12+14=26$.

<flash>file=Zasd_ilustr_b.swf |width=800|height=250</flash>

Należy zaobserwować, że przepływ netto w przekroju może zawierać negatywny przepływy pomiędzy wierzchołkami, jednakże przepustowość przekroju składa się wyłącznie z nieujemnych wartości. Innymi słowy, przepływ netto poprzez przekrój $(S,T)$ składa się z dodatnich przepływów płynących w dwa kierunki; dodatni przepływ z $S$ do $T$ jest dodawany, podczas gdy dodatni przepływ z $T$ do $S$ jest odejmowany. Z drugiej strony, przepustowość przekroju $(S,T)$ jest obliczana tylko od krawędzi odchodzących z $S$ do $T$. Krawędzie biegnące z $T$ do $S$ nie są włączone do obliczeń $c(S,T)$. Powyższy lemat pokazuje, że przepływ netto przez jakikolwiek przekrój jest taki sam i równy jest wartości przepływu.

Lemat 3

Nich $f$ będzie przepływem w sieci przepływów $G$ ze źródłem $s$ i ujściem $t$ i niech $(S,T)$ będzie przekrojem w $G$. Wtedy przepływ netto przez $(S,T)$ wynosi $f(S,T)=|f|$.

Dowód

Zauważmy, że $f(S-s,V)=0$ z warunku zachowania przepływu, dlatego:

$f(S,T)=f(S,V)-f(S,S)=f(s,V)+f(S-s,V)=f(s,V)=|f|.$

Jako w wniosek z tego lematu otrzymujemy, że przepustowość przekroju jest graniczeniem wartości przepływu.

Wniosek 4

Wartość dowolnego przepływu $f$ w sieci przepływów $G$ jest ograniczona z góry przez przepustowość dowolnego przekroju w $G$.

Dowód

3

Niech $(S,T)$ będzie dowolnym przekrojem w $G$ i niech $f$ będzie dowolnym przepływem. Z lematu 3 i warunku ograniczenia przepustowości otrzymujemy:

$|f|=f(S,T)=\sum _{u\in S}\sum _{v\in T}f(u,v)\le \sum _{u\in S}\sum _{v\in T}c(u,v)=c(S,T)$

W szczególności maksymalny przepływ w sieci jest ograniczony od góry przez przepustowość najmniejszego przekroju w sieci. Twierdzenie o maksymalnym przepływie i minimalnym przekroju, które teraz postawimy i udowadnimy, mówi że wartość maksymalnego przepływu jest w rzeczywistości równa przepustowości najmniejszego przekroju.

Twierdzenie 5 [O maksymalnym przepływie i minimalnym przekroju]

Jeśli $f$ jest przepływem w sieci przepływowej $G=(V,E)$ ze źródłem $s$ i ujściem $t$, wówczas następujące warunki są równoważne:

1. $f$ jest maksymalnym przepływem w $G$.
2. Sieć rezydualna $G_f$ nie zawiera żadnych ścieżek powiększających.
3. $|f|=c(S,T)$ dla pewnego przekroju $(S,T)$ w $G$.

Dowód

(1)$\to$(2): Załóżmy przez sprzeczność, że $f$ jest maksymalnym przepływem w $G$, ale że $G_f$ posiada ścieżkę powiększającą $p$. Wówczas, z wniosku 2, suma przepływów $f+f_p$, gdzie $f_p$ jest dane wzorem 1, jest przepływem w $G$ o wartości ściśle większej niż $|f|$, co jest sprzeczne z założeniem, że $f$ jest przepływem maksymalnym.

(2)$\to$(3): Przypuśćmy, że $G_f$ nie posiada żadnej ścieżki powiększającej, to znaczy że $G_f$ nie posiada żadnej ścieżki z $s$ do $t$. Zdefiniujmy:

$S=\{v\in V:\text{ istnieje ścieżka z }s\text{ do }v\text{ w }{G}_f\}$,

oraz:

$T=V-S$.

Podział $(S,T)$ jest przekrojem: oczywiście $s\in S$ i $t\in T$, ponieważ nie ma żadnej ścieżki z $s$ do $t$ w $G_f$. Dla każdej pary wierzchołków $u\in S$ i $v\in T$, mamy $f(u,v)=c(u,v)$, gdyż w przeciwnym wypadku $(u,v)\in E_f$, co umiejscowiłoby $v$ w zbiorze $S$. Dlatego też, z lematu 3, mamy $|f|=f(S,T)=c(S,T)$.

(3)$\to$(1): Z wniosku 4 wiemy, że $|f|\le c(S,T)$ dla wszystkich przekrojów $(S,T)$. Czyli warunek $|f|=c(S,T)$ oznacza, że $f$ jest przepływem maksymalnym.

Algorytm Forda – Fulkersona

W każdej iteracji metody Forda–Fulkersona odnajdujemy dowolną ścieżkę powiększającą $p$ i zwiększamy przepływ $f$ na każdej krawędzi $p$ o przepustowość rezydualną $c_f(p)$. Poniżej zamieszczamy implementacje tej metody.

Algorytm [Forda-Fulkersona] znajduje przepływ maksymalny w grafie $G$

---

 FORD-FULKERSON($G=(V,E),s,t$)
 1 for każda krawędź $(u,v)\in E$ do
 2 begin
 3   $f(u,v)=0$
 4   $f(v,u)=0$
 5  end
 6  while istnieje ścieżka $p$ z $s$ do $t$ w sieci rezydualnej $G_f$ do
 7  begin
 8    $c_f(p)=\min \{c_f(u,v):(u,v)\in p\}$
 9    for każda krawędź $(u,v)\in p$ do
 10   begin
 11     $f(u,v)=f(u,v)+c_f(p)$
 12     $f(v,u)=-f(u,v)$
 13   end
 14 end
 15 return $f$

Działanie tego algorytmu przestawione jest na następującej animacji. <flash>file=Zasd_ilustr_r.swf |width=800|height=300</flash>

Czas działania metody Forda-Fuklersona zależy od wyboru ścieżki powiększającej. Jeżeli będziemy ją wybierać źle, to algorytm wręcz może się nie zakończyć. W przypadku, gdy przepustowości krawędzi są całkowito liczbowe, to łatwo możemy pokazać, że czas działania tego algorytmu wynosi $O(E|f^{*}|)$, gdzie $f^{*}$ jest przepływem maksymalnym w sieci. Jeżeli przepływ $f^{*}$ jest mały, to algorytm ten działa szybko, jednak może się zdarzyć, nawet dla prostego przykładu, że algorytm będzie musiał wykonać $f^{*}$ iteracji. Taki przykład pokazany jest na poniższej animacji.

<flash>file=zasd_ilustr_e.swf |width=800|height=300</flash>