Augmenting Paths and Ford-Fulkerson

Given a flow network with capacities $c(u,v)$ and a feasible flow $f$, the residual graph $G_f$ records how much additional flow each edge can carry.

For every edge $(u,v)$ in the original network, $G_f$ may contain up to two edges:

• A forward residual edge $(u,v)$ with capacity

$$c_f(u,v) = c(u,v) - f(u,v),$$

representing how much more flow can be pushed along $(u,v)$.

• A backward residual edge $(v,u)$ with capacity

$$c_f(v,u) = f(u,v),$$

representing how much existing flow on $(u,v)$ can be cancelled by routing in the reverse direction.

Only residual edges with strictly positive capacity are included in $G_f$.

For instance, if an edge $(u,v)$ has capacity $10$ and currently carries flow $7$, then $G_f$ contains

$$c_f(u,v) = 10 - 7 = 3, \qquad c_f(v,u) = 7.$$

We can push up to $3$ more units forward along $(u,v)$, or cancel up to $7$ units by routing flow backward.