Przepływy

Mamy dany graf G(V,E). Są wyróżnione 2 wierzchołki : źródło(s - source) i ujście(t - target). Każda krawędź (u,v) ma przypisana wartość c(u,v) - oznaczającą maksymalną wartość jaka może "przepłynąć" przez nią. Przepływem w sieci G nazywamy funkcję , która spełnia następujące własności :

1. Warunek Przepustowości : Dla wszystkich u,v $\in$ V zachodzi f(u,v) <= c(u,v)
2. Warunek Skośnej Symetryczności : Dla wszystkich u,v $\in$ V zachodzi $f(u,v) = -f(v,u)$.
3. Warunek Zachowania Przepływu : Dla wszystkich v $\in$ V - {s,t} zachodzi : $\Sigma_{ u \in V }$ f(u,v) = 0

Pierwszy warunek oznacza, że przez dana krawędź może przepływać nie więcej niż wynosi przepustowość tej krawędzi. Drugi warunek oznacza, że przepływ z wierzchołka v do u, ma wartość przeciwną do przepływu z u do v. Trzeci, że suma przepływów przechodzących przez każdy wierzchołek równa się zero (oprócz źródła i ujścia). To znaczy, że tyle samo wpływa do danego wierzchołka ile też z niego wypływa.
Problem maksymalnego przepływu jest zdefiniowany następująco : Mając dany graf G(V,E) oraz funkcje c(u,v), należy znaleźć przepływ f dla którego wartość :
$|f|$ = $\Sigma_{u \in V} f(s,u)$ jest maksymalna.
Będę używał kilku pojęć:

• Ścieżka powiększająca - ścieżka która prowadzi od źródła(s) do ujścia(t) po krawędziach na których można zwiększyć przepływ tzn. c(u,v) - f(u,v) > 0
• Przekrój - jest to każdy podział zbioru $V$ na z $S$ i $T$ = $V-S$, taki, że $s \in S$ i $t \in T$
• Przepustowość przekroju $(S,T)$ oznaczamy jako $c(S,T) = \Sigma_{u \in S,v \in T} c(u,v)$
• Przepustowość Residualna - dla każdej krawędzi (u,v) to wartosc o jaką można jeszcze zwiększyć przepływ na tej krawędzi : $c_{f}(u,v) = c(u,v) - f(u,v)$
• Sieć Residualna - mając daną sieć $G(V,E)$ i przepływ $f$, siecią residualną dla sieci G indukowana przez przepływ $f$ nazywamy sieć $G_{f}(V,E_{f})$, gdzie zbór krawędzi wygląda następująco : $E_{f} = (u,v) \in V \times V: c_{f}(u,v) > 0$. Jest to taka sieć na której istnieją tylko takie krawędzie na których możemy zwiększyć przepływ.

Na początku omówię Metodę Forda-Fulkersona. Będę się tylko odnosił do przepustowości o wartościach naturalnych. Opiera się na Twierdzeniu o Maksymalnym Przepływie i Minimalnym Przekroju. Jest ono następujące : Jeśli $f$ jest przepływem w sieci $G(V,E)$ ze źródłem(s) i ujściem(t), to następujące warunki są równoważne :

1. Przepływ $f$ jest maksymalny w sieci $G$.
2. Sieć Residualna $G_{f}$ nie zawiera ścieżek powiększających.
3. Dla pewnego przekroju $(S,T)$ w sieci $G$ zachodzi $|f| = c(S,T)$.

Dowód tego twierdzenia znajduje się w Cormenie.
W metodzie Forda-Fulkersona, zaczynamy od przepływu zainicjowanego na 0. A potem w kolejnych iteracjach zwiększamy go, używając ścieżek powiększających. Robimy tak dopóki, nie będzie istniała żadna ścieżka powiększająca. Na końcu, na mocy twierdzenia o maksymalnym przepływie i minimalnym przekroju, otrzymany przepływ $f$ będzie przepływem maksymalnym.

  Ford_Fulkerson(G,s,t){
    dla każdej pary (u,v) : f(u,v) = 0
    while(istnieje ścieżka powiekszająca - p){
        min_p = minimalna przepustowość residualna na ścieżce p;
        dla każdej krawędzi (u,v) leżącej na p{
            f(u,v) = f(u,v) + min_p;
            f(v,u) = f(v,u) - min_p; // to samo co f(v,u) = -f(u,v)
        }
    }
    return f;
  }

