PL 
EnglishDomyślny
Українська📦 Maksymalny przepływ / minimalny przekrój
Prześledź algorytm Forda–Fulkersona (Edmondsa–Karpa) krok po kroku w sieci przepływowej: BFS znajduje ścieżki powiększające, przepływ płynie po grafie residualnym, a na końcu ujawnia się minimalny przekrój, gdzie max-flow = min-cut.
O tej symulacji
Ta symulacja uruchamia algorytm Edmondsa-Karpa, wariant Forda-Fulkersona oparty na przeszukiwaniu wszerz, na skierowanej sieci z ograniczeniami przepustowości, aby znaleźć maksymalny przepływ ze źródła s do ujścia t. Każde kliknięcie Krok wykonuje jedną pełną iterację: BFS przeszukuje graf resztkowy w poszukiwaniu najkrótszej ścieżki powiększającej, przepycha przepływ równy przepustowości wąskiego gardła tej ścieżki i aktualizuje przepustowości resztkowe (w tym krawędzie odwrotne, które pozwalają algorytmowi później „cofnąć” przepływ). Gdy BFS nie może już dotrzeć do ujścia, algorytm się zatrzymuje i ujawnia minimalny przekrój — zgodnie z twierdzeniem o maksymalnym przepływie i minimalnym przekroju jego przepustowość zawsze równa się znalezionemu maksymalnemu przepływowi.
🔬 Co przedstawia
Graf resztkowy na żywo dla jednej z pięciu gotowych sieci (lub losowo wygenerowanego warstwowego DAG-a). Niebieskie krawędzie przenoszą przepływ, czerwone są nasycone (przepływ równy przepustowości), a zielona oznacza bieżącą ścieżkę powiększającą znalezioną przez BFS. Gdy nie pozostanie żadna ścieżka powiększająca, złote krawędzie oznaczają minimalny przekrój, a wypełnienie wierzchołków pokazuje, po której stronie przekroju — osiągalnej ze s (zielona) lub nie (pomarańczowa) — każdy wierzchołek się znajduje.
🎮 Jak korzystać
Wybierz sieć z listy rozwijanej Gotowa sieć, a następnie naciśnij Krok, aby wykonać jedną iterację Edmondsa-Karpa naraz, lub Autoodtwarzanie, aby uruchomić ją automatycznie z prędkością ustawioną suwakiem Prędkość animacji (Pauza ją zatrzymuje, Reset wczytuje wybraną sieć od nowa). Obserwuj panel Statystyki na żywo, pokazujący bieżącą wartość przepływu, przepustowość minimalnego przekroju po jej znalezieniu, liczbę wykonanych ścieżek powiększających oraz liczbę przeprowadzonych iteracji BFS.
💡 Czy wiesz, że?
Ponieważ Edmonds-Karp zawsze powiększa wzdłuż najkrótszej ścieżki (o najmniejszej liczbie krawędzi) w grafie resztkowym, gwarantowane jest zakończenie w co najwyżej O(V·E) powiększeniach niezależnie od przepustowości krawędzi — w przeciwieństwie do zwykłej metody Forda-Fulkersona, którą na przeciwnie dobranych grafach o całkowitoliczbowych wagach można zmusić do ogromnej, a nawet nieskończonej liczby drobnych powiększeń.
Najczęściej zadawane pytania
Jaki algorytm faktycznie uruchamia ta symulacja?
Uruchamia Edmondsa-Karpa: wielokrotne przeszukiwanie wszerz grafu resztkowego w poszukiwaniu najkrótszej dostępnej ścieżki powiększającej ze źródła do ujścia, a następnie przepychanie przepływu równego wąskiemu gardłu tej ścieżki (minimalnej przepustowości resztkowej) wzdłuż każdej krawędzi na ścieżce. To konkretna, dobrze zachowująca się implementacja ogólnej metody Forda-Fulkersona.
Czym jest graf resztkowy i po co istnieją krawędzie odwrotne?
Graf resztkowy śledzi, ile dodatkowej przepustowości pozostaje na każdej krawędzi po przepchnięciu przepływu. Każda oryginalna krawędź otrzymuje sparowaną krawędź odwrotną o przepustowości równej już wysłanemu przepływowi; przepchnięcie przepływu wzdłuż tej odwrotnej krawędzi skutecznie anuluje część przepływu w przód. Te odwrotne krawędzie pozwalają algorytmowi poprawić wcześniejszy, nieoptymalny wybór trasy w kolejnej iteracji.
Jak znajdowany jest minimalny przekrój po zatrzymaniu algorytmu?
Gdy BFS ze źródła nie może już dotrzeć do ujścia w grafie resztkowym, symulacja oznacza każdy wierzchołek wciąż osiągalny ze źródła jako „stronę S”, a każdy pozostały jako „stronę T”. Minimalny przekrój składa się z oryginalnych krawędzi prowadzących z wierzchołka po stronie S do wierzchołka po stronie T, a suma ich przepustowości daje przepustowość przekroju — którą twierdzenie o maksymalnym przepływie i minimalnym przekroju gwarantuje jako równą wartości maksymalnego przepływu.
Co oznaczają liczby w panelu Statystyki?
Bieżąca wartość przepływu to całkowity przepływ przepchnięty dotąd ze źródła do ujścia; Przepustowość minimalnego przekroju pojawia się dopiero po zakończeniu algorytmu i równa się ostatecznemu maksymalnemu przepływowi; Ścieżki powiększające liczy, ile udanych ścieżek BFS przeniosło przepływ; Iteracje BFS liczy każde wykonane przeszukiwanie, w tym ostatnie, które nie dociera do ujścia i wyzwala zakończenie.
Dlaczego Edmonds-Karp zawsze się kończy, w przeciwieństwie do naiwnego Forda-Fulkersona?
Ponieważ Edmonds-Karp zawsze wybiera najkrótszą ścieżkę powiększającą według liczby krawędzi, można udowodnić, że odległość od źródła do dowolnego wierzchołka nigdy nie maleje między iteracjami, co ogranicza całkowitą liczbę powiększeń do O(V·E). Zwykły Ford-Fulkerson nie ma takiej reguły wyboru ścieżki, więc na pewnych grafach ze źle dobranymi ścieżkami może wymagać znacznie więcej iteracji, a przy niewymiernych przepustowościach może w ogóle się nie zakończyć.