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 Minimalnego Drzewa RozpinającegoKalkulator Najkrótszej Ścieżki DijkstryKalkulator Sortowania TopologicznegoKalkulator Macierzy Sąsiedztwa
Strona główna > Matematyka > Zaawansowane działania matematyczne
 

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

Kalkulator przepływu w sieci (maksymalny przepływ) MiniWebtool wyznacza przepływ od źródła do ujścia w skierowanej sieci o ograniczonej przepustowości. Ścieżki powiększające Edmondsa-Karpa, przepustowości rezydualne i końcowe cięcie minimalne pokazują, jak ustala się maksimum.

Potrzebujesz pomocy z narzędziem? Zapytaj AI
Gemini (kopiuj i otwórz)

W Gemini wklej skopiowane pytanie do czatu. Możesz je też skopiować poniżej.

Zobacz pytanie

3 darmowe użycia dziennieBez rejestracjiNatychmiastowe wyniki
Kalkulator Przepływu w Sieci (Maksymalny Przepływ)Wypróbuj teraz — za darmo ▼
Przepływ maksymalny = przekrój minimalny: 4 + 6 + 4 + 5 = 19 = 10 + 9

Wpisz poniżej krawędzie wraz z przepustowościami, aby uzyskać przepływ maksymalny, wszystkie ścieżki powiększające i przekrój minimalny.

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.

W skrócie

Kalkulator Przepływu w Sieci (Maksymalny Przepływ) znajduje maksymalny przepływ od źródła do ujścia w sieci skierowanej z przepustowościami krawędzi. Stosuje algorytm Edmondsa-Karpa i pokazuje każdą ścieżkę powiększającą, przepustowości rezydualne i przekrój minimalny.

Kalkulator Przepływu w Sieci (Maksymalny Przepływ): funkcje w skrócie
FunkcjaCo otrzymujeszPrzydatne dla
Dwa formaty danychWpisz listę krawędzi w wierszach, np. A -> B : 10, albo kwadratową macierz przepustowości z opcjonalnymi etykietami wierzchołków.Zadania z teorii grafów i ćwiczenia algorytmiczne
Źródło i ujścieWybierz dowolny wierzchołek źródłowy i ujściowy. Jeśli pola pozostaną puste, zostaną użyte S i T.Sieci, w których wierzchołki mają własne nazwy
Ścieżki powiększająceOdtwórz każdą ścieżkę algorytmu Edmondsa-Karpa za pomocą przycisków odtwarzania, poprzednia, następna i resetowania oraz prędkości Wolna, Normalna lub Szybka.Śledzenie algorytmu krok po kroku
Przekrój minimalnyWymienia strony źródłową i ujściową przekroju oraz wyróżnia nasycone krawędzie. Jego przepustowość jest równa wartości maksymalnego przepływu.Potwierdzenie optymalności przepływu
Trzy macierzePrzełączaj się między macierzą przepustowości, przepływu i rezydualną oraz kopiuj macierz.Ręczne sprawdzanie przepustowości rezydualnych
Tabela krawędziDla każdej krawędzi pokazuje przepustowość, przepływ, wartość rezydualną, pasek wykorzystania i wskaźnik nasycenia; kolory krawędzi odpowiadają wartościom od 0 do 100 procent.Wykrywanie krawędzi będących wąskimi gardłami
Limity rozmiaruMaksymalnie 30 wierzchołków i 200 krawędzi. Pętle własne są odrzucane, a przepustowości mogą być ułamkowe.Zachowanie czytelności grafu i macierzy

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

Kalkulator Przepływu w Sieci (Maksymalny Przepływ): 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

Porozmawiaj ze swoją ulubioną AI

Gemini (kopiuj i otwórz)

W Gemini wklej skopiowane pytanie do czatu. Możesz je też skopiować poniżej.

Zobacz pytanie

Zaawansowane działania matematyczne:

Rozwiązywanie matematykiCo chcesz obliczyć?

Rozwiązywanie matematyki

Przykłady
Więcej wyrażeń

Wybierz przykład, zmień liczby i rozwiąż. log ma podstawę 10; ln to logarytm naturalny.

Liczby i dzielniki

Ułamki i dzielenie

Potęgi, pierwiastki i logarytmy

Algebra i równania

Rachunek różniczkowy i całkowy

Geometria i trygonometria

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)