W zależności od tego jakiego rodzaju przeszukiwania użyjemy, złożoność czasowa jest inna. Jeżeli zastosujemy DFS to algorytm będzie działał $O(E|f^*|)$, gdzie $f^*$ to maksymalny przepływ. Jest tak gdyż każde szukanie ścieżki powiększającej zajmuję O(E) czasu, a pętla while będzie miała co najwyżej $f^*$ iteracji. Widać jednak, że taki algorytm nam się nie podoba, bo nie działa w czasie wielomianowym. Jeśli jednak zastosujemy przeszukiwanie używając BFS(nazywa się to algorytm Edmondsa-Karpa), złożoność będzie wynosiła $O(VE^2)$. Dzieje się tak dzięki temu, że znaleziona w przeszukiwaniu ścieżka będzie ścieżką o minimalnej odległości od źródła(traktując odległość jako ilość krawędzi na ścieżce). Można udowodnić, że ilość iteracji pętli while() wynosi $O(VE)$.

---

Zadanie X

Mamy dany graf $G(V,E)$ oraz dwa wierzchołki $a$ i $b$. Mamy znaleźć ile minimalnie krawędzi trzeba usunąć z $E$, żeby w nie istniała ścieżka z wierzchołka $a$ do $b$ i wskazać te krawędzie.
Przekształćmy te dane, tak żeby można było użyć metody Forda-Fulkersona. Oznaczmy $a$ jako źródło(s) i $b$ jako ujście(t). Przepustowość c[u][v] = 1, jeżeli $(u,v) \in E$, w przeciwnym wypadku c[u][v] = 0. Teraz jeżeli znajdziemy maksymalny przepływ $|f|$ - to dowiemy się ile istnieje ścieżek rozłączno-krawędziowych w grafie G prowadzących z $a$ do $b$ i tyle też krawędzi będzie trzeba usunąć z tego grafu. Wiemy iż maksymalny przepływ jest ograniczony przez przekrój w sieci. Więc na pewno istnieje przekrój $(S,T)$, dla którego $c(S,T) = |f|$. Zadanie sprowadza się więc do znalezienie tego przekroju i wypisania krawędzi $(u,v)_{u \in S, v \in T,(u,v) \in E}$. Aby ten program działał, przy poszukiwaniu ścieżki powiększającej trzeba używać tablicy odwiedzin (czy dany wierzchołek był odwiedzony w przeszukiwaniu). Jeżeli wierzchołek jest odwiedzony tzn. że należy do zbioru S, w przeciwnym wypadku do T. Wypada jeszcze wspomnieć o złożoności, która wynosi $O(V^3)$, stosując implementacje na macierzy. Jest tak ponieważ, każde przeszukiwanie zajmuje $O(V^2)$, a pętla while() wykona $O(f^*)$ obiegów, czyli $O(V)$ iteracji. Wiec złożoność wynosi $O(V^2) \cdot O(V) = O(V^3)$. Pseudokod:

IN:

• c[i][j] - macierz sąsiedztwa w grafie, a zarazem przepustowość
• s - źródło(a)
• t - ujście(b)

  Zadanie X(G,s,t){
    f = Ford-Fulkerson(G,a,b);
    int ile = suma, dla wszystkich 'u' f[s][u];
    wypisz(ile);
    dla każdego (u,v)
    jeżeli (c[u][v]==1 && 'u' - należy do S && 'v' należy T)
       wypisz(u v);
  }

author : Michał Zgliczyński