Kalkulator Przepływu w Sieci (Maksymalny Przepływ)

O Kalkulator Przepływu w Sieci (Maksymalny Przepływ)

Kalkulator Przepływu w Sieci oblicza maksymalny przepływ z wybranego źródła s do wybranego ujścia t w dowolnej skierowanej sieci o określonych przepustowościach. Pod maską wykorzystuje metodę Forda-Fulkersona z szukaniem ścieżek powiększających wszerz (algorytm Edmondsa-Karpa), a następnie rejestruje każdą znalezioną ścieżkę, umożliwiając prześledzenie procesu decyzyjnego krok po kroku. Strona wynikowa prezentuje również przekrój minimalny — wąskie gardło sieci, które dowodzi optymalności uzyskanego wyniku.

Czym jest problem maksymalnego przepływu?

Sieć przepływowa to graf skierowany G = (V, E) z funkcją przepustowości c: E → ℝ_≥0. Wyróżnia się w niej dwa wierzchołki: źródło s (skąd wypływa przepływ) oraz ujście t (gdzie jest on odbierany). Przepływ f to przypisanie wartości f(u, v) ≥ 0 krawędziom, spełniające warunki:

Problem maksymalnego przepływu polega na znalezieniu takiego przepływu f, który maksymalizuje |f|. Intuicyjnie: jeśli krawędzie byłyby rurami o danej wydajności, ile litrów na sekundę można przesłać z s do t?

Jak działa algorytm — Ford-Fulkerson z BFS

Algorytm utrzymuje graf szczątkowy obok aktualnego przepływu. Dla każdej krawędzi (u, v) o wydajności c i aktualnym przepływie f, graf szczątkowy zawiera:

• krawędź szczątkową w przód (u, v) o przepustowości c − f (ile jeszcze można przesłać), oraz
• krawędź szczątkową wsteczną (v, u) o przepustowości f (ile przepływu można wycofać).

W każdej iteracji wykonuje przeszukiwanie wszerz (BFS) od s do t w grafie szczątkowym. Jeśli ścieżka zostanie znaleziona, najmniejsza wydajność na tej ścieżce — wąskie gardło — jest dodawana do przepływu na krawędziach w przód i odejmowana na krawędziach wstecznych. Jest to tzw. ścieżka powiększająca. Gdy BFS nie może już dotrzeć do t, przepływ jest optymalny.

Zastosowanie BFS (zamiast dowolnego szukania ścieżek) zamienia metodę Forda-Fulkersona w algorytm Edmondsa-Karpa, o gwarantowanym czasie działania O(V · E²). Gwarantuje to również zakończenie obliczeń przy przepustowościach niewymiernych.

Twierdzenie o przepływie maksymalnym i przekroju minimalnym

Przekrój to podział wierzchołków na dwa zbiory (S, T), gdzie s ∈ S oraz t ∈ T. Jego przepustowość to suma wydajności krawędzi prowadzących z S do T:

Twierdzenie o przepływie maksymalnym i przekroju minimalnym (Ford i Fulkerson, 1956) mówi:

Narzędzie znajduje przekrój minimalny automatycznie. Po zakończeniu algorytmu Edmondsa-Karpa uruchamia dodatkowy BFS ze źródła; osiągnięte wierzchołki tworzą zbiór S, pozostałe T. Każda krawędź łącząca S → T w oryginalnym grafie jest nasycona. Ich łączna przepustowość daje wartość max przepływu.

Funkcje stworzone do nauki

• Animacja krok po kroku. Odtwórz każdą ścieżkę powiększającą z kontrolą tempa. Zobacz, którą ścieżkę wybrał BFS i jak narastał sumaryczny przepływ.
• Trzy zsynchronizowane macierze. Przełączaj się między macierzą wydajności C, końcowym przepływem f oraz macierzą szczątkową C − f.
• Widok podziału na przekrój minimalny. Wierzchołki stron S i T są wymienione jako etykiety, a krawędzie nasycone tworzące przekrój są wyróżnione na czerwono.
• Tabela krawędzi. Dla każdej krawędzi: wydajność, przepływ, pozostała rezerwa oraz wizualny pasek nasycenia.
• Warstwowy układ grafu. Rysunek grafu jest obliczany na podstawie odległości BFS od źródła, dzięki czemu przepływ wizualnie płynie od lewej do prawej — tak jak w podręcznikach.

