Zaawansowane algorytmy i struktury danych/Wykład 10

Abstrakt

W wykładzie tym przedstawimy trzy algorytmy znajdowania przepływu w grafie. Pierwszym będzie algorytm Edmondsa-Karpa działający w czasie $O(n{m}^2)$. Następnym będzie algorytm Dinica działający w czasie $O(n^{2}m)$, oraz trzecim tak zwany algorytm trzech Hindusów, działający w czasie $O(n^3)$. Nazwiska tych tytułowych Hindusów to Malhotra, Kumar i Maheshwari. Dwa ostatnie algorytmy oparte będą na konstrukcji przepływów blokujących, które są analogiczną konstrukcją do konstrukcji maksymalnego zbioru rozłącznych ścieżek, której użyliśmy w algorytmie Hopcrofta-Karpa.

Algorytm Edmonds’a-Karp’a

Algorytm Edmonds'a-Karp'a to algorytm Forda-Fulkersona w, którym zamiast dowolnej ścieżki powiększającej wybieramy zawsze najkrótszą ścieżkę powiększającą. Zakładamy tutaj, że wszystkie krawędzie mają jednostkowe długości. Taka modyfikacja pozwala poprawić ograniczenie w czasie działania tego algorytmu. Udowodnimy, że algorytm Edmonds’a–Karp’a działa w czasie $O(n{m}^2)$. W naszej analizie będziemy korzystać z zapisu $d_f(u,v)$ dla odległości z $u$ do $v$ w $G_f$, przy założenie, że każda krawędź ma jednostkową wagę.

Lemat 1

Jeśli algorytm Edmondsa–Karpa działa w sieci przepływowej $G=(V,E)$ ze źródłem $s$ i ujściem $t$, to wtedy dla wszystkich wierzchołków $v\in V-\{s,t\}$, odległość $d_f(s,v)$ w sieci rezydualnej $G_f$ nie maleje.

Dowód

Przypuśćmy, że dla pewnego wierzchołka $v\in V-\{s,t\}$ istnieje powiększający przepływ, który powoduje zmniejszenie odległości najkrótszej ścieżki z $s$ do $v$, a następnie otrzymamy wynik sprzeczny z tym założeniem. Niech $f$ będzie przepływem zaraz przed pierwszym powiększeniem, które skraca długość najkrótszej ścieżki i niech $f^{\prime }$ będzie przepływem następującym zaraz potem. Niech $v$ będzie wierzchołkiem o minimalnym $d_{f^{\prime }}(s,v)$, którego dystans został zmniejszony poprzez to powiększenie tak, że $d_{f^{\prime }}(s,v)<d_f(s,v)$. Niech $p=s\to u\to v$ będzie najkrótszą ścieżką z $s$ do $v$ w $G_{f^{\prime }}$, tak że $(u,v)\in E_{f^{\prime }}$ oraz:

$d_{f^{\prime }}(s,u)=d_{f^{\prime }}(s,v)-1$

Ze względu na sposób wybrania $v$, wiemy że odległość z wierzchołka $u$ się nie zmniejszyła, to znaczy:

$d_{f^{\prime }}(s,u)\ge d_f(s,u)$

Twierdzimy, że $(u,v)\notin E_f$. Dlaczego? Gdybyśmy mieli $(u,v)\in E_f$, wówczas z nierówności trójkąta dla $s,v$ i $u$ oraz powyższych nierówności wynikałoby:

$d_f(s,v)\le d_f(s,u)+1\le d_{f^{\prime }}(s,u)+1\le d_{f^{\prime }}(s,v)$

Co jest sprzeczne z założeniem, że $d_{f^{\prime }}(s,v)<d_f(s,v)$. Jak możemy zatem otrzymać $(u,v)\notin E_f$ i $(u,v)\in E_{f^{\prime }}$? Powiększeniu przepływu z $f$ do $f^{\prime }$ powinno także powiększyć przepływ z $v$ do $u$. Algorytm Edmondsa–Karpa zawsze powiększa przepływ wzdłuż najkrótszych ścieżek i dlatego też najkrótsza ścieżka z $s$ do $u$ w $G_f$ posiada $(v,u)$ jako ostatnią krawędź. Dlatego mamy:

$d_f(s,v)=d_f(s,u)-1=d_{f^{\prime }}(s,u)-2=d_{f^{\prime }}(s,v)-2$

co jest sprzeczne z założeniem, że $d_{f^{\prime }}(s,v)<d_f(s,v)$. Wnioskujemy zatem, że założenie, iż taki wierzchołek $v$ istnieje, jest nieprawdziwe.

Następujące twierdzenie ogranicza liczbę iteracji algorytmu Edmondsa–Karpa.

