Network Flows, Cuts & Matching

edge capacity

Every pipe has a width: there is a hard limit on how much can pass through it per unit time. Edge capacity is that limit, attached to each edge of a flow network. A wide highway has high capacity; a narrow alley has low capacity. The whole point of a flow problem is that these per-edge limits, taken together, bound how much can travel from source to sink.

Precisely, the capacity of edge (u, v) is a number c(u, v) >= 0, and any flow f must obey the capacity constraint 0 <= f(u, v) <= c(u, v) on that edge. An edge whose flow equals its capacity, f(u, v) = c(u, v), is called saturated — it is full and cannot carry more. Capacities are usually integers in textbook problems, which has a happy consequence (the integrality theorem): if all capacities are integers, some maximum flow assigns an integer to every edge. That is what lets flow solve discrete matching and selection problems, where a fractional answer would be meaningless.

Capacity is the only thing limiting a flow on a single edge; conservation handles the junctions. It pays to be careful about a few conventions. Capacities are directed: c(u, v) and c(v, u) can differ, and an edge with no reverse arc has c(v, u) = 0. If you want an undirected pipe that can carry flow either way up to k, you model it as two directed edges each of capacity k, or with a special residual rule. And capacity is a constraint, not a flow — a high-capacity edge need not be used at all.

If c(u, v) = 5 and a flow sets f(u, v) = 5, that edge is saturated and is a candidate bottleneck. If instead f(u, v) = 3, there are 2 units of spare room on it — exactly the spare room that the residual graph records as a forward residual edge of capacity 2.

Spare capacity (c minus f) is what an algorithm hunts for; a saturated edge has none in the forward direction.

Integer capacities guarantee an integer maximum flow, but irrational capacities can make naive Ford-Fulkerson loop forever — so capacity values are not a harmless detail; they affect whether an algorithm even terminates.

Also called
capacityc(u,v)容量