Formaty wejściowe

1. Lista krawędzi z przepustowościami

Jedna krawędź na linię. Format ze strzałką jest najbardziej czytelny, ale inne też działają:

Akceptowane również: A, B, 10 · A B 10 · A -> B , 10. Wiele krawędzi między tą samą parą zostanie zsumowanych.

2. Macierz przepustowości

Jeden wiersz na linię, wartości oddzielone spacjami lub przecinkami. Wpis C[i][j] to wydajność krawędzi z i do j. Użyj 0 dla braku połączenia. Macierz musi być kwadratowa, a przekątna musi wynosić 0.

Wprowadź pasujące etykiety w polu Etykiety macierzy. Jeśli je pominiesz, zostaną nadane domyślnie S, A, B, …, T.

Zastosowania Maksymalnego Przepływu

Przykładowe rozwiązanie

Przykład „Podręcznikowy” zawiera 6 węzłów ze źródłem S i ujściem T. Algorytm Edmondsa-Karpa znajduje cztery ścieżki powiększające:

1. S → A → B → T z wąskim gardłem 4 (krawędź A-B ogranicza przepływ). Suma: 4.
2. S → A → D → T z wąskim gardłem 6. Suma: 10.
3. S → C → D → T z wąskim gardłem 4 (D-T ogranicza przepływ, zostało w nim 4). Suma: 14.
4. S → C → D → B → T z wąskim gardłem 5. Suma: 19.

Algorytm kończy pracę — brak dalszych ścieżek. Przekrój minimalny to (S = {S, C}, T = {A, B, D, T}) z krawędziami S → A (wydajność 10) oraz C → D (wydajność 9), co daje sumę 19 — dokładnie wartość max przepływu.

Jak używać tego kalkulatora

1. Wybierz format wejściowy (lista krawędzi lub macierz).
2. Wprowadź swoją sieć. Możesz zacząć od przykładu. W macierzy możesz też podać własne etykiety węzłów.
3. Podaj źródło i ujście (lub zostaw puste dla S i T).
4. Kliknij Oblicz Maksymalny Przepływ. Zobaczysz wartość przepływu, podział przekroju, wizualizację grafu, listę ścieżek i macierze.
5. Uruchom animację pod grafem, aby zobaczyć jak działa algorytm krok po kroku.

Ograniczenia

• Wierzchołki: do 30 — zapewnia czytelność wizualizacji i macierzy.
• Krawędzie: do 200.
• Przepustowości: nieujemne, do 10⁹. Dozwolone wartości ułamkowe.
• Brak pętli własnych. Pętle własne (z wierzchołka do niego samego) nie przenoszą przepływu w standardowej sformułowaniu i są odrzucane.

Najczęściej zadawane pytania

Czym jest problem maksymalnego przepływu?

Pyta o to, ile maksymalnie jednostek można przesłać ze źródła do ujścia przy danych ograniczeniach przepustowości każdej drogi i zasadzie zachowania przepływu w węzłach pośrednich.

Czym jest metoda Forda-Fulkersona?

To technika iteracyjnego szukania ścieżek powiększających w grafie szczątkowym do momentu, aż żadna już nie będzie dostępna.

Co to jest przekrój minimalny?

To „najwęższe miejsce” sieci oddzielające źródło od ujścia, którego przepustowość jest równa maksymalnemu możliwemu przepływowi.

Czym jest graf szczątkowy?

To graf pomocniczy pokazujący aktualne możliwości przesłania dodatkowego przepływu lub wycofania już istniejącego.

Więcej informacji

• Problem maksymalnego przepływu — Wikipedia
• Algorytm Forda–Fulkersona — Wikipedia
• Algorytm Edmondsa–Karpa — Wikipedia
• Twierdzenie o przepływie maksymalnym i przekroju minimalnym — Wikipedia