= Solution
A finite <flow network> is a <directed graph> with distinguished source $s$, sink $t$, and nonnegative finite <flow network edge capacities> $c_{ij}$ on its directed edges. A feasible <flow> consists of numbers $f_{ij}$ satisfying
$$
0\leq f_{ij}\leq c_{ij},\qquad
\sum_j f_{ij}=\sum_j f_{ji}\quad(i\ne s,t).
$$
The second condition is <flow conservation>; absent edges contribute zero. The <strength of a flow> is its net outflow from the source,
$$
|f|=\sum_j f_{sj}-\sum_j f_{js},
$$
which equals net inflow to the sink by summing <flow conservation> over the other vertices. The <maximum flow problem> is
$$
\boxed{\text{maximise }|f|\text{ over all feasible flows}}.
$$
No assumption that a capacity-saturating flow at the source is feasible downstream is made. On a finite network a maximum exists, because the constraints define a nonempty <compact> set of edge flows and the objective is <continuous>.
Back to article page
