Sieć przepływowa (ang. flow network) jest spójnym grafem skierowanym G = (V,E) (ang. connected directed graph), w którego krawędziach odbywa się przepływ (ang. flow) jakiegoś czynnika (wody, gazu, prądu, informacji, towarów, pasażerów itp.). Przepływ jest możliwy tylko w kierunku zwrotu krawędzi grafu.

W sieci przepływowej wyróżnia się jeden wierzchołek s, z którego wychodzą przepływy – jest to tzw. źródło (ang. source), oraz jeden wierzchołek t, do którego zbiegają się przepływy – jest to tzw. ujście (ang. sink). Możemy wyobrazić sobie, iż czynnik przepływający poprzez sieć jest wytwarzany w źródle s, następnie przemieszcza się poprzez krawędzie grafu docierając różnymi drogami do ujścia t, gdzie jest w jakiś sposób odprowadzany.

Z każdą krawędzią grafu (w terminologii sieci przepływowych krawędzie nazywamy kanałami – ang. chanels) skojarzony jest parametr określający tzw. przepustowość (ang.capacity), która oznacza maksymalną ilość czynnika mogącego przez tę krawędź przepływać (tzn. czynnika przepływającego przez kanał może być mniej od jego przepustowości, lecz nigdy więcej). Przepustowość jest nieujemną funkcją rzeczywistą oznaczaną zwykle przez c(u,v), gdzie u i v ∈ V. Jeśli wierzchołki u i v są połączone kanałem, czyli (u,v) ∈ E, to przepustowość tego kanału spełnia warunek c(u,v) ≥ 0. Jeśli wierzchołki u i v nie są połączone kanałem, czyli (u, v) ∉ E, to c(u,v) = 0. Interpretacja tego faktu jest bardzo prosta – przepustowość odnosi się tylko do istniejących w sieci kanałów. Jeśli kanał nie istnieje, to nie może wystąpić w nim przepływ, zatem jego przepustowość jest zerowa.

Na powyższym rysunku przedstawiamy bardzo prosty przykład sieci przepływowej. Jej graf składa się z 5 wierzchołków: źródła s, trzech wierzchołków pośredniczących A, B i C oraz z ujścia t. Czerwonymi strzałkami zaznaczono kierunki przepływów. Granatowe liczby określają przepustowość kanałów. Zwróć uwagę, że w źródle wszystkie przepływy są wychodzące. Podobnie w ujściu wszystkie przepływy są wchodzące.

Przepływ to funkcja rzeczywista o argumentach będących parą wierzchołków grafu, oznaczana zwykle przez f(u,v). Funkcja przepływu musi spełniać trzy warunki:

Ograniczenia przepustowości (ang. capacity constraints)

Dla każdej pary wierzchołków u i v ∈ V zachodzi f(u,v) ≤ c(u,v).

Warunek ten mówi, iż przepływ w kanale (u,v) ∈ E nie może przekroczyć jego przepustowości. Zwróć uwagę, iż z warunku tego i własności przepustowości kanału wynika od razu, iż jeśli pomiędzy wierzchołkami u i v nie ma kanału, to przepływ  f(u,v) = 0, ponieważ c(u,v) = 0.

Skośna symetria (ang. skew symmetry)

Dla każdej pary wierzchołków u i v ∈ V zachodzi f(u,v) = -f(v,u). Warunek ten oznacza, iż przepływ w odwrotnym kierunku jest ujemny. Z warunku tego wynika od razu, iż f(u,u) = -f(u,u) = 0 – przepływ pomiędzy tym samym wierzchołkiem grafu jest zawsze zerowy.

Zachowanie przepływu (ang. flow conservation)

Dla każdego wierzchołka u ∈ V \ {s,t} suma wszystkich przepływów f(u,v), v ∈ V, jest równa zero. Warunek ten oznacza, iż suma wszystkich przepływów wpływających do wierzchołka jest równa sumie przepływów wypływających z wierzchołka.

Funkcję f(u,v) nazywamy przepływem netto (ang. net flow) od wierzchołka u do wierzchołka v. Funkcja ta może przyjmować wartości dodatnie i ujemne.

Przepływ sieci jest definiowany jako suma przepływów netto ze źródła s do wszystkich pozostałych wierzchołków sieci:

Ponieważ przepływ netto f(u,v) = 0, jeśli pomiędzy wierzchołkami u i v nie istnieje kanał, to przepływ sieci można w prosty sposób określić sumując przepływy netto z  wierzchołka s do wszystkich jego sąsiadów, czyli:

Jeśli graf sieci przepływowej będzie reprezentowany w pamięci komputera za pomocą list sąsiedztwa, to wierzchołki sąsiednie znajdziemy bardzo szybko odczytując je po kolei z listy sąsiedztwa wierzchołka s. Takie podejście pozwala przyspieszyć wyliczanie przepływu sieci.

