To pytanie dotyczy złożoności czasowej algorytmu maksymalnego przepływu Forda-Fulkersona podczas korzystania z DFS w celu znalezienia ścieżek rozszerzających.
Istnieje dobrze znany przykład pokazujący, że przy użyciu DFS można potrzebować liniowej liczby iteracji w maksymalnym przepływie, patrz na przykład strona Wikipedii, do której prowadzi link powyżej.
Jednak tak naprawdę nie przekonuje mnie ten przykład: standardowa implementacja DFS nie wykazywałaby zachowania na przemian między B i C jako pierwszym węzłem ścieżki (przy użyciu nazw wierzchołków ze strony Wikipedii).
Nałóżmy więc bardzo naturalny warunek, że za każdym razem, gdy DFS odwiedza węzeł , zawsze bada sąsiadów u w tej samej kolejności. Czy są jeszcze przykłady, dla których FF z DFS używa dużej liczby iteracji?
Jako wariant załóżmy, że mamy dodatkową właściwość polegającą na tym, że różne uporządkowania sąsiadów są zgodne z pewną arbitralną, ale stałą globalną kolejnością wierzchołków. Czy to robi różnicę?
Wydaje mi się, że to dość podstawowe pytanie; Z góry przepraszam, jeśli odpowiedź jest dobrze znana, ale nie jestem ekspertem od przepływów, a niektórzy googling nic nie znaleźli.
Edycja: Odpowiedź okazuje się tak, wciąż istnieją przykłady. Zobacz rysunek 2 tego dokumentu . W tych przykładach FF z DFS przyjmują wykładniczą (w liczbie wierzchołków) liczbę iteracji. Łatwo jest udowodnić, że jest to ścisłe, tj. Że liczba iteracji jest zawsze ograniczona przez (niezależnie od wartości pojemności).
źródło
Odpowiedzi:
Jeśli listy sąsiedztwa są ustalone wcześniej, DFS zawsze kończy działanie (nawet jeśli istnieją nieracjonalne możliwości).
Patrz dziekan, goemans, immorlica - skończone zakończenie algorytmów „ścieżki rozszerzania” w obecności nieracjonalnych danych problemowych .
źródło