Max-Flow / Min-Cut: Jak Ford-Fulkerson Znajduje Napięcie

Sieci przepływowe i graf resztkowy

Sieć przepływu to skierowane graf, w którym każda krawędź (u,v) ma pojemność c(u,v) ≥ 0, wraz z źródłem s i drenem t. Poprawny przepływ musi przestrzegać ograniczenia pojemności na każdej krawędzi oraz zasady zachowania się w każdym węźle wewnętrznym – czyli dokładnie prawo Kirchhoffa dotyczące natłoku dla wody lub elektryczności. Centralnym pomysłem stojącym za każdym algorytmem max-flow jest graf resztkowy G_f, który śledzi, ile dodatkowego przepływu można jeszcze przesłać wzdłuż krawędzi, a także – co najważniejsze – ile istniejącego przepływu można "odwrócić", przesyłając go wstecz. Ta sztuczka z odwrotną krawędź umożliwia częściowe anulowanie wczesnego, pochopnego wyboru, jeśli okaże się on nieoptymalny, bez konieczności cofania się po oryginalnym grafie.

Ford-Fulkerson i Edmonds-Karp

Ford i Fulkerson (1956) zaproponowali wielokrotne znajdowanie dowolnej ścieżki rozszerzającej z s do t w grafie resztkowym oraz przesyłanie przepływu równego jej pojemności wąskiego gardła, aż nie pozostaną żadne ścieżki. Jednakże metoda ta nie określa, jak znaleźć tę ścieżkę, a naiwne DFS może wymagać tyle iteracji, ile maksymalny przepływ – miliony na małym grafie z dużymi pojemnościami całkowitoliczbowymi. Edmonds i Karp (1972) poprawili to jednym ulepszeniem: zawsze wybierać najkrótszą ścieżkę rozszerzającą za pomocą BFS. Ponieważ najmniejsza odległość w drodze od s do dowolnego wierzchołka jest monotonicznie nie malejąca w iteracjach, każdy krawędź może stać się krytyczna najwyżej O(V) razy, co daje autentyczny wielopowietnościowy wynik O(VE²) niezależny od wartości pojemności.

Twierdzenie o cięciu s-t

Cięcie s-t dzieli wierzchołki na S (zawierające s) i T (zawierające t); jego pojemność to całkowita pojemność krawędzi przecinających z S do T. Twierdzenie o cięciu s-t (Ford i Fulkerson, 1956) mówi, że maksymalna wartość przepływu równa się dokładnie minimalnej pojemności cięcia dla wszystkich takich podziałów — każdy jednostkowy przepływ musi przeciąć cięcie co najmniej raz (dwójność słabego), a w optymalnym przypadku wszystkie krawędzie s→T są nasycone, a wszystkie krawędzie t→S przenoszą zero przepływu. To dwójstwo oznacza, że znalezienie najtańszego zestawu połączeń do przerwania — najsłabszego punktu w łańcuchu dostaw lub najbardziej podatnych połączeń w sieci — jest darmowe.

max |f|  over all valid flows f   =   min cap(S,T)  over all s-t cuts (S,T)

Edmonds-Karp:  O(V·E²)   (shortest augmenting path via BFS)
Dinic's:       O(V²·E) — O(E·√V) on unit-capacity graphs (bipartite matching)

Algorytm Dinica i dopasowywanie bipartytne

Algorytm Dinica (1970) buduje "graf poziomów" za pomocą BFS, znajduje blokujący przepływ w nim za pomocą DFS, a następnie powtarza to – na każdej fazie BFS poziom t rośnie ściśle, ograniczając czas działania do O(V) faz i O(V²E) w sumie, co spada do O(E√V) na grafach o pojemności jednostkowej. Ten szczególny przypadek ma ogromne znaczenie: maksymalne dopasowywanie bipartytne – łączenie pracowników z zadaniami, np. – redukuje się bezpośrednio do maksymalnego przepływu poprzez dodanie superźródła i superzbiornika z krawędziami o pojemności 1 wszędzie. Ponieważ twierdzenie integralności gwarantuje wartością całkowitą optymalny przepływ, gdy wszystkie pojemności są liczbami całkowitymi, wynikowy przepływ jest automatycznie ważnym dopasowaniem 0/1, a Dinic na tej redukcji to słynny algorytm Hopcrofta-Karpa w ukryciu.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz the simulation i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.