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

Ograniczenie w czasie działania w algorytmie Forda–Fulkersona może zostać poprawione, kiedy jako ścieżkę powiększającą będziemy wybierać zawsze najkrótszą ścieżkę z $s$ do $t$ w sieci rezydualnej, przy założeniu jednostkowych długości krawędzi. Teraz 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 Parser nie mógł rozpoznać (nieznana funkcja „\v”): {\displaystyle 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:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle d_f(s, v) = d_f(s, u) – 1 = d_{f'} (s, u) - 2 = d_{f'} (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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle |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ą krótszymi ścieżkami, kiedy $(u,v)$ są krytyczne za pierwszym razem, 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)=d_{f^{\prime }}(s,v)$, co wynika z lematu 1, otrzymujemy

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

Czyli od czasu, kiedy $(u,v)$ staje sie krytyczne, do czasu kiedy ponownie staje się krytyczne, dystans $u$ ze źródła zwiększa się o co najmniej $2$. Dystans $u$ ze źródła wynosi początkowo co najmniej $0$. Wierzchołki pośrednie (intermediate) na najkrótszej ścieżce z $s$ do $u$ nie mogą zawierać $s$, $u$ ani $t$ (ponieważ to, że $(u,v)$ jest krytyczna na ścieżce oznacza, że istnieje ścieżka z $u$ do $t$). Dlatego też zanim $u$ stanie się nieosiągalne ze źródła, jeśli kiedykolwiek, jego odległość do niego wynosić będzie 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, które mogą mieć krawędź pomiędzy sobą w grafie rezydualnym, 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}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:

1. każda ścieżka z $s$ do $t$ w $b$ jest najkrótszą ścieżką w $G_d$,
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 w algorytmie 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 znajdowanie 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}$ $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 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}}_M=\{(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 Parser nie mógł rozpoznać (nieznana funkcja „\oveline”): {\displaystyle \oveline{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  for każdy $v\in V$ do
 4    $out(v)=$ liczba krawędzi wychodzących z $v$
 5  while ${\bar{E}}_f\ne \mathrm{\varnothing }$ do
 6  begin
 7    znajdź ścieżkę $p$ z $s$ do $t$ w ${\bar{G}}_f$
 8    for każda krawędź $(u,v)\in p$ do
 9    begin
 10     $b(u,v)=b(u,v)+c_f(p)$
 11     $b(v,u)=-b(u,v)$
 12     if $b(u,v)=c_f(u,v)$ then
 13     begin
 14       $out(u)=out(u)-1$
 15       if $out(u)=0$ then ${\bar{G}}_M={\bar{G}}_m-u$
 16   end
 17 end
 18 return $b$

Działanie tego algorytmu zobrazowane jest na następującej animacji. <flash>file=Zasd_ilustr_p.swf |width=600|height=500</flash>

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 nasycona jest co najmniej jedna krawędź. Pętlę tę można zaimplementować, 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_f$, 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 każdy $w\in V$ do
 9    begin
 10     PRZEŚLIJ(w)
 11     COFNIJ(w)
 12   end
 13   usuń $v$ z grafu poprawiając przepustowości wierzchołków sąsiednich
 13 end
 15 return $b$

Działanie tego algorytmu zobrazowane jest na następującej animacji. <flash>file=Zasd_ilustr_q.swf |width=600|height=500</flash>

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)$.