Załóżmy, że mamy daną sieć przepływową w postaci grafu skierowanego G = (V,E), przepustowości c(u,v) oraz przepływów f(u,v), gdzie u,v ∈ V. Dla uproszczenia przyjmijmy, iż przepustowości c(u,v) i przepływy f(u,v) posiadają wartości całkowite (wartości wymierne sprowadza się do całkowitych poprzez przemnożenie przez odpowiednio dobrany współczynnik).

W powyższej sieci przepływowej zaznaczyliśmy dla każdego kanału jego przepływ:przepustowość. Na przykład w kanale A-C jest przepływ równy 3, a przepustowość tego kanału wynosi 5.

Przepustowość rezydualna c_f(u,v) (ang. residual capacity) danego kanału (u,v) jest równa różnicy przepustowości oraz przepływu w tym kanale:

cf(u,v) = c(u,v)-f(u,v)

Ponieważ:

c(v,u) = 0
f(v,u) =-f(u,v)

to

cf(v,u) = 0-(-f(u,v)) = f(u,v)

Przepustowości rezydualne liczy się również w kierunku przeciwnym, chociaż w sieci może nie występować kanał zwrotny. W takim przypadku, zgodnie z definicją przepustowości i własnością skośnej symetrii przepływu, mamy:

cf(v,u) = c(v,u)-f(v,u)

Przepustowość rezydualna w kierunku zgodnym ze zwrotem kanału jest "zapasem" przepływu, który dodatkowo można przez ten kanał przepuścić. W kierunku przeciwnym jest natomiast równa aktualnemu przepływowi w kanale.

Przepustowości rezydualne indukują tzw. sieć rezydualną (ang. residual network), która zawiera wszystkie wierzchołki oryginalnej sieci przepływowej oraz krawędzie łączące wierzchołki, dla których przepustowość rezydualna jest większa od zera – oznacza to, iż w sieci rezydualnej nie umieszczamy krawędzi pomiędzy wierzchołkami u i v, jeśli c_f(u,v) = 0. Na poniższym rysunku przedstawiamy sieć rezydualną dla przykładowej sieci przepływowej:

→

W otrzymanej przez nas sieci rezydualnej każdy kanał pierwotnej sieci przepływowej jest reprezentowany przez dwa przeciwnie skierowane kanały. Ponieważ sieć rezydualna jest zwykle modyfikowana przez różne algorytmy przepływowe, umówmy się, iż dany kanał nie "istnieje" w sieci rezydualnej, jeśli jego przepustowość rezydualna spadnie do 0 – tzn. fizycznie kanał może istnieć, ale nie można już przez niego przepuszczać więcej przepływu – staje się on jakby nieużyteczny, niedrożny. Takie podejście znakomicie ułatwia tworzenie sieci rezydualnej.

W sieci przepływowej może występować wiele źródeł oraz wiele ujść:

Na szczęście taką sieć można w bardzo prosty sposób sprowadzić do sieci z jednym źródłem i z jednym ujściem. W tym celu dodajemy jeden wierzchołek superźródła S oraz jeden wierzchołek superujścia T. Superźródło S łączymy kanałami z poszczególnymi źródłami s₀,s₁, … Przepustowość kanałów jest sumą przepustowości kanałów wychodzących ze źródeł w pierwotnej sieci. Z kolei poszczególne ujścia t₀,t₁, … łączymy kanałami z superujściem T. Przepustowości tych kanałów są sumą przepustowości kanałów dochodzących do ujść. Nasza sieć będzie teraz wyglądała następująco:

Przepływ sieci jest równy sumie przepływów sieciowych poszczególnych źródeł i jest generowany przez superźródło:

Czasami mamy do czynienia z przypadkiem, gdy ograniczony zostaje maksymalny przepływ przez węzeł – np. bez względu na przepustowości autostrad wchodzących do miasta i wychodzących z niego Rada Miejska postanowiła ograniczyć ruch samochodowy przepływający przez miasto (np. ze względu na ochronę zdrowia mieszkańców). Zatem otrzymujemy sieć przepływową, w której oprócz przepustowości kanałów mamy również przepustowość węzłów. Sieć taką powinniśmy sprowadzić do zwykłej sieci przepływowej, co ułatwi jej przetwarzanie przez algorytmy przepływowe.

→

Zadanie rozwiązujemy w bardzo prosty sposób. Węzeł z ograniczeniem przepływu zastępujemy dwoma węzłami. Do pierwszego z nich podłączamy wszystkie kanały wejściowe. Do drugiego węzła podłączamy wszystkie kanały wyjściowe. Następnie oba węzły łączymy kanałem o przepustowości równej maksymalnemu przepływowi dozwolonemu w pierwotnym węźle. W wyniku otrzymujemy zwykłą sieć przepływową.