Max Flow and Ford-Fulkerson
What This Concept Is
A flow assigns each directed input edge a quantity between zero and its nonnegative capacity. Every nonterminal conserves incoming and outgoing flow. The value is net outflow at source, equal to net inflow at sink; source and sink must differ. Parallel and antiparallel original edges remain distinct records.
For each edge carrying f of capacity c, residual choices include c-f forward and f backward. A backward residual move cancels previous flow; it is not necessarily an original edge. Ford–Fulkerson repeatedly augments along a residual s-to-t path by that path's minimum residual capacity.
Why It Matters Here
Residual cancellation makes earlier choices reversible. An implementation that searches only unused original forward capacity is a greedy routing procedure and can stop below maximum flow. Outputting per-edge flows lets a separate checker validate capacity and conservation instead of trusting a scalar value.
Concrete Examples
Take source s, left vertices a,b, right vertices x,y, sink t, and unit edges s→a,s→b,a→x,a→y,b→x,x→t,y→t. First augment s→a→x→t. To reach value 2, use residual path s→b→x→a→y→t; x→a cancels the first assignment. Final assignments are b→x and a→y. Without the reverse residual edge, the initial choice can leave value 1 despite a feasible value-2 flow.
Store a paired forward/reverse residual record for every original edge ID. An original x→a edge, if present, has its own pair and must not be confused with the cancellation record of a→x.
Common Confusion / Misconceptions
Ford–Fulkerson names a method, not a specific path-selection complexity bound. With integer capacities and zero initial flow, positive augmentation increases value by at least one, giving a value-dependent termination argument. That bound can be pseudo-polynomial in binary-encoded capacities. Arbitrary irrational capacities and bad path choices can defeat termination of the generic method.
How To Use It
Define source/sink, numeric domain, edge identity, flow vector and error policy. The lab uses exact integer capacities and BFS augmenting paths. Self-loops may carry zero flow without reducing optimum value. Incoming source and outgoing sink edges require net, not just gross, terminal accounting.
Check Yourself
- What does a backward residual edge mean?
- Why are original antiparallel edges separate from cancellation records?
- Why is O(E times flow value) not a bit-polynomial guarantee?
- Why does source value use net outflow?
Mini Drill or Application
Trace both augmentations on the reassignment network. Write the flow on every original edge after each step and verify conservation. Temporarily omit reverse updates in Lab D; preserve the failure and repair it. See P17.
Read This Only If Stuck
Find flow feasibility, residual graphs, and augmenting paths in Skiena, CLRS, or Sedgewick and Wayne. These are book indexes, not exact section links. The reading guide names bounded assignments and local source files. Attempt the worked examples before adding more reading.