Wykres resztkowy w maksymalnym przepływie

Czytam tutaj o problemie z maksymalnym przepływem . Nie mogłem zrozumieć intuicji stojącej za wykresem rezydualnym. Dlaczego podczas obliczania przepływu bierzemy pod uwagę tylne krawędzie?

Czy ktoś może mi pomóc zrozumieć pojęcie wykresu resztkowego?

Jak zmienia się algorytm w niekierowanych grafach?

Intuicyjna interpretacja wykresu resztkowego w problemie maksymalnego przepływu jest bardzo dobrze przedstawiona w tym wykładzie. Wyjaśnienie jest następujące.

Załóżmy, że próbujemy rozwiązać problem maksymalnego przepływu dla następującej sieci (gdzie każda etykieta oznacza zarówno przepływ przepchnięty przez krawędź i pojemność tej krawędzi):$G$$f_e/c_e$$f_e$$e$$c_e$

Jednym z możliwych chciwych podejść jest:

1. Odebrać dowolne rozszerzanie ścieżki , która wychodzi z wierzchołka źródło zlewu wierzchołek tak, że ); to znaczy wszystkie krawędzie w mają dostępną pojemność.s t ∀ $P$$s$$t$$\forall e \: (e \in P \rightarrow f_e \lt c_e$$P$
2. Popchnij maksymalny możliwy przepływ przez tę ścieżkę. Wartość określa się przez wąskie gardło w ; to znaczy krawędź o minimalnej dostępnej pojemności. Formalnie .$\Delta$$\Delta$$P$$\Delta=\min_{e \in P} (c_e-f_e)$
3. Przejdź do kroku 1, aż nie będzie żadnych ścieżek rozszerzających.

Oznacza to, że znajdź ścieżkę o dostępnej pojemności, wyślij przepływ wzdłuż tej ścieżki i powtórz.

W jedno możliwe wykonanie powyższej heurystyki znajduje trzy ścieżki rozszerzające , i , w tej kolejności. Te ścieżki wypychają odpowiednio 2, 2 i 1 jednostki przepływu, co daje całkowity przepływ 5:$G$$P_1$$P_2$$P_3$

Wybór ścieżek w tej kolejności prowadzi do optymalnego rozwiązania; co się jednak stanie, jeśli najpierw wybierzemy (tj. przed i )?$P_3$$P_1$$P_2$

Otrzymujemy tak zwany przepływ blokujący : nie ma już żadnych ścieżek rozszerzających. W takim przypadku całkowity przepływ wynosi 3, co nie jest optymalne. Ten problem można rozwiązać, zezwalając na operacje cofania (tj. Zezwalając na wysyłanie przepływu w odwrotną stronę, cofanie pracy poprzednich iteracji): wystarczy przesunąć 2 jednostki przepływu wstecz od wierzchołka do wierzchołka następujący sposób:$w$$v$

Kodowanie tych dozwolonych operacji cofania jest głównym celem wykresu resztkowego .

Wykres resztkowy sieci ma taki sam zestaw wierzchołków jak i zawiera dla każdej krawędzi :$R$$G$$G$$e=(u,v) \in G$

• Przednia krawędź o pojemności , jeśli .$e'=(u,v)$$c_e-f_e$$c_e-f_e \gt 0$

• krawędź o pojemności , jeśli .$e''=(v,u)$$f_e$$f_e \gt 0$

Weźmy na przykład wykres resztkowy który jest uzyskiwany po pierwszej iteracji zachłannej heurystyki, gdy heurystyka najpierw wybiera (to znaczy, kiedy otrzymuje przepływ blokujący):$R$$P_3$

Zauważ, że operacja cofania , która popycha 2 jednostki przepływu z do jest kodowana jako ścieżka do przodu (zwiększająca) od do w :$w$$v$$s$$t$$R$

Ogólnie:

Po wybraniu ścieżki rozszerzającej na wykresie resztkowym :$P'$$R$

• Każda krawędź w która odpowiada przedniej krawędzi w zwiększa przepływ, stosując krawędź o dostępnej pojemności.$P'$$G$
• Każda krawędź w która odpowiada krawędzi cofającej się w cofa przepływ, który w przeszłości był popychany do przodu.$P'$$G$

Jest to główna idea metody Forda-Fulkersona .

Metoda Forda-Fulkersona postępuje dokładnie tak samo, jak chciwe podejście opisane powyżej, ale zatrzymuje się tylko wtedy, gdy nie ma już ścieżek rozszerzających na wykresie resztkowym (nie w oryginalnej sieci). Metoda jest poprawna (tzn. Zawsze oblicza maksymalny przepływ), ponieważ wykres resztkowy ustanawia następujący warunek optymalności :

Przy danej sieci przepływ jest maksymalny w jeśli nie ma ścieżki na wykresie resztkowym.$G$$f$$G$$s-t$

Intuicyjna sieć rezydualna polega na tym, że pozwala nam „anulować” już przypisany przepływ, tj. Jeśli mamy już przypisane 2 jednostki przepływu z do , wówczas przekazanie 1 jednostki przepływu z do jest interpretowane jako anulowanie jednej jednostki pierwotnego przepływu od do .$A$$B$$B$$A$$A$$B$