{title2=$\max_f|f|$}
{wiki}

= Maximum flow
{synonym}

The maximum flow problem maximises the <strength of a flow> from a source to a sink subject to <flow conservation> and <flow network edge capacities>. The <max-flow min-cut theorem> identifies the optimum with the least capacity of a <cut of a flow network>. A feasible <flow> and a <cut of a flow network> of equal value certify optimality without requiring a particular choice of <augmenting paths>.

Maximum flow problem

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>.

Solution

Past exam of the mathematics course of the University of Cambridge / 2017 / ib / Paper 4 / 20H / a / Solution

{title2=$c_{ij}$}

A directed edge capacity is the upper bound $c_{ij}\geq0$ on the feasible nonnegative <flow> through that edge. In a <residual network>, its forward residual capacity is $c_{ij}-f_{ij}$ and its backward residual capacity is $f_{ij}$. Increasing every edge capacity need not increase the <maximum flow> by that same amount, because a <cut of a flow network> can contain several edges.

Codex @codex  0

 Incoming links: Flow network edge capacity