Zaawansowane algorytmy i struktury danych/Wykład 9

From Studia Informatyczne

Spis treści

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) \ge 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 \mathcal{R}_+ będzie dla niej funkcją przypisującą przepustowości. Przepływem w G nazwiemy funkcję f:V \times V \to \mathcal{R} 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:
    \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' będzie przepływem w G_f. Wtedy suma przepływów f + f' jest przepływem w G o wartości |f + f'| = |f| + |f'|.

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:
\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'(u, v) \le c_f(u, v) dla wszystkich u, v \in V i dlatego:

(f + f')(u, v) = f(u, v) + f'(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:

\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' wynosi:

\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}
image:End_of_proof.gif

Ś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.



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) \mbox{ 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{cases} c_f(p) & \mbox{jeżeli } (u,v) \mbox{ jest na } p,\\ -c_f(p) & \mbox{jeżeli } (v,u) \mbox{ jest na } p,\\ 0 & \mbox{w przeciwnym przypadku}. \end{cases}      (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' : V \times V \to \mathcal{R} jako f' = f + f_p, wówczas f' jest przepływem w G o wartości |f'| = |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.



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|.
image:End_of_proof.gif

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)
image:End_of_proof.gif

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 : \mbox{ istnieje ścieżka z } s \mbox{ do } v \mbox{ 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. image:End_of_proof.gif

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.



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.

Nawigacja