= Maximum flow problem
{title2=$\max_f|f|$}
{wiki}
= Maximum flow
{synonym}
= Max-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>. For the nonnegative arc amounts used in <flow network>, its objective is net outflow from the source:
$$
|f|=\sum_{v:(s,v)\in E}f_{sv}-\sum_{u:(u,s)\in E}f_{us}
=\sum_{u:(u,t)\in E}f_{ut}-\sum_{v:(t,v)\in E}f_{tv}.
$$
The equality follows by summing <flow conservation> over all internal <vertices>. Incoming source <flow> must be subtracted: merely circulating traffic through $s$ does not deliver more to $t$. The <max-flow min-cut theorem> identifies the optimum with the least <cut 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>.
For the five-<edge> <flow network> with <flow network edge capacities> $(3,2,1,2,3)$, take
$$
(f_{sa},f_{sb},f_{ab},f_{at},f_{bt})=(3,2,1,2,3).
$$
Every <capacity constraint> holds with equality. <Flow conservation> at $a$ is $3=1+2$, and at $b$ it is $2+1=3$. The <strength of a flow> is $|f|=3+2=5$, also $2+3=5$ entering $t$. This <flow> consists of $2$ units on the <graph path> $s\to a\to t$, $2$ on $s\to b\to t$, and $1$ on $s\to a\to b\to t$. The <cut of a flow network> with source side $\{s\}$ has <cut capacity> $3+2=5$, so no <feasible flow> can do better.
Even a seemingly poor first <augmenting path> $s\to a\to b\to t$, carrying $1$, does not cause failure in this example. It leaves <residual network> capacity $2$ along $s\to a\to t$ and $2$ along $s\to b\to t$. These two subsequent <augmenting paths> yield values $1$, $3$, and $5$, and produce exactly the <flow> above. Backward <residual network> <edges> become essential in the unit-capacity example under <residual network>, where this same first choice blocks every unused forward route.
Discrete assignment is another reason to study <maximum flow>. Put unit-capacity <edges> from $s$ to job <vertices>, from each job to eligible worker <vertices>, and from workers to $t$. An integral <flow> selects a <matching in a graph>: each job and worker participates at most once, and the <strength of a flow> counts assigned jobs. The <integral max-flow theorem> therefore turns maximum cardinality assignment into <maximum flow>. Minimizing assignment costs is the related <assignment problem>, modeled by <minimum-cost flow>.https://ocw.mit.edu/courses/6-854j-advanced-algorithms-fall-2008/4064d889e5033a9915327a777d12b592_notes_flow.pdf[Goemans, Network flows, assignment formulation]{ref}
Back to article page
