= Reverse residual rerouting in a six-node flow
{title2=$1\to2\to4\to3\to5\to6$}
For arc capacities $(c_{12},c_{13},c_{24},c_{34},c_{35},c_{46},c_{56})=(3,3,2,2,3,3,2)$, the feasible flow $(1,3,1,2,1,3,1)$ has value four. The displayed residual path has bottleneck one and traverses $4\to3$ opposite to the original arc $3\to4$. Augmentation cancels one unit there and gives $(2,3,2,1,2,3,2)$ of value five. The sink cut has capacity five, proving optimality. Reverse residual arcs are what permit rerouting instead of only adding flow along unused forward arcs.
Back to article page
