= Flow network
{title2=$(G,c,s,t)$}
{wiki}
A <flow network> is a <directed graph> $G=(V,E)$ with distinct source and sink <vertices> $s,t$ and a nonnegative <flow network edge capacity> $c_{uv}$ on each directed <edge> $(u,v)$. In the finite setting here, every <flow network edge capacity> is a finite real number. A <feasible flow> assigns a nonnegative amount $f_{uv}$ to each original directed <edge>, satisfies the <capacity constraints>, and obeys <flow conservation> at every other <vertex>:
$$
0\leq f_{uv}\leq c_{uv},\qquad
\sum_{u:(u,v)\in E}f_{uv}=\sum_{w:(v,w)\in E}f_{vw}\quad(v\notin\{s,t\}).
$$
These are nonnegative arc amounts. The antisymmetric convention in <flow> instead records net amounts $\theta_{uv}=f_{uv}-f_{vu}$, taking a missing arc amount as zero. The two conventions express the same <flow conservation>; keeping them distinct makes backward <residual network> <edges> easier to interpret.
Think of <vertices> as routers, directed <edges> as communication links, <flow network edge capacities> as available bandwidth, and <flow> as a steady transmission rate. An intermediate router can distribute incoming traffic among outgoing links, but <flow conservation> prevents it from creating traffic. The <maximum flow problem> asks how much total traffic can pass from $s$ to $t$, allowing several <graph paths> to share the work. The same <flow network> language models transportation and abstract resource allocation.https://ocw.mit.edu/courses/6-854j-advanced-algorithms-fall-2008/4064d889e5033a9915327a777d12b592_notes_flow.pdf[Goemans, Network flows, introduction and maximum flow formulation]{ref}
Our running <flow network> has <vertices> $V=\{s,a,b,t\}$ and exactly five directed <edges>, with <flow network edge capacities>
$$
(c_{sa},c_{sb},c_{ab},c_{at},c_{bt})=(3,2,1,2,3).
$$
The cross <edge> $a\to b$ lets traffic entering $a$ use spare capacity on $b\to t$. With this <edge> removed, the two separate <graph paths> can carry only $\min(3,2)+\min(2,3)=4$; including it will let the <maximum flow> reach $5$. Thus a link's usefulness depends on the rest of the <flow network>, rather than just its own <flow network edge capacity>.
Back to article page
