Zaawansowane algorytmy i struktury danych/Wykład 9

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Abstrakt

Wykład ten poświęcony będzie problemowi znajdowania maksymalnego przepływu w grafie. Zaczniemy od wprowadzenia potrzebnych pojęć, a następnie przestawimy metodę Forda-Fulkersona znajdowania maksymalnego przepływu w grafie.

Podstawowe pojęcia

Siecią przepływową, bądź krótko siecią, nazywamy skierowany graf , w którym z każdą krawędzią wiążemy jej nieujemną przepustowość . W sieci przepływowej wyróżniamy dwa wierzchołki: źródło oznaczane jako oraz ujście oznaczane jako .

Niech będzie siecią oraz niech będzie dla niej funkcją przypisującą przepustowości. Przepływem w nazwiemy funkcję spełniającą następujące właściwości:

  • Dla wszystkich zachodzi - warunek ten nazywamy warunkiem ograniczenia przepustowości.
  • Dla wszystkich zachodzi - jest to warunek skośnej symetrii.
  • Dla wszystkich żądamy aby zachodził warunek zachowania przepływu:

O wartości mówimy, że jest to wielkość przepływu z do . Wartość przepływu , oznaczamy i definiujemy jako sumaryczną wielkość przepływu wypływającego z wszystkimi krawędziami, tzn.:

W problemie maksymalnego przepływu dla danej sieci chcemy znaleźć przepływ o największej wartości.

W dalszej części wykładu używać będziemy następującej notacji sumacyjnej, w której argument funkcji może być podzbiorem dziedziny . W takim wypadku przyjmujemy, że wartością funkcji jest suma jej wartości dla zbioru , tzn.:

Używając tej notacji, możemy zapisać warunek zachowania przepływu dla wierzchołka jako . W poniższym lemacie używamy tej notacji do zapisania podstawowych właściwości przepływu.

Lemat 1

Niech będzie siecią przepływową oraz przepływem w niej. Wtedy:
  1. Dla wszystkich mamy .
  2. Dla wszystkich mamy .
  3. Dla wszystkich zachodzi:
    Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \begin{array}{r@{}c@{}l} f(X \cup Y,Z) &=& f(X,Z) + f(Y,Z) - f(X \cap Y,Z) \mbox{ i } f(Z, X \cup Y)=\\ &=& f(Z,X) + f(Z,Y) - f(Z,X \cap Y). \end{array}}
  4. .

Dowód tego lematu pozostawiony jest jako Zadanie 1 do tego wykładu.

Sieć rezydualna

Intuicyjnie, dla danej sieci przepływowej i przepływu , sieć rezydualna składa się z krawędzi, którymi można przesłać większy przepływ. Bardziej formalnie, przypuśćmy, że mamy sieć przepływową ze źródłem i ujściem oraz niech będzie przepływem w . Rozważmy teraz parę wierzchołków . Ilość dodatkowego przepływu , którą możemy przesłać z do , zanim przekroczymy przepustowość , wynosi

Na przykład, jeśli i , wtedy możemy zwiększyć o jednostek, zanim przekroczymy ograniczenie przepustowości krawędzi .

Dla danej sieci i przepływu , sieć rezydualna zaindukowana przez to graf , gdzie:

To znaczy, tak jak napisaliśmy powyżej, że każdą krawędzią sieci rezydualnej lub krawędzią rezydualną można przepuścić przepływ, który jest większy niż 0.

Krawędzie w są albo krawędziami w , albo krawędziami o odwróconym kierunku. Jeśli zachodzi dla krawędzi , to wtedy i . Jeśli dla krawędzi , to wtedy . W tym przypadku, , i dlatego . Jeśli ani ani nie pojawiają się w pierwotnej sieci, to wówczas i , a zatem też . Podsumowując, krawędź może się pojawić w sieci rezydualnej tylko wtedy, kiedy co najmniej jedna z krawędzi i jest w pierwotnej sieci. Dlatego też . Należy zauważyć, że sieć rezydualna jest także siecią przepływową o przepustowości krawędzi zadanej przez . Następujący lemat pokazuje, jak przepływ w rezydualnej sieci powiązany jest z przepływem w pierwotnej sieci przepływów.

Lemat 1

