Max-flow, residual graphs and matching

Flow obeys 0≤f≤capacity and conservation outside source/sink. Residual edges represent remaining forward capacity and the ability to undo prior flow. Reverse edges model rerouting, not physical extra pipes.

Ford–Fulkerson augments a path by its bottleneck. Integer capacities ensure termination, while general irrational capacities with poor path choice can cause problems. Edmonds–Karp uses shortest residual paths by BFS, bounding time by O(VE²). Dinic uses level graphs and blocking flows.

Max-flow=min-cut supplies a certificate using residual reachability. Bipartite matching reduces to unit-capacity source-left-right-sink flow; Hopcroft–Karp runs in O(E√V). Min-cost flow is distinct: maximum volume need not be cheapest.

Why reverse edges are essential

A flow decision may need revision. Sending f units along u→v decreases forward residual capacity and increases reverse v→u capacity. The reverse edge is permission to undo an earlier choice, not a new physical pipe. Augment by the path’s minimum residual capacity and update every edge.

Flow conservation holds away from source and sink, with 0≤f≤c on each edge. Parallel edges and undirected capacities need explicit representation; one matrix cell can conflate real and reverse-edge semantics.

The max-flow/min-cut theorem connects optimal flow with a cut. When no augmenting path remains, vertices reachable from the source in the residual graph define a cut whose capacity equals the flow. Edmonds-Karp chooses paths with BFS and has O(VE²) complexity based on path-length behaviour. Arbitrary Ford-Fulkerson paths can fail to terminate under irrational-capacity models.

Foundation: Verify conservation after every augmentation. Intermediate: Construct an improvement requiring a reverse edge. Advanced: Reduce bipartite matching to unit-capacity flow and return matching witnesses and min-cut certificates separately.

# A residual augmentation along s -> a -> t.
r = {("s","a"):3, ("a","t"):2, ("a","s"):0, ("t","a"):0}
path = [("s","a"),("a","t")]
bottleneck = min(r[e] for e in path)
for u,v in path:
    r[u,v] -= bottleneck
    r[v,u] += bottleneck
assert r["a","s"] == 2 and r["a","t"] == 0