Residual network
= Residual network
{title2=$G_f$}
For a <feasible flow> $f$, each original directed <edge> $u\to v$ supplies a forward <residual network> <edge> of capacity $c_{uv}-f_{uv}$ and a backward one $v\to u$ of capacity $f_{uv}$; zero-capacity residual <edges> may be omitted. The forward <edge> permits an increase, while the backward <edge> permits cancellation of existing <flow>. In particular, backward residual capacity is the amount already sent, rather than unused original capacity. If both original orientations exist, keep their residual contributions separate, or add capacities for contributions with the same direction. An <augmenting path> uses these permitted changes while preserving <flow conservation> and the <capacity constraints>.
To see why cancellation matters, give all five directed <edges> $s\to a$, $s\to b$, $a\to b$, $a\to t$, $b\to t$ unit <flow network edge capacities>. Starting from zero <flow>, an <augmenting path> $s\to a\to b\to t$ carrying $1$ yields
$$
(f_{sa},f_{sb},f_{ab},f_{at},f_{bt})=(1,0,1,0,1),\qquad |f|=1.
$$
The remaining unused original <edges> are $s\to b$ and $a\to t$, which do not form a source-to-sink <graph path>. However, the backward residual <edge> $b\to a$ has capacity $f_{ab}=1$. Consequently the <residual network> contains the <augmenting path> $s\to b\to a\to t$, with residual capacities $1,1,1$.
Augment by $1$: increase $f_{sb}$ and $f_{at}$ from $0$ to $1$, and decrease $f_{ab}$ from $1$ to $0$. The result is
$$
(f_{sa},f_{sb},f_{ab},f_{at},f_{bt})=(1,1,0,1,1),\qquad |f|=2.
$$
Now <flow conservation> is $1=0+1$ at $a$ and $1+0=1$ at $b$. The final <flow> sends one unit along each of $s\to a\to t$ and $s\to b\to t$. The <cut of a flow network> $S=\{s\}$ has <cut capacity> $1+1=2$, proving this is a <maximum flow>. Traversing $b\to a$ in the <residual network> revised the earlier routing decision; it did not send actual traffic along a nonexistent original <edge>.
\Image[/residual-flow-rerouting.png]
{title=Backward residual capacity reroutes the first unit of flow}
{description=Before: one unit follows s to a to b to t. Middle: the residual augmenting path s to b to a to t cancels flow on a to b. After: two units use the separate paths, and the middle original edge carries zero flow.}