Metoda Forda-Fulkersona

Metoda Forda-Fulkersona jest stosowana do znajdowania maksymalnego przepływu w sieci przepływowej. Stanowi podstawę wielu algorytmów, między innymi algorytmu Edmondsa-Karpa czy algorytmu Dynica

Zasadę jej działania można streścić w następujący sposób: Należy zwiększać przepływ wzdłuż dowolnej ścieżki ze źródła do ujścia, dopóki jest to możliwe.

Pojęcia

Dla dowolnej sieci przepływowej ${\displaystyle G=(V,E)}$ o źródle ${\displaystyle s}$ i ujściu ${\displaystyle t,}$ w której dowolna krawędź ${\displaystyle (u,v)}$ należąca do zbioru ${\displaystyle E}$ ma przepustowość ${\displaystyle c(u,v)}$ oraz przepływ ${\displaystyle f}$ definiuje się następujące pojęcia:

Sieć rezydualna

Siecią rezydualną dla sieci przepływowej ${\displaystyle G}$ nazywamy sieć ${\displaystyle G_{f}=(V,E_{f}),}$ gdzie ${\displaystyle E_{f}}$ jest zdefiniowane następująco:

${\displaystyle E_{f}=\left\{(u,v)\in V\times V:c_{f}(u,v)>0\right\}}$

gdzie ${\displaystyle c_{f}(u,v)}$ oznacza tzw. przepustowość rezydualną dla krawędzi ${\displaystyle (u,v).}$ Ta natomiast jest dana wzorem:

${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$

Krawędzie należące do ${\displaystyle E_{f}}$ nazywa się krawędziami rezydualnymi.

Bardziej intuicyjnie, przepustowość rezydualna dla pewnej krawędzi ${\displaystyle (u,v)}$ oznacza, o ile można zwiększyć przepływ przez nią, tak jednak, aby nie przekroczył on jej przepustowości. Do sieci rezydualnej natomiast należą te krawędzie, przez które przepływ można zwiększyć.

Należy zwrócić uwagę, że może zachodzić

${\displaystyle c_{f}(u,v)>c(u,v).}$

Ma to miejsce w przypadku, gdy ${\displaystyle f(u,v)<0.}$ W szczególności, do ${\displaystyle E_{f}}$ mogą należeć krawędzie nienależące do ${\displaystyle E.}$

Ścieżka powiększająca

Ścieżką powiększającą dla sieci ${\displaystyle G}$ nazywamy dowolną ścieżkę z ${\displaystyle s}$ do ${\displaystyle t}$ w sieci rezydualnej dla ${\displaystyle G.}$ Przepustowość rezydualną dowolnej ścieżki powiększającej ${\displaystyle p}$ dla sieci ${\displaystyle G}$ określamy wzorem:

${\displaystyle c_{f}(p)=\min \left\{c_{f}(u,v):(u,v)\in p\right\}}$

Jest to wartość, o jaką maksymalnie można zwiększyć przepływ przez wszystkie krawędzie należące do ścieżki ${\displaystyle p.}$

Algorytm

Poniżej przedstawiono zapis metody Forda-Fulkersona w pseudokodzie:

while istnieje pewna ścieżka powiększająca ${\displaystyle p\in G_{f}}$ do
    for each ${\displaystyle (u,v)\in p}$ do
        ${\displaystyle f(u,v):=f(u,v)+c_{f}(p)}$
        ${\displaystyle f(v,u):=f(v,u)-c_{f}(p)}$

Złożoność czasowa

Złożoność czasowa metody Forda-Fulkersona silnie zależy od sposobu wyszukiwania ścieżki powiększającej ${\displaystyle p.}$ Można jednak znaleźć jej górne ograniczenie. Zauważmy, że za każdym razem, gdy taka ścieżka zostanie znaleziona, przepływ ze źródła do ujścia zostanie zwiększony co najmniej o 1. Niech ${\displaystyle f_{max}}$ oznacza maksymalny przepływ w sieci ${\displaystyle G.}$ Wtedy pętla while zostanie wykonana w co najwyżej ${\displaystyle |f_{max}|}$ iteracjach. Ponieważ na ścieżce ${\displaystyle p}$ może leżeć co najwyżej ${\displaystyle |E|}$ krawędzi, dla każdej takiej ścieżki pętla for each zostanie zakończona po nie więcej, niż ${\displaystyle |E|}$ przebiegach. Ponieważ również wyszukiwanie ścieżki powiększającej można zrealizować w czasie ${\displaystyle O(E),}$ złożoność czasowa metody Forda-Fulkersona, to ${\displaystyle O\left(Ef_{max}\right).}$

W rzeczywistości, jedna z popularniejszych implementacji tej metody, algorytm Edmondsa-Karpa ma złożoność ${\displaystyle O(VE^{2}).}$

Przykład

Poniższy przykład przedstawia początkowe kroki metody Forda-Fulkersona w sieci z 4 wierzchołkami, źródłem A oraz ujściem D. Ścieżki powiększające są wyszukiwane za pomocą przeszukiwania w głąb, w którym sąsiadujące wierzchołki są odwiedzane w kolejności alfabetycznej. Jest to najgorszy możliwy przypadek, gdyż w każdej iteracji pętli głównej procedury przepływ jest powiększany tylko o 1.

Ścieżka	Przepustowość	Otrzymany przepływ
	Sytuacja początkowa
${\displaystyle A,B,C,D}$	${\displaystyle {\begin{aligned}&\min \left\{c_{f}(A,B),c_{f}(B,C),c_{f}(C,D)\right\}\\={}&\min \left\{c(A,B)-f(A,B),c(B,C)-f(B,C),c(C,D)-f(C,D)\right\}\\={}&\min \left\{1000-0,1-0,1000-0\right\}=1\end{aligned}}}$
${\displaystyle A,C,B,D}$	${\displaystyle {\begin{aligned}&\min \left\{c_{f}(A,C),c_{f}(C,B),c_{f}(B,D)\right\}\\={}&\min \left\{c(A,C)-f(A,C),c(C,B)-f(C,B),c(B,D)-f(B,D)\right\}\\={}&\min \left\{1000-0,0-(-1),1000-0\right\}=1\end{aligned}}}$
	${\displaystyle \dots }$
	Sytuacja końcowa

Warto zwrócić uwagę, w jaki sposób przepływ „wraca” z wierzchołka C do B po wykorzystaniu ścieżki A,C,B,D.

Bibliografia

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Wprowadzenie do algorytmów, WNT 2004, ​ISBN 83-204-2879-3​.