Niech będzie siecią przepływową ze źródłem i ujściem i niech będzie przepływem w . Niech będzie siecią rezydualną dla , indukowaną przez , i niech będzie przepływem w . Wtedy suma przepływów jest przepływem w o wartości .

Dowód

Po pierwsze musimy pokazać, że dla sumy przepływów warunki, symetrii skośnej, ograniczenia przepustowości jak i zachowania przepływu są spełnione. W przypadku symetrii skośnej zauważmy, że dla wszystkich , mamy:
Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \begin{array}{r@{}c@{}l} (f + f')(u, v) &=& f(u, v) + f'(u, v) = -f(v, u) - f'(v, u) =\\&=& -(f(v, u) + f'(v, u))= -(f + f')(v, u). \end{array}}

W przypadku ograniczenia przepustowości zauważmy, ze dla wszystkich i dlatego:

W przypadku warunku zachowania przepływu, należy zauważyć, że dla wszystkich , mamy:

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \begin{array}{r@{}c@{}l}\sum_{v \in V}(f+f')(u,v) &=& \sum_{v \in V}(f(u,v) + f'(u,v)) =\\&=& \sum_{v\in V}f(u,v) + \sum_{v\in V}f(u,v) = 0 + 0 = 0.\end{array}}

Ostatecznie otrzymujemy, że wartość wynosi:

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \begin{array}{r@{}c@{}l}|f + f'| &=& \sum_{v \in V}(f + f')(s,v) = \sum_{v \in V}(f(s,v) + f'(s,v)) =\\&=& \sum_{v \in V}f(s,v) + \sum_{v\in V}f'(s,v) = |f| + |f'|.\end{array}}
End of proof.gif

Ścieżki powiększające

Jeśli dana jest sieć przepływowa i przepływ , wówczas ścieżka powiększająca jest ścieżką prostą z do w rezydualnej sieci . Z definicji sieci rezydualnej, każda krawędź na ścieżce powiększającej pozwala na przesłanie pewnego dodatkowego przepływu z do bez naruszenia ograniczenia przepustowości krawędzi. Znajdowanie ścieżki powiększającej w sieci rezydualnej, a następnie powiększenie przy jej pomocy przepływu zobrazowane jest na następującej animacji.

Najwyższą wartość, o jaką można zwiększyć przepływ przy użyciu ścieżki , nazywamy rezydualną przepustowością . Wielkość ta jest dana przez:

Zdefiniujmy tę zmianę przepływu związaną ze ścieżką jako funkcję równą:

     (1)

Wówczas jest przepływem w o wartości . Dodając do , otrzymamy kolejny przepływ w , którego wartość jest bliższa maksimum, co sformułowane jest w tym wniosku.

Wniosek 2

Niech będzie siecią przepływową, niech będzie przepływem w i niech będzie ścieżką powiększającą w . Niech będzie zdefiniowane jak we wzorze 1. Zdefiniujmy funkcję jako , wówczas jest przepływem w o wartości .

Przekroje w sieci

Twierdzenie o maksymalnym przepływie i minimalnym przekroju, które za chwilę udowodnimy, pokazuje że przepływ jest maksymalny wtedy i tylko wtedy, kiedy jego sieć rezydualna nie zawiera żadnej ścieżki powiększającej. Jednak, aby udowodnić to twierdzenie, musimy wpierw wprowadzić pojęcie przekroju sieci przepływowej. Przekrój sieci przepływowej jest podziałem na i tak, że i . Jeśli jest przepływem, wtedy przepływ netto poprzez przekrój jest zdefiniowany jako . Przepustowość przekroju definiujemy jako . Minimalnym przekrojem sieci jest przekrój, którego przepustowość jest najmniejsza ze wszystkich przekrojów w sieci.

Poniższa ilustracja pokazuje przekrój w sieci przepływów. Przepływ netto poprzez ten przekrój wynosi: , a jego przepustowość wynosi .

Należy zaobserwować, że przepływ netto w przekroju może zawierać negatywny przepływy pomiędzy wierzchołkami, jednakże przepustowość przekroju składa się wyłącznie z nieujemnych wartości. Innymi słowy, przepływ netto poprzez przekrój składa się z dodatnich przepływów płynących w dwa kierunki; dodatni przepływ z do jest dodawany, podczas gdy dodatni przepływ z do jest odejmowany. Z drugiej strony, przepustowość przekroju jest obliczana tylko od krawędzi odchodzących z do . Krawędzie biegnące z do nie są włączone do obliczeń . Powyższy lemat pokazuje, że przepływ netto przez jakikolwiek przekrój jest taki sam i równy jest wartości przepływu.

Lemat 3

Nich będzie przepływem w sieci przepływów ze źródłem i ujściem i niech będzie przekrojem w . Wtedy przepływ netto przez wynosi .

Dowód

Zauważmy, że z warunku zachowania przepływu, dlatego:
End of proof.gif

Jako w wniosek z tego lematu otrzymujemy, że przepustowość przekroju jest graniczeniem wartości przepływu.


Wniosek 4

Wartość dowolnego przepływu w sieci przepływów jest ograniczona z góry przez przepustowość dowolnego przekroju w .

Dowód

3

Niech będzie dowolnym przekrojem w i niech będzie dowolnym przepływem. Z lematu 3 i warunku ograniczenia przepustowości otrzymujemy:

End of proof.gif

W szczególności maksymalny przepływ w sieci jest ograniczony od góry przez przepustowość najmniejszego przekroju w sieci. Twierdzenie o maksymalnym przepływie i minimalnym przekroju, które teraz postawimy i udowadnimy, mówi że wartość maksymalnego przepływu jest w rzeczywistości równa przepustowości najmniejszego przekroju.

Twierdzenie 5 [O maksymalnym przepływie i minimalnym przekroju]

Jeśli jest przepływem w sieci przepływowej ze źródłem i ujściem , wówczas następujące warunki są równoważne:
  1. jest maksymalnym przepływem w .
  2. Sieć rezydualna nie zawiera żadnych ścieżek powiększających.
  3. dla pewnego przekroju w .

Dowód

(1)(2): Załóżmy przez sprzeczność, że jest maksymalnym przepływem w , ale że posiada ścieżkę powiększającą . Wówczas, z wniosku 2, suma przepływów , gdzie jest dane wzorem 1, jest przepływem w o wartości ściśle większej niż , co jest sprzeczne z założeniem, że jest przepływem maksymalnym.

(2)(3): Przypuśćmy, że nie posiada żadnej ścieżki powiększającej, to znaczy że nie posiada żadnej ścieżki z do . Zdefiniujmy:

,

oraz:

.

Podział jest przekrojem: oczywiście i , ponieważ nie ma żadnej ścieżki z do w . Dla każdej pary wierzchołków i , mamy , gdyż w przeciwnym wypadku , co umiejscowiłoby w zbiorze . Dlatego też, z lematu 3, mamy .

(3)(1): Z wniosku 4 wiemy, że dla wszystkich przekrojów . Czyli warunek oznacza, że jest przepływem maksymalnym. End of proof.gif

Algorytm Forda – Fulkersona

W każdej iteracji metody Forda–Fulkersona odnajdujemy dowolną ścieżkę powiększającą i zwiększamy przepływ na każdej krawędzi o przepustowość rezydualną . Poniżej zamieszczamy implementacje tej metody.

Algorytm [Forda-Fulkersona] znajduje przepływ maksymalny w grafie


 FORD-FULKERSON()
 1 for każda krawędź  do
 2 begin
 3   
 4   
 5  end
 6  while istnieje ścieżka  z  do  w sieci rezydualnej  do
 7  begin
 8    
 9    for każda krawędź  do
 10   begin
 11     
 12     
 13   end
 14 end
 15 return 

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

Czas działania metody Forda-Fuklersona zależy od wyboru ścieżki powiększającej. Jeżeli będziemy ją wybierać źle, to algorytm wręcz może się nie zakończyć. W przypadku, gdy przepustowości krawędzi są całkowito liczbowe, to łatwo możemy pokazać, że czas działania tego algorytmu wynosi , gdzie jest przepływem maksymalnym w sieci. Jeżeli przepływ jest mały, to algorytm ten działa szybko, jednak może się zdarzyć, nawet dla prostego przykładu, że algorytm będzie musiał wykonać iteracji. Taki przykład pokazany jest na poniższej animacji.

<flash>file=zasd_ilustr_e.swf |width=800|height=300</flash>