Потокова мережа

${\displaystyle \ G(V,E)}$ скінченний орієнтований граф, в якому кожне ребро ${\displaystyle \ (u,v)\in E}$ має додатню ємність ${\displaystyle \ c(u,v)}$. Якщо ${\displaystyle \ (u,v)\not \in E}$ ми припускаємо, що ${\displaystyle \ c(u,v)=0}$. Ми розрізняємо дві вершини: джерело ${\displaystyle \ s}$ і стік ${\displaystyle \ t}$. Потокова мережа — дійсна функція ${\displaystyle \ f:V\times V\rightarrow \mathbb {R} }$ з наступними трьома властивостями для всіх вершин ${\displaystyle \ u}$ і ${\displaystyle \ v}$:

Обмеження ємності (англ. capacity constraints):	${\displaystyle \ f(u,v)\leq c(u,v)}$. Потік уздовж ребра не може перевищити його ємність.
Скісна симетрія (англ. skew symmetry):	${\displaystyle \ f(u,v)=-f(v,u)}$. Потік мережі з ${\displaystyle \ u}$ до ${\displaystyle \ v}$ має бути протилежним до потоку з ${\displaystyle \ v}$ до ${\displaystyle \ u}$ (дивись приклад).
Збереження потоку (англ. flow conservation):	${\displaystyle \ \sum _{w\in V}f(u,w)=0}$, хіба що ${\displaystyle \ u=s}$ або ${\displaystyle \ w=t}$. Мережевий потік у вершині нульовий, за винятком джерела, яке «виробляє» потік, і стоку, який «споживає» потік.

Зауважте, що ${\displaystyle \ f(u,v)}$ це мережевий потік з ${\displaystyle \ u}$ до ${\displaystyle \ v}$. якщо граф представляє фізичну мережу і, якщо існує справжній потік, наприклад, в 4 одиниці з ${\displaystyle \ u}$ до ${\displaystyle \ v}$, і справжній потік в 3 одиниці з ${\displaystyle \ v}$ до ${\displaystyle \ u}$, тоді маємо ${\displaystyle \ f(u,v)=1}$ і ${\displaystyle \ f(v,u)=-1}$.

Залишкова ємність ребра це ${\displaystyle \ c_{f}(u,v)=c(u,v)-f(u,v)}$. Це визначає залишкову мережу позначувану ${\displaystyle \ G_{f}(V,E_{f})}$, яка дає загальну доступну ємність. Може бути ребро з ${\displaystyle \ u}$ до ${\displaystyle \ v}$ в залишковій мережі, хоча не існує ребро з ${\displaystyle \ u}$ до ${\displaystyle \ v}$ в справжній мережі. Через те, що потоки в протилежних напрямках збалансовуються, зменшення потоку з ${\displaystyle \ v}$ до ${\displaystyle \ u}$ це те саме, що збільшення потоку з ${\displaystyle \ u}$ до ${\displaystyle \ v}$. Шлях розширення це шлях ${\displaystyle \ (u_{1},u_{2},\dots ,u_{k})}$ в залишковій мережі, де ${\displaystyle \ u_{1}=s}$, ${\displaystyle \ u_{k}=t}$, і ${\displaystyle \ c_{f}(u_{i},u_{i+1})>0}$. Мережа перебуває в стані максимального потоку тоді і тільки тоді, коли не існує залишкового шляху в залишковій мережі.

Отже, ${\displaystyle \ G_{f}}$ створений із використанням графу ${\displaystyle G}$ таким чином:

1. Вершини ${\displaystyle \ G_{f}}$ = ${\displaystyle \ V}$
2. Ребра ${\displaystyle \ G_{f}}$ = ${\displaystyle \ E_{f}}$ визначені так

Для кожного ребра ${\displaystyle \ (x,y)\in E}$

    (i). Якщо ${\displaystyle \ f(x,y)<c(x,y),}$ утворити вперед-ребро ${\displaystyle \ (x,y)\in E_{f}}$ з ємністю ${\displaystyle \ c_{f}=c(x,y)-f(x,y)}$.
    (ii). Якщо ${\displaystyle \ f(x,y)>0,}$ утворити назад-ребро ${\displaystyle \ (y,x)\in E_{f}}$ з ємністю ${\displaystyle \ c_{f}=f(x,y)}$.

Цю концепцію використовує алгоритм Форда — Фалкерсона, який обчислює максимальний потік у потоковій мережі.

Іноді необхідно змоделювати мережу з більше ніж одним джерелом, тоді вводять суперджерело.[1] Воно утворене вершиною зв'язаною з кожним джерелом ребром нескінченної ємності, відтак діє як глобальне джерело. Подібна конструкція зветься суперстоком.[2]