Wiemy, że obliczenie maksymalnego przepływu lub. minimalne ograniczenie sieci o przepustowości jest równoważne; por. twierdzenie o maksymalnym przepływie min. cięcie .
Mamy (mniej lub bardziej wydajne) algorytmy obliczania maksymalnych przepływów, a obliczanie minimalnego cięcia przy maksymalnym przepływie nie jest ani trudne, ani drogie.
Ale co na odwrót? Biorąc pod uwagę minimalne cięcie, jak możemy określić maksymalny przepływ? Oczywiście bez rozwiązania Max-Flow od zera, a najlepiej też szybciej .
Kilka myśli:
Od minimalnego cięcia znamy maksymalną wartość przepływu. Nie widzę, w jaki sposób te informacje pomagają standardowi w podejściu do ścieżki rozszerzania i zmiany etykiety, chociaż dostosowanie tej drugiej wydaje się nieco bardziej prawdopodobne.
Nie możemy użyć minimalnego cięcia, aby podzielić sieć na dwie części i powtórzyć, ponieważ nie zmniejszy to problemu w najgorszym przypadku (jeśli jedna partycja jest singletonem); również nie mielibyśmy minimalnego cięcia mniejszych instancji.
Czy znajomość wartości maksymalnego przyspieszenia przyspiesza rozwiązanie Max-Flow LP, być może poprzez uzupełniające się warunki luzu?
źródło
Odpowiedzi:
W najgorszym przypadku samo cięcie minimalne nie przekazuje wielu informacji o maksymalnym przepływie. Rozważmy wykres w którym minimum s , t -cut ma wartość w . Jeśli przedłużę G , dodając nowy wierzchołek s ′ i krawędź ( s ′ , s ) o wadze w , minimalne s ′ , t -cut na nowym wykresie składa się tylko z krawędzi ( s ′ , s )G = ( V, E) s , t w sol s′ ( s′, s ) w s′, t ( s′, s ) ale to nie daje żadnych informacji o tym, jak uzyskać jednostek przepływu od s do t .w s t
W rzeczywistości minimalne cięcie mówi o wartości przepływu, ale nie o tym, jak go osiągnąć. Oznacza to, że znajomość minimalnego cięcia może przyspieszyć znalezienie przepływu co najwyżej przez czynnik logarytmiczny, ponieważ moglibyśmy przeprowadzić wyszukiwanie binarne, aby znaleźć wartość cięcia.
źródło
Z pewnością istnieją algorytmy, które pozwalają obliczyć minimalne cięcie przed obliczeniem maksymalnego przepływu. Dwa takie algorytmy to „push push” i pseudoprzepływowe algorytmy, które są ze sobą ściśle powiązane. Ten ostatni jest bardziej wydajny. Oba te algorytmy wykorzystują specjalne właściwości wykresu resztkowego, które iteracyjnie poprawiają, aby uzyskać maksymalny przepływ z minimalnego cięcia. Aby uzyskać szczegółowe informacje, zdecydowanie polecam przeczytanie kodu i dokumentów.
Aby rozwinąć przypadek etykiety push push, gdy algorytm nie może przepchnąć więcej przepływu do zlewu, gwarantuje się, że obliczył minimalne cięcie. Ta część algorytmu nazywa się fazą 1 z powodu braku lepszej nazwy. Faza 2 jest bardziej wydajnym etapem, w którym przekształca minimalne cięcie w maksymalny przepływ poprzez iteracyjne anulowanie cykli na wykresie resztkowym za pomocą pierwszego wyszukiwania z jedną głębokością i wypychanie nadmiaru z powrotem do źródła. Uważam, że faza 2 może być bezobjawowo bardziej wydajna niż faza 1.
źródło