Od 2010 · Ponad 2 mln uruchomień narzędzi miesięcznie
Od 2010
Dodaj do Chrome

Moje Narzędzia

Tryb Automatyczny

Nie zapisano jeszcze żadnych narzędzi.

Uaktualnij do Wersji Premium
Powiązane narzędzia
Kalkulator Sortowania TopologicznegoEkstraktor liczb
Strona główna > Matematyka > Zaawansowane działania matematyczne
 

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

Oblicz maksymalny przepływ ze źródła do ujścia w sieci z ograniczeniami przepustowości algorytmem Forda-Fulkersona z Edmonds-Karp. Animuje ścieżkę powiększającą i pokazuje przepustowości resztkowe, nasycone krawędzie i minimalny przekrój.

BezpłatneBez rejestracjiNatychmiastowe wyniki
Kalkulator Przepływu w Sieci (Maksymalny Przepływ)Wypróbuj teraz — za darmo ▼
Szybkie przykłady:
Podręcznikowy (6 węzłów) Mała sieć Klasyczny CLRS Dwudzielny Wprowadzanie macierzy
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 oddzielone przecinkami lub spacjami, jedna na wiersz macierzy. Domyślnie S, A, B, …, T.

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:

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

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

DziedzinaZastosowanie
Transport i logistykaIle towaru można przesłać siecią kolejową/drogową/urociągiem dziennie z punktu A do B?
Skojarzenia dwudzielnePrzypisywanie zadań pracownikom. Przepływ o jednostkowej wydajności daje maksymalne skojarzenie.
Segmentacja obrazuAlgorytm min-cut Boykova–Kolmogorova w wizji komputerowej oddziela tło od pierwszego planu.
Niezawodność sieciPrzekrój minimalny identyfikuje najsłabsze ogniwa, których awaria rozłączy sieć.
HarmonogramowanieProblemy wyboru i domknięć można sprowadzić do szukania minimalnego przekroju.
Eliminacje sportoweOkreś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:

  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

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.

Zaawansowane działania matematyczne:

Popularne i zaktualizowane narzędzia:

Kalkulator tętna maksymalnegoKalkulator Maksimum Jednego Powtórzenia (1RM)Kalkulator marży przepływów pieniężnychZobacz wszystkie →
Strona główna > Matematyka > Zaawansowane działania matematyczne > Kalkulator Przepływu w Sieci (Maksymalny Przepływ)