Network Flows, Cuts & Matching

an augmenting path

You have routed some water and want to send more. If you can trace a route from pump to drain along pipes that all still have room — possibly including some 'undo' moves that pull back water you sent earlier — then you can push extra water along that whole route at once. Such a route is an augmenting path, and finding one means the flow is not yet maximum.

Precisely, an augmenting path is a path from s to t in the residual graph Gf in which every edge has positive residual capacity. Its bottleneck is the smallest residual capacity along the path. To augment, you add that bottleneck amount to the flow on each forward edge of the path and subtract it on each backward edge; this keeps capacities and conservation satisfied while increasing the flow value by exactly the bottleneck. For example, if the path s -> a -> b -> t has residual capacities 5, 2, 4, the bottleneck is 2, so you push 2 more units and the flow value goes up by 2. Because some of those edges may be backward (cancellation) edges, augmenting can reroute earlier flow, not just add fresh flow.

Augmenting paths are the basic move of max-flow algorithms: repeat 'find an augmenting path, push along it' until none remains. The deep fact (the augmenting-path theorem) is that a flow is maximum if and only if its residual graph has no augmenting path — so the simple stopping rule is exactly right, and at that moment the unreachable vertices reveal a minimum cut. The catch is which path you pick: an arbitrary choice (plain Ford-Fulkerson) can be slow or even non-terminating on irrational capacities, whereas always taking a shortest augmenting path (Edmonds-Karp) guarantees a polynomial number of augmentations.

With current flow on s->a->t saturating a->t, suppose the residual path s -> b -> a -> t exists, where b -> a uses a backward residual edge (canceling some a->b flow). Its bottleneck is, say, 1; augmenting pushes 1 unit, reroutes a's flow, and raises the total by 1 — a path no plain greedy would have found.

The bottleneck of the path is how much you gain; backward edges let an augmenting path undo and reroute earlier choices.

No augmenting path means maximum flow — that is a theorem, not just a heuristic stop. But the choice of path controls speed: arbitrary choices can be exponential or loop on irrational capacities; shortest-path choices (Edmonds-Karp) stay polynomial.

Also called
augmenting pathimproving path擴充路徑