Co to jest przekrój minimalny sieci przepływowej?

Przekrój to podział wierzchołków na dwa zbiory S i T taki, że źródło znajduje się w S, a ujście w T. Przepustowość przekroju to suma przepustowości krawędzi prowadzących z S do T. Przekrój minimalny to przekrój o najmniejszej możliwej przepustowości. Twierdzenie Forda-Fulkersona dowodzi, że wartość maksymalnego przepływu jest zawsze równa przepustowości minimalnego przekroju.

Dlaczego narzędzie używa BFS do szukania ścieżek powiększających?

Wybór ścieżek powiększających za pomocą przeszukiwania wszerz (Edmonds-Karp) gwarantuje zakończenie obliczeń w czasie wielomianowym, niezależnie od przepustowości krawędzi. Zwykła metoda Forda-Fulkersona z dowolną strategią szukania ścieżek może zapętlić się na wykładniczą liczbę iteracji przy niefortunnych danych, a przy przepustowościach niewymiernych może nigdy się nie zakończyć. BFS znajduje również najkrótsze ścieżki powiększające.

Co oznacza krawędź nasycona?

Krawędź jest nasycona, gdy jej przepływ jest równy jej przepustowości, co oznacza, że nie można przez nią przesłać więcej jednostek. Nasycone krawędzie stanowią wąskie gardła sieci, a każdy przekrój minimalny składa się wyłącznie z nasyconych krawędzi prowadzących ze strony S na stronę T przekroju. Narzędzie wyróżnia nasycone krawędzie na czerwono.

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

Oblicz maksymalny przepływ od źródła do ujścia w skierowanej sieci pojemnościowej metodą Forda-Fulkersona (Edmondsa-Karpa). Animuje każdą ścieżkę powiększającą, pokazuje pojemności szczątkowe, nasycone krawędzie oraz przekrój minimalny dowodzący optymalności.

Szybkie przykłady:

Podręcznikowy (6 węzłów) Mała sieć Klasyczny CLRS Dwudzielny Wprowadzanie macierzy

↦ Lista krawędzi z przepustowościami ▦ Macierz przepustowości

Dane sieci

Format krawędzi: A -> B : 10 (strzałka plus przepustowość) lub A, B, 10. Format macierzy: jeden wiersz na linię, C[i][j] to przepustowość krawędzi i → j (użyj 0 dla braku krawędzi). Przekątna musi wynosić 0.

Etykiety macierzy (opcjonalnie)

Etykiety oddzielone przecinkami lub spacjami, jedna na wiersz macierzy. Domyślnie S, A, B, …, T.

Wierzchołek źródłowy ⭘

Wierzchołek ujścia ⬤

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

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:

Przepustowość: 0 ≤ f(u, v) ≤ c(u, v) dla każdej krawędzi (u, v) Zachowanie: Σ f(w, v) = Σ f(v, w) dla każdego v ∈ V \ {s, t} Wartość: |f| = Σ f(s, w) − Σ f(w, s) (przepływ netto opuszczający s)

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.

dopóki istnieje ścieżka powiększająca P z s do t w grafie szczątkowym: b ← min c_szczątkowa(u, v) dla krawędzi (u, v) w P prześlij b jednostek przepływu wzdłuż P // aktualizuje graf szczątkowy + przepływ zwróć całkowity przepływ |f|

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:

cap(S, T) = Σ c(u, v) dla u ∈ S, v ∈ T

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

wartość maksymalnego przepływu = przepustowość minimalnego przekroju

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ą:

S -> A : 10 S -> B : 13 A -> B : 10 B -> A : 4 B -> T : 14

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.

S A B C D T S [ 0 10 0 10 0 0 ] A [ 0 0 4 2 8 0 ] B [ 0 0 0 0 0 10 ] C [ 0 0 0 0 9 0 ] D [ 0 0 6 0 0 10 ] T [ 0 0 0 0 0 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

Dziedzina	Zastosowanie
Transport i logistyka	Ile towaru można przesłać siecią kolejową/drogową/urociągiem dziennie z punktu A do B?
Skojarzenia dwudzielne	Przypisywanie zadań pracownikom. Przepływ o jednostkowej wydajności daje maksymalne skojarzenie.
Segmentacja obrazu	Algorytm min-cut Boykova–Kolmogorova w wizji komputerowej oddziela tło od pierwszego planu.
Niezawodność sieci	Przekrój minimalny identyfikuje najsłabsze ogniwa, których awaria rozłączy sieć.
Harmonogramowanie	Problemy wyboru i domknięć można sprowadzić do szukania minimalnego przekroju.
Eliminacje sportowe	Określanie, czy drużyna ma jeszcze matematyczne szanse na tytuł mistrzowski.

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:

S → A → B → T z wąskim gardłem 4 (krawędź A-B ogranicza przepływ). Suma: 4.
S → A → D → T z wąskim gardłem 6. Suma: 10.
S → C → D → T z wąskim gardłem 4 (D-T ogranicza przepływ, zostało w nim 4). Suma: 14.
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

Wybierz format wejściowy (lista krawędzi lub macierz).
Wprowadź swoją sieć. Możesz zacząć od przykładu. W macierzy możesz też podać własne etykiety węzłów.
Podaj źródło i ujście (lub zostaw puste dla S i T).
Kliknij Oblicz Maksymalny Przepływ. Zobaczysz wartość przepływu, podział przekroju, wizualizację grafu, listę ścieżek i macierze.
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

Cytuj ten materiał, stronę lub narzędzie w następujący sposób:

"Kalkulator Przepływu w Sieci (Maksymalny Przepływ)" na https://MiniWebtool.com/pl/kalkulator-przepywu-w-sieci-maksymalny-przepyw/ z MiniWebtool, https://MiniWebtool.com/

przez zespół miniwebtool. Aktualizacja: 22 kwietnia 2026

Możesz także wypróbować nasz AI Rozwiązywacz Matematyczny GPT, aby rozwiązywać swoje problemy matematyczne poprzez pytania i odpowiedzi w języku naturalnym.

Inne powiązane narzędzia:

Kalkulator Macierzy SąsiedztwaNowy

Kalkulator Najkrótszej Ścieżki Dijkstry

Kalkulator Kolorowania GrafówNowy

Kalkulator Sortowania TopologicznegoNowy

Solver Problemu Komiwojażera (TSP)Nowy

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

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

Czym jest problem maksymalnego przepływu?

Jak działa algorytm — Ford-Fulkerson z BFS

Twierdzenie o przepływie maksymalnym i przekroju minimalnym

Funkcje stworzone do nauki

Formaty wejściowe

1. Lista krawędzi z przepustowościami

2. Macierz przepustowości

Zastosowania Maksymalnego Przepływu

Przykładowe rozwiązanie

Jak używać tego kalkulatora

Ograniczenia

Najczęściej zadawane pytania

Czym jest problem maksymalnego przepływu?

Czym jest metoda Forda-Fulkersona?

Co to jest przekrój minimalny?

Czym jest graf szczątkowy?

Więcej informacji

Inne powiązane narzędzia:

Zaawansowane działania matematyczne:

Polecane narzędzia: