Zaawansowane algorytmy i struktury danych/Wykład 10

From Studia Informatyczne

Spis treści

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(nm^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(nm^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' będzie przepływem następującym zaraz potem. Niech v będzie wierzchołkiem o minimalnym d_{f'}(s, v), którego dystans został zmniejszony poprzez to powiększenie tak, że d_{f'}(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'}, tak że (u, v) \in E_{f'} oraz:
d_{f'}(s,u) = d_{f'}(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'}(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'} (s, u) + 1 \le  d_{f'} (s, v),

Co jest sprzeczne z założeniem, że d_{f'}(s, v) < d_f(s, v). Jak możemy zatem otrzymać (u, v) \notin E_f i (u, v) \in E_{f'}? Powiększeniu przepływu z f do f' 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'} (s, u) - 2  = d_{f'} (s, v) - 2,
co jest sprzeczne z założeniem, że d_{f'} (s, v) < d_f(s, v). Wnioskujemy zatem, że założenie, iż taki wierzchołek v istnieje, jest nieprawdziwe. image:End_of_proof.gif

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(V E).

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' jest przepływem w G i to zdarzenie ma miejsce, wówczas mamy:

d_{f'}(s, u) = d_{f'}(s, v) + 1.

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

d_{f'}(s, u) = d_{f'}(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 \neq 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ą. image:End_of_proof.gif

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

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ą \overline{G}_f dla sieci rezydualnej G_f = (V,E_f) definiujemy jako graf skierowany \overline{G}_f = (V,\overline{E}_f) o następującym zbiorze krawędzi:

\overline{E}_f = \{(u,v): (u,v) \in E_f \mbox{ i } d_f(s,u) + 1 = d_f(s,v)\}.

Zauważmy, że wszystkie ścieżki w \overline{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 \overline{G}_f wszystkie ścieżki są najkrótsze, jednak nie wszystkie ścieżki muszą prowadzić do t. Jeżeli usuniemy zawczasu z grafu \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 \overline{G}_f
 3  while \overline{E}_f \neq \emptyset do
 4  begin
 5    znajdź ścieżkę p z s do t w \overline{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.



Zauważmy, że po zakończeniu działania algorytmu, w grafie \overline{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(mn^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\left\{ \sum_{u \in V} c(u,v), \sum_{u \in V} c(v,u)  \right\}.

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 \overline{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 \overline{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 \overline{G}_f
 3  while \overline{E}_f \neq \emptyset 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.



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