Twierdzenie 2

Jeśli algorytm Edmondsa–Karpa działa w sieci przepływowej $G=(V,E)$ ze źródłem $s$ i ujściem $t$, wówczas całkowita liczba przepływów powiększających znalezionych w algorytmie wynosi $O(VE)$.

Dowód

Mówimy, że krawędź $(u,v)$ w sieci rezydualnej $G_f$ jest krytyczna na ścieżce powiększającej $p$, jeśli przepustowość rezydualna $p$ jest przepustowością rezydualną $(u,v)$, to znaczy jeśli $c_f(p)=c_f(u,v)$. Po tym, jak otrzymamy powiększający przepływ wzdłuż ścieżki powiększającej, każda krawędź krytyczna na ścieżce znika z sieci rezydualnej. Ponadto co najmniej jedna krawędź na dowolnej ścieżce musi być krytyczna. Pokażemy, że każda z $|E|$krawędzi może stać się krytyczna co najwyżej $|V|/2-1$ razy.

Niech $u$ i $v$ będą wierzchołkami w $V$ połączonymi krawędzią $E$. Ponieważ ścieżki powiększające są najkrótszymi ścieżkami, to dla kawędzi krytycznej $(u,v)$, otrzymujemy

$d_f(s,v)=d_f(s,u)+1$

Gdy tylko przepływ jest zwiększony, krawędź $(u,v)$ znika z sieci rezydualnej. Nie może ona się znów pojawić na żadnej innej ścieżce powiększającej dopóki przepływ z $u$ do $v$ nie będzie zmniejszony, a nastąpi to tylko wtedy, kiedy $(v,u)$ pojawi się na ścieżce powiększającej. Jeśli $f^{\prime }$ jest przepływem w $G$ i to zdarzenie ma miejsce, wówczas mamy:

$d_{f^{\prime }}(s,u)=d_{f^{\prime }}(s,v)+1$

Ponieważ $d_f(s,v)\le d_{f^{\prime }}(s,v)$, co wynika z lematu 1, otrzymujemy

$d_{f^{\prime }}(s,u)=d_{f^{\prime }}(s,v)+1\ge d_f(s,v)+1=d_f(s,u)+2$

Czyli od czasu, kiedy $(u,v)$ stało sie krytyczne, do czasu kiedy ponownie stanie się krytyczne, dystans ze źródła do $u$ zwiększa się o co najmniej $2$. Dystans do $u$ wynosi początkowo co najmniej $0$. Wierzchołki pośrednie na najkrótszej ścieżce z $s$ do $u$ nie mogą zawierać $s$, $u$ ani $t$ (ponieważ to, że $(u,v)$ jest krytyczna oznacza, że $u\ne t$). Dlatego też odległość do $u$ może wynosić co najwyżej $|V|-2$. Stąd $(u,v)$ może stać sie krytyczne co najwyżej $(|V|-2)/2=|V|/2-1$ razy. Ponieważ istnieje $O(|E|)$ par wierzchołków pomiędzy którymi może istnieć krawędź w grafie rezydualnym, to całkowita liczba krawędzi krytycznych podczas działania algorytmu Edmondsa–Karpa wynosi $O(|V||E|)$, bo każda ścieżka powiększająca ma co najmniej jedną krawędź krytyczną.

Ponieważ każdą iterację algorytmu FORD-FULKERSON można zaimplementować w czasie $O(|E|)$, to całkowity czas działania algorytmu Edmondsa-Karpa wynosi $O(|V||E{|}^2)$. W następnych częściach wykładu pokażemy, jak wykorzystując przepływy blokujące poprawić ten wynik do czasu $O(|V{|}^3)$.

Przepływ blokujący

Przepływem blokującym w sieci rezydualnej $G_f$ nazywamy taki przepływ $b$ w $G_f$, że:{{{2}}}

1. każda ścieżka z $s$ do $t$ w $b$ jest najkrótszą ścieżką w $G_f$,
2. oraz każda najkrótsza ścieżka w $G_f$ zawiera krawędź nasyconą w $G_{f+b}$.

Zauważ, że jest to definicja, która odpowiada pojęciu maksymalnego zbioru najkrótszych ścieżek powiększających użytemu w Wykładzie 7. Załóżmy na chwilę, że mamy algorytm znajdujący przepływ blokujący. Pokażemy jak go wykorzystać do znalezienia przepływu maksymalnego, jest to algorytm Dinica. Algorytmy na znajdowanie przepływu blokującego pokażemy w dalszej części tego wykładu.

Algorytm [Dinica] znajduje przepływ maksymalny w grafie $G$

