= Solution
A <flow network> is a finite <directed graph> $G=(V,E)$ with nonnegative <flow network edge capacities> $c_e$, together with distinct source and sink <vertices> $s,t$. A <feasible flow> in the nonnegative directed-<edge> convention is a <function> $f:E\to\mathbb R_{\geq0}$ satisfying the <capacity constraints> and <flow conservation>:
$$
0\leq f_{uv}\leq c_{uv}\quad(uv\in E),\qquad
\sum_{u:uv\in E}f_{uv}=\sum_{w:vw\in E}f_{vw}\quad(v\notin\{s,t\}).
$$
Its <flow value> is the net outflow at the source,
$$
|f|=\sum_{w:sw\in E}f_{sw}-\sum_{u:us\in E}f_{us},
$$
which equals the net inflow at the sink by <flow conservation>.
A <cut of a flow network> is a <partition of a set> $(S,V\setminus S)$ with $s\in S$ and $t\notin S$. Its <cut capacity> counts only directed <edges> leaving $S$:
$$
c(S,V\setminus S)=\sum_{u\in S,\ v\notin S:\,uv\in E}c_{uv}.
$$
The net <flow> across the <cut of a flow network> subtracts <flow> on <edges> returning into $S$, and equals $|f|$.
For the following parts, a <circulation with vertex demands> has no exceptional source or sink in the original <directed graph>. Instead it satisfies net inflow minus net outflow equal to $d_v$ at every <vertex>. Thus positive demands consume <flow>, and negative demands supply <flow>.
Back to article page
