Wykład 3. Skojarzenia i przepływy

Lista zagadnień, które zostały omówione:

  1. Postawienie problemu. Mamy dany skierowany graf G z wyróżnionymi dwoma wierzchołkami s(nazywanym dalej źródłem) oraz t(ujściem). Dla każdej krawędzi chcemy przypisać liczbę całkowitą 0 lub 1, tak aby:
    • dla każdego wierzchołka v (poza źródłem oraz ujściem) suma krawędzi wchodzących była równa sumie krawędzi wychodzących,
    • każdej krawędzi wchodzącej do źródła była przypisana liczba 0,
    • każdej krawędzi wychodzącej z ujścia była przypisana liczba 0.

    Funkcję spełniającą powyższe warunki będziemy nazywali przepływem (możemy sobie wyobrazić taką funkcję jako schemat przesyłu wody przez rurociągi). Wartością przepływu nazywamy sumę krawędzi wychodzących ze źródła (która jest równa sumie krawędzi wchodzących do ujścia). Naszym celem będzie zmaksymalisowanie wartości przepływu.

     

    Uwaga: Jeśli w danym grafie krawędzie mają przepustowości większe niż 1, to krawędź o przepustowości c możemy zamienić na c krawędzi o przepustowości 1, otrzymując równoważny problem. W praktycznej implementacji będziemy oczywiście inaczej radzić sobie z przypadkiem większych przepustowości.

  2. Schemat Forda-Fulkersona. Wszystkie poruszane metody znajdowania maksymalnego przepływu będą oparte na znajdywaniu kolejnych ścieżek z wierzchołka s do wierzchołka t. Rozważmy następujący graf:

    Załóżmy, że zdecydowaliśmy się na użycie krawędzi leżących na pogrubionej ścieżce:

    Jeśli decyzja ta byłaby nieodracalna, to nie moglibyśmy znaleźć przepływu o większej wartości, dlatego też krawędzie wykorzystane w ostatnio znalezionej ścieżce będziemy odwracać, operację taką nazywamy powiększeniem przepływu wzdłuż danej ścieżki. W naszym przykładzie graf będzie wyglądał następująco:

    Nie trudno zauważyć, że w grafie tym nadal istnieje ścieżka ze źródła do ujścia. Możemy teraz sformułować następujący schemat (zwany schematem Forda-Fulkersona):

    • dopóki istnieje ścieżka z wierzchołka s do wierzchołka t,
    • powiększ aktualny przepływ wzdłuż znalezionej ścieżki (odwracając przy tym wszystkie krawędzie na tej ścieżce).

    Powyższy opis nie jest algorytmem, gdyż nie precyzuje on jak daną ścieżkę znaleźć oraz w przypadku istnienia wielu takich ścieżek, którą z nich należy wybrać. Aby pokazać, że wybór ścieżki może być kluczowy dla złożoności obliczeniowej algorytmu rozważmy ponownie nasz graf, ale tym razem z krawędziami mającymi dowolne całkowite przepustowości:

     

    Jeśli będziemy wykorzystywać ścieżki przechodzące przez krawędź o przepustowości 1, to aby otrzymać maksymalny przepływ musimy wykonać aż 1000000 powiększeń!

  3. Twierdzenie o maksymalnym przepływie i minimalnym przekroju. Z problemem znajdowania maksymalnego przepływu związany jest problem do niego dualny, nazywany problemem znajdowania minimalnego przekroju. Przekrojem w danym grafie nazywamy podział zbioru wierzchołków V na dwa zbiory V1 oraz V2, takie że s należy do V1 natomiast t należy do V2. Wartością danego przekroju nazywamy łączną przepustowość krawędzi prowadzących z V1 do V2.

    Uwaga: Problem znajdowania minimalnego przekroju możemy również interpretować równoważnie jako znajdowanie podzbioru krawędzi o minimalnej sumie przepustowości, takiego że po usunięciu tych krawędzi, nie istnieje ścieżka z s do t.

    Twierdzenie o maksymalnym przepływie i minimalnym przekroju: Dla dowolnego grafu G minimalny przekrój i maksymalny przepływ mają taka samą wartość.

    Dowód: Rozważmy pewien przepływ f w grafie G. Pokażemy, że następujące trzy warunki są równoważne:

    1. Przepływ f jest maksymalny.
    2. W grafie G nie istnieje ścieżka powiększająca.
    3. W oryginalnym grafie Gorig istnieje przekrój o wartości równej wartości przepływu f (oznaczanej jako |f|).

    Przejście 1->2 jest oczywiste. Przejście 3->1 łatwo wykazać, gdyż każdy przekrój ogranicza nam wartość maksymalnego przepływu. Pozostaje nam do udowodnienia implikacja 2->3. Przez zbiór V1 oznaczmy zbiór wierzchołków osiągalnych z s (oczywiście s należy do V1), natomiast jako V2 weźmy V2=V-V1. Można pokazać że przekrój ten ma wartość równą dokładnie |f|.

     

    Dowód powyższego twierdzenia jest konstruktywny, mając dany maksymalny przepływ możemy łatwo wyznaczyć przekrój o takiej samej wartości. Niestety jednak nie jest dotychczas znany żaden algorytm, który korzystając z minimalnego przekroju wyznacza maksymalny przepływ. Dowód przedstawionego twierdzenia pokazuje poprawność schematu Forda-Fulkersona.

  4. Algorytm Edmondsa-Karpa oraz zmodyfikowany algorytm Dinica. Algorytm Edmondsa-Karpa jest uszczególnieniem schematu Forda-Fulkersona, nakazuje on wybieranie najkrótszej ścieżki powiększającej (w sensie liczby krawędzi), co można zrealizować za pomocą algorytmu BFS. Należy jeszcze sprecyzować w jaki sposób będziemy radzić sobie z krawędziami o dowolnych całkowitych przepustowościach. Graf możemy reprezentować jako tablicę list sąsiedztwa oraz pomocniczą tablicę dwuwymiarową, określającą krotności krawędzi o przepustowościach jednostkowych, czyli innymi słowy przepustowość krawędzi pomiędzy danymi wierzchołkami. Można pokazać (co nie jest trywialne) że dla krawędzi o dowolnych przepustowościach złożoność algorytmu Edmondsa-Karpa wynosi O(nm2), co oznacza że w wielu zadaniach możemy potrzebować szybszego algorytmu.

    Algorytm Dinica jest oparty na następującym schemacie:

    • dopóki istnieje ścieżka z s do t, wykonuj:
    • znajdź przepływ blokujący w grafie warstwowym powstałym z grafu G.

    Do grafu warstwowego należą tylko i wyłącznie wszystkie krawędzie uv, takie że dist(s,v)=dist(s,u)+1 (gdzie dist(x,y) to odległość wierzchołka y od wierzchołka x w sensie liczby krawędzi). Inaczej mówiąc w grafie warstwowym występują tylko krawędzie prowadzące od bliższej do dalszej warstwy w drzewie BFS. Przepływ blokujący, jest to dowolny przepływ uzyskany przez znajdowanie kolejnych ścieżek powiększających, ale bez odwracania krawędzi. Innymi słowy jest to przepływ uzyskany przez zachłanne, nieodwracalne decyzje, którego nie da się powiększyć bez wycofywania się z wcześniej nasyconych krawędzi. Poniższy przykład pokazuje przepływ blokujący w grafie warstwowym, który nie jest maksymalnym przepływem:

     

  5. Znajdowanie przepływu blokującego w grafie warstwowym będziemy nazywali fazą. Aby pokazać złożoność obliczeniową naszego algorytmu będziemy musieli oczasować liczbę faz oraz złożoność pojedynczej fazy.

    Fakt 1W każdej fazie odległość między wierzchołkami s i t jest większa niż w poprzedniej faziej.

    Dowód: Nietrywialny i żmudny.

    Z powyższego faktu wynika, że liczba faz w algorytmie Dinica jest niewiększa niż n. W oryginalnym algorytmie Dinica pojedyncza faza jest realizowana w czasie O(n2), jednakże algorytm ten jest dość skomplikowany, dlatego też będziemy stosować uproszczony algorytm do znajdowania przepływu blokującego. Algorytm ten będzie w sposób zachłanny przesyłał maksymalną ilość "wody" od źródła do ujścia w sposób rekurencyjny, pamiętając zawsze minimalną przepustowość krawędzi na ścieżce od źródła do aktualnie rozważanego wierzchołka. Bardzo istotna optymalizacja polega na tym, że dla danego wierzchołka przeglądamy krawędzie rozpoczynając od ostatnio rozważanej krawędzi. Implementację całego algorytmu można znaleźć tutaj. Można pokazać, że złożoność pojedynczej fazy w tej implementacji wynosi O(n3), co powoduje że złożoność całego algorytmu wynosi O(n4), jednakże w praktyce nie da się znaleźć (przynajmniej my nie umiemy) instancji na której algorytm wykona właśnie tyle operacji. Dla losowych danych algorytm zachowuje się lepiej niż algorytmy o nominalnej złożoności O(n3).

  6. Nietrywialne zastosowania twierdzenia o maksymalnym przepływie i minimalnym przekroju.

    Crazy Painter, autor: Andrey Stankevich

    W zadaniu mamy daną prostokątną planszę złożoną z kwadratów 1x1. Niektóre pola tej planszy są zabronione. Naszym celem jest pomalowanie wszystkich pól dozwolonych minimalnym kosztem. Możemy wykonywać 3 czynności: pomalowanie pojedynczego pola (koszt operacji wynosi x), pomalowanie poziomego paska pól dozwolonych (koszt h), pomalowanie pionowego paska pól dozwolonych (koszt v). Nie możemy malować pól zabronionych, jednakże pole dozwolone może być malowane wielokrotnie.

    Rozwiązanie: Skonstruujmy następujący graf dwudzielny, jedna warstwa będzie zawierała wszystkie maksymalne w sensie zawierania paski poziome pól dozwolonych, druga warstwa będzie zawierała wszystkie maksymalne paski pionowe pól dozwolonych. Z wierzchołka pierwszej warstwy wychodzi krawędź do wierzchołka drugiej warstwy o przepustowości x wtw gdy paski odpowiadające owym wierzchołkom się przecinają. Do grafu dodajemy źródło i ujście. Źródło łączymy ze wszystkimi wierzchołkami pierwszej warstwy krawędziami o przepustowościach h, natomiast z każdego wierzchołka drugiej warstwy prowadzimy krawędź do ujścia o przepustowości v. Oto przykład konstrukcji grafu:

    Można pokazać, że wartość maksymalnego przepływu w takim grafie jest równa wartości szukanej w zadaniu. Aby zrozumieć dlaczego tak jest, będziemy zamiast maksymalnego przepływu szukać minimalnego przekroju (który ma taką samą wartość). Teraz zarówno problem postawiony w zadaniu jak i problem przekroju są problemami minimalizacyjnymi. Można pokazać, że podzbiór krawędzi który rozspójnia źródło i ujście jest dobrym pomalowaniem, gdyż w grafie istnieje ścieżka z s do t wtw gdy istnieje niepomalowane pole. Analogicznie optymalne rozwiązanie zadania daje się przetłumaczyć na przekrój w naszym grafie o takim samym koszcie.

  7. Na początku drugiej części wykładu o tym samym temacie zobaczymy kolejny przykład nietrywialnego zastosowania twierdzenia o maksymalnym przepływie i minimalnym przekroju, a także postaramy się przybliżyć ogólny schemat konstrukcji grafu w takich zadaniach.

    Wszelkie uwagi odnośnie tego wykładu, w tym niniejszego jego opisu, w tym wszelkie poprawki błędów, jakich niewątpliwie jest w nim mnóstwo, prosimy kierować do Marka Cygana.