---

 DINIC$(G,s,t)$
 1  $f=0$
 2  while istnieje ścieżka od $s$ do $t$ w $G_f$ do
 3  begin
 4    znajdź przepływ blokujący $b$ w $G_f$
 5    $f=f+b$
 6  end
 7  return $f$

Poprawność algorytmu Dinica wynika bezpośrednio z twierdzenia o maksymalnym przepływie i minimalnym przekroju, gdyż po zakończeniu algorytmu nie ma już w sieci $G$ ścieżek powiększających. Zastanówmy się teraz, ile razy może zostać wykonana pętla while, czyli innymi słowy ile razy będzie konieczne znalezienie przepływu blokującego.

Lemat 3

Niech $b$ będzie przepływem blokującym w $G_f$, wtedy długość najkrótszej ścieżki powiększającej w $G_{f+b}$ jest większa niż długość najkrótszej ścieżki powiększającej w $G_f$.

Dowód

Załóżmy, że długość najkrótszej ścieżki $p$ w $G_{f+b}$ jest nie większa niż długość najkrótszej ścieżki w $G_f$. Wtedy ścieżka $p$ ma z przepływem blokującym $b$ wspólną krawędź nasyconą. Niech $u-v$ będzie ostatnią taką krawędzią na $p$. Oznacza to, że krawędź $v-u$ musiała należeć do przepływu $b$. Inaczej w $G_{f+b}$ krawędź $u-v$ nadal byłaby nasycona. Ponieważ $b$ może zostać rozłożone na sumę pewnych najkrótszych ścieżek w $G_f$, to z lematu 1, wiemy, że odległość z $s$ do $u$ nie zmalała, tzn. $d_f(s,u)\le d_{f+b}(s,u)$. Jednak ponieważ $p$ jest najkrótszą ścieżką z $s$ do $t$, oznacza to, że odległość do $v$ wzrosła o co najmniej $2$, $d_f(s,v)+2\le d_{f+b}(s,v)$. Kawałek ścieżki $p$ od $v$ do $t$ też jest najkrótszą ścieżką, więc $d_f(s,t)+2\le d_{f+b}(s,t)$. Długość najkrótszej ścieżki w grafie rezydualnym musiała więc wzrosnąć.

Wniosek 4

Ponieważ maksymalna długość najkrótszej ścieżki może wynosić co najwyżej $n-1$, maksymalna liczba faz w algorytmie Dinica wynosi $n$.

Znajdowanie przepływu blokującego - Algorytm Dinica

Zanim przejdziemy do opisu algorytmów znajdujących przepływ blokujący, wprowadźmy pojęcie sieci warstwowej. Sieć warstwową ${\bar{G}}_f$ dla sieci rezydualnej $G_f=(V,E_f)$ definiujemy jako graf skierowany ${\bar{G}}_f=(V,{\bar{E}}_f)$ o następującym zbiorze krawędzi:

${\bar{E}}_f=\{(u,v):(u,v)\in E_f\text{ i }{d}_f(s,u)+1=d_f(s,v)\}.$

Zauważmy, że wszystkie ścieżki w ${\bar{G}}_f$ z $s$ do $t$ są najkrótszymi ścieżkami. Jeżeli chcemy wyszukać przepływ blokujący, to zauważmy, że robiąc to w sieci warstwowej, będziemy mieli spełniony automatycznie warunek 1 definicji przepływu blokującego. W grafie ${\bar{G}}_f$ wszystkie ścieżki są najkrótsze, jednak nie wszystkie ścieżki muszą prowadzić do $t$. Jeżeli usuniemy zawczasu z grafu ${\bar{G}}_f$ krawędzie, które prowadzą donikąd, to ścieżki z $s$ do $t$ będziemy mogli wyszukiwać w czasie $O(n)$.

Algorytm [Dinica] znajduje przepływ blokujący w grafie $G_f$

---

 DINIC-PRZEPŁYW-BLOKUJĄCY$(G_f,s,t)$
 1  $b=0$
 2  skonstruuj graf ${\bar{G}}_f$
 3  while ${\bar{E}}_f\ne \mathrm{\varnothing }$ do
 4  begin
 5    znajdź ścieżkę $p$ z $s$ do $t$ w ${\bar{G}}_f$
 6    for każda krawędź $(u,v)\in p$ do
 7    begin
 8      $b(u,v)=b(u,v)+c_f(p)$
 9      $b(v,u)=-b(u,v)$
 10     usuń rekurencyjnie $u$ i inne wierzchołki jeżeli nie wychodzi z nich żadna krawędź residualna 
 11 end
 12 return $b$

Działanie tego algorytmu zobrazowane jest na następującej animacji.

Plik:Zasd ilustr p.svg

