Zaawansowane algorytmy i struktury danych/Wykład 10

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Abstrakt

W wykładzie tym przedstawimy trzy algorytmy znajdowania przepływu w grafie. Pierwszym będzie algorytm Edmondsa-Karpa działający w czasie . Następnym będzie algorytm Dinica działający w czasie , oraz trzecim tak zwany algorytm trzech Hindusów, działający w czasie . 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 . W naszej analizie będziemy korzystać z zapisu dla odległości z do w , 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 ze źródłem i ujściem , to wtedy dla wszystkich wierzchołków , odległość w sieci rezydualnej nie maleje.

Dowód

Przypuśćmy, że dla pewnego wierzchołka istnieje powiększający przepływ, który powoduje zmniejszenie odległości najkrótszej ścieżki z do , a następnie otrzymamy wynik sprzeczny z tym założeniem. Niech będzie przepływem zaraz przed pierwszym powiększeniem, które skraca długość najkrótszej ścieżki i niech będzie przepływem następującym zaraz potem. Niech będzie wierzchołkiem o minimalnym , którego dystans został zmniejszony poprzez to powiększenie tak, że . Niech będzie najkrótszą ścieżką z do w , tak że oraz:

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

Twierdzimy, że . Dlaczego? Gdybyśmy mieli , wówczas z nierówności trójkąta dla i oraz powyższych nierówności wynikałoby:

Co jest sprzeczne z założeniem, że . Jak możemy zatem otrzymać i ? Powiększeniu przepływu z do powinno także powiększyć przepływ z do . Algorytm Edmondsa–Karpa zawsze powiększa przepływ wzdłuż najkrótszych ścieżek i dlatego też najkrótsza ścieżka z do w posiada jako ostatnią krawędź. Dlatego mamy:

co jest sprzeczne z założeniem, że . Wnioskujemy zatem, że założenie, iż taki wierzchołek istnieje, jest nieprawdziwe. 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 ze źródłem i ujściem , wówczas całkowita liczba przepływów powiększających znalezionych w algorytmie wynosi .

Dowód

Mówimy, że krawędź w sieci rezydualnej jest krytyczna na ścieżce powiększającej , jeśli przepustowość rezydualna jest przepustowością rezydualną , to znaczy jeśli . 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 krawędzi może stać się krytyczna co najwyżej razy.

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

Gdy tylko przepływ jest zwiększony, krawędź 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 do nie będzie zmniejszony, a nastąpi to tylko wtedy, kiedy pojawi się na ścieżce powiększającej. Jeśli jest przepływem w i to zdarzenie ma miejsce, wówczas mamy:

Ponieważ , co wynika z lematu 1, otrzymujemy

Czyli od czasu, kiedy stało sie krytyczne, do czasu kiedy ponownie stanie się krytyczne, dystans ze źródła do zwiększa się o co najmniej . Dystans do wynosi początkowo co najmniej . Wierzchołki pośrednie na najkrótszej ścieżce z do nie mogą zawierać , ani (ponieważ to, że jest krytyczna oznacza, że ). Dlatego też odległość do może wynosić co najwyżej . Stąd może stać sie krytyczne co najwyżej razy. Ponieważ istnieje 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 , bo każda ścieżka powiększająca ma co najmniej jedną krawędź krytyczną. End of proof.gif

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

Przepływ blokujący

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

  1. każda ścieżka z do w jest najkrótszą ścieżką w ,
  2. oraz każda najkrótsza ścieżka w zawiera krawędź nasyconą w .

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


 DINIC
 1  
 2  while istnieje ścieżka od  do  w  do
 3  begin
 4    znajdź przepływ blokujący  w 
 5    
 6  end
 7  return 

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 ś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ędzie przepływem blokującym w , wtedy długość najkrótszej ścieżki powiększającej w jest większa niż długość najkrótszej ścieżki powiększającej w .

Dowód

Załóżmy, że długość najkrótszej ścieżki w jest nie większa niż długość najkrótszej ścieżki w . Wtedy ścieżka ma z przepływem blokującym wspólną krawędź nasyconą. Niech będzie ostatnią taką krawędzią na . Oznacza to, że krawędź musiała należeć do przepływu . Inaczej w krawędź nadal byłaby nasycona. Ponieważ może zostać rozłożone na sumę pewnych najkrótszych ścieżek w , to z lematu 1, wiemy, że odległość z do nie zmalała, tzn. . Jednak ponieważ jest najkrótszą ścieżką z do , oznacza to, że odległość do wzrosła o co najmniej , . Kawałek ścieżki od do też jest najkrótszą ścieżką, więc . Długość najkrótszej ścieżki w grafie rezydualnym musiała więc wzrosnąć. End of proof.gif

Wniosek 4

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

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ą dla sieci rezydualnej definiujemy jako graf skierowany o następującym zbiorze krawędzi:

Zauważmy, że wszystkie ścieżki w z do 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 wszystkie ścieżki są najkrótsze, jednak nie wszystkie ścieżki muszą prowadzić do . Jeżeli usuniemy zawczasu z grafu krawędzie, które prowadzą donikąd, to ścieżki z do będziemy mogli wyszukiwać w czasie .

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


 DINIC-PRZEPŁYW-BLOKUJĄCY
 1  
 2  skonstruuj graf 
 3  while  do
 4  begin
 5    znajdź ścieżkę  z  do  w 
 6    for każda krawędź  do
 7    begin
 8      
 9      
 10     usuń rekurencyjnie  i inne wierzchołki jeżeli nie wychodzi z nich żadna krawędź residualna 
 11 end
 12 return 

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

Zauważmy, że po zakończeniu działania algorytmu, w grafie nie pozostanie żadna ścieżka z do . 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 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 , dlatego całkowity czas działania tej procedury wynosi . Korzystając z Wniosku 4 widzimy, że czas działania algorytmu Dinica wynosi .

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

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

.

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 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 - jeżeli do wierzchołka wpływa większy przepływ niż wypływa, to procedura ta przesyła ten nadmiar do przodu w grafie , nasycając po kolei krawędzie wychodzące z ,
  • procedury COFNIJ - jeżeli z wierzchołka 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 krawędzie do , nasycając po kolei krawędzie wchodzące do .

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


 MKM-PRZEPŁYW-BLOKUJĄCY
 1  
 2  skonstruuj graf 
 3  while  do
 4  begin
 5    znajdź wierzchołek o najmniejszym 
 6    prześlij  jednostek przepływu krawędziami wychodzącymi z 
 7    prześlij  jednostek przepływu krawędziami wchodzącymi do 
 8    for  to  do
 9      foreach  do 
 10       PRZEŚLIJ
 11   for  downto  do
 12     foreach  do 
 13       COFNIJ
 14   usuń  z grafu poprawiając przepustowości wierzchołków sąsiednich
 15 end
 16 return 

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 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 razy będziemy przesyłać przepływ nasycając krawędzie. Natomiast liczba przesłań nie nasycających krawędzi nie przekroczy , 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 . Czas potrzebny na znalezienie przepływu blokującego wynosi więc . Łącząc ten algorytm z algorytmem Dinica, otrzymujemy algorytm znajdujący maksymalny przepływ w grafie w czasie .