Zauważmy, że po zakończeniu działania algorytmu, w grafie ${\bar{G}}_f$ nie pozostanie żadna ścieżka z $s$ do $t$. Skonstruowany przepływ będzie więc przepływem blokującym.

Główna pętla programu w liniach 5-17 wykonana zostanie co najwyżej $m$ razy, bo w każdym jej przebiegu nasycana jest co najmniej jedna krawędź. Pętlę tę można zaimplementować tak, aby działała w czasie $O(n)$, dlatego całkowity czas działania tej procedury wynosi $O(nm)$. Korzystając z Wniosku 4 widzimy, że czas działania algorytmu Dinica wynosi $O(m{n}^2)$.

Znajdowanie przepływu blokującego - Algorytm trzech Hindusów

W algorytmie tym użyjemy pojęcia przepustowości wierzchołka w sieci $G$, którą definiujemy jako:

$c(v)=\min \{\sum _{u\in V}c(u,v),\sum _{u\in V}c(v,u)\}$.

W algorytmie trzech Hindusów, który nazywany jest też algorytmem MKM (od nazwisk autorów), będziemy w każdym wykonaniu głównej pętli algorytmu nasycać jeden wierzchołek, przesyłając z niego przepływ do przodu i w pewnym sensie do tyłu. W czasie wykonywania pętli funkcja $f$ przestanie spełniać warunek zachowania przepływu, jednak pod koniec ten warunek zostanie przywrócony. Użyjemy tutaj dwóch pomocniczych procedur:

• procedury PRZEŚLIJ$(v)$ - jeżeli do wierzchołka $v$ wpływa większy przepływ niż wypływa, to procedura ta przesyła ten nadmiar do przodu w grafie ${\bar{G}}_f$, nasycając po kolei krawędzie wychodzące z $v$,
• procedury COFNIJ$(v)$ - jeżeli z wierzchołka $v$ wypływa więcej niż do niego wpływa, to procedura ta kompensuje ten niedomiar, przesyłając przepływ z wierzchołków, z których istnieją w ${\bar{G}}_f$ krawędzie do $v$, nasycając po kolei krawędzie wchodzące do $v$.

Algorytm [Malhotra, Kumar i Maheshwari] znajduje przepływ blokujący w grafie $G_f$

---

 MKM-PRZEPŁYW-BLOKUJĄCY$(G_f,s,t)$
 1  $b=0$
 2  skonstruuj graf ${\bar{G}}_f$
 3  while ${\bar{E}}_f\ne \mathrm{\varnothing }$ do
 4  begin
 5    znajdź wierzchołek o najmniejszym $c(v)$
 6    prześlij $c(v)$ jednostek przepływu krawędziami wychodzącymi z $v$
 7    prześlij $c(v)$ jednostek przepływu krawędziami wchodzącymi do $v$
 8    for $i=d(s,v)+1$ to $n-1$ do
 9      foreach $w\in \{w\in V:d(s,w)=i\}$ do 
 10       PRZEŚLIJ$(w)$
 11   for $i=d(s,v)-1$ downto $1$ do
 12     foreach $w\in \{w\in V:d(s,w)=i\}$ do 
 13       COFNIJ$(w)$
 14   usuń $v$ z grafu poprawiając przepustowości wierzchołków sąsiednich
 15 end
 16 return $b$

Działanie tego algorytmu zobrazowane jest na następującej animacji.

Plik:Zasd ilustr q.svg

Zauważmy, że ponieważ wybraliśmy wierzchołek o najmniejszej przepustowości, to zawsze w procedurach PRZEŚLIJ i COFNIJ uda nam się przesłać nadmiar bądź zrekompensować niedomiar w wierzchołku.

Zauważmy, że główna pętla procedury może wykonać się co najwyżej $n-2$ razy, ponieważ za każdym razem nasycany jest co najmniej jeden wierzchołek grafu. Policzmy teraz, ile razy łącznie będą nasycane krawędzie w trakcie wykonywania procedur PRZEŚLIJ i COFNIJ. Co najwyżej $m$ razy będziemy przesyłać przepływ nasycając krawędzie. Natomiast liczba przesłań nie nasycających krawędzi nie przekroczy $O(n^2)$, gdyż dla każdego wierzchołka w wykonaniu procedury PRZEŚLIJ i COFNIJ wykonujemy co najwyżej jedno przesłanie nie nasycające, a operacji tych łącznie wykonywanych jest $O(n^2)$. Czas potrzebny na znalezienie przepływu blokującego wynosi więc $O(n^2)$. Łącząc ten algorytm z algorytmem Dinica, otrzymujemy algorytm znajdujący maksymalny przepływ w grafie w czasie $O(n^3)$.