3.5.16 · D5Graphs
Question bank — Network flow — max-flow min-cut theorem, Ford-Fulkerson, Edmonds-Karp
Recall Ten words of context first
A flow network is pipes from source to sink ; max flow = most water per second; min cut = cheapest set of pipes to sever. Every trap below pokes at one of these ideas. See Graphs for the underlying directed-graph vocabulary.
True or false — justify
True or false: Every flow network has a unique maximum flow.
False. The value is unique (it equals the min cut), but many different flow assignments can achieve that same value — think of two parallel equal-capacity routes you can load in different proportions.
True or false: Every flow network has a unique minimum cut.
False. There can be several distinct cuts all sharing the minimum capacity; the theorem only guarantees at least one min cut equals the max flow value, not uniqueness.
True or false: If you increase one edge's capacity, the max flow strictly increases.
False. It increases only if that edge lies on some min cut (is a bottleneck). Widening a pipe that is not the bottleneck changes nothing.
True or false: A maximum flow must saturate every edge leaving the source .
False. It saturates every forward edge of the min cut it induces, but the source's own out-edges need not all be full unless itself happens to be a min cut.
True or false: The value measures flow leaving minus flow entering .
True. ; the subtraction matters whenever edges point back into the source, so "net" is the operative word, not "total out".
True or false: Backward residual edges are part of the original network .
False. They are bookkeeping in the residual graph only. They represent "undo capacity" — the right to cancel flow you already committed — and never appear as real pipes.
True or false: With integer capacities, Ford–Fulkerson always terminates.
True. Each augmentation raises by at least 1 and is bounded by the min cut, so only finitely many steps occur — this is the integrality guarantee.
True or false: With irrational capacities, Ford–Fulkerson always terminates.
False. A pathological path-choice sequence can push ever-smaller bottlenecks that converge below the true max flow — it never reaches it. Edmonds–Karp's BFS rule dodges this entirely.
True or false: Flow value can be negative.
True in principle if net flow enters , but for a maximum flow it is (you can always send zero). We normally orient the problem so .
Spot the error
Error hunt: "The cut capacity counts every edge crossing between and , in both directions."
Wrong — only forward edges count. Backward edges are free (they carry in the Step-1 balance), so including them would over-count the bottleneck.
Error hunt: "Edmonds–Karp runs in ."
That is plain Ford–Fulkerson, whose bound depends on the flow value. Edmonds–Karp uses BFS-shortest augmenting paths, giving the capacity-independent .
Error hunt: "When we push units along a path, we add to every edge on that path."
Only forward edges get ; backward (residual) edges get , because using a backward edge cancels previously routed flow rather than adding new flow.
Error hunt: "A greedy DFS that never revisits edges reaches max flow, since each push only increases ."
Increasing every step does not imply reaching the maximum. Without backward edges you can strand capacity (Worked Example 2), getting stuck below optimum — you need residual re-routing.
Error hunt: "If no augmenting path exists, maybe a longer or cleverer path still could."
No. "No augmenting path in " is equivalent to optimality by the theorem; the reachable set from forms a cut with , closing the door on any further increase.
Error hunt: "Conservation applies to every node including and ."
Wrong — and are exempt; they are precisely where net flow is created and absorbed. Forcing conservation on them would pin .
Error hunt: "The bottleneck of an augmenting path is the maximum residual capacity along it."
It is the minimum. You can only push as much as the tightest edge allows; any more would violate a capacity constraint on that edge.
Why questions
Why does summing conservation over all nodes in make internal edges vanish?
An edge with both endpoints in contributes (leaving one node) and (entering the other) to the sum, cancelling; only edges crossing the – boundary survive, which is why cut flow equals .
Why is weak duality () true for any flow and any cut, before we know the max?
Because forward crossing flow is capped by capacity () and backward crossing flow is subtracted and non-negative (); dropping the subtraction and raising each forward to only enlarges the bound.
Why does BFS (shortest augmenting path) prevent the non-termination that plagues Ford–Fulkerson?
BFS distances never decrease, and each edge can be saturated only times, bounding augmentations by regardless of capacity magnitudes — so no infinite convergent sequence can form. (BFS supplies the distance layering.)
Why must a backward edge appear with capacity exactly , not ?
You can only "take back" flow you actually sent along , which is units; you cannot un-route capacity that was never used.
Why is max-flow min-cut a special case of Linear Programming Duality?
Max flow is a linear program (maximise under capacity + conservation); its LP dual is exactly the min-cut problem, and strong duality forces their optima equal — the combinatorial theorem is that duality made concrete.
Why does Bipartite Matching reduce to a flow problem, and what caps guarantee an integer matching?
Add source→left (cap 1), right→sink (cap 1), left→right (cap 1); integer capacities make the max flow integral, and each unit of flow corresponds to one matched edge — max flow = maximum matching.
Why is Menger's Theorem just min-cut with unit capacities?
Give every edge capacity 1: max flow becomes the number of edge-disjoint – paths and min cut becomes the fewest edges whose removal disconnects from — Menger's edge version is max-flow min-cut restated.
Edge cases
Edge case: and are the same node.
Ill-defined — there is nothing to flow between, so max flow is conventionally (or the input is rejected); the source/sink partition of a cut can't be formed.
Edge case: There is no path at all from to .
Max flow is ; the min cut is with capacity , since every forward crossing edge is missing (capacity ).
Edge case: An edge has capacity .
It is effectively absent — it can never carry flow forward and contributes to any cut it crosses, so it may be deleted without changing max flow or min cut.
Edge case: A node has no outgoing edges but is not .
Conservation forces its in-flow to ; any flow entering it is impossible to balance, so no augmenting path can ever route usefully through it — it's a dead end.
Edge case: Antiparallel edges and both exist with real capacities.
Handle by splitting one into a dummy node () so residual bookkeeping doesn't confuse a real reverse pipe with a residual undo edge; otherwise the definitions collide.
Edge case: All capacities are equal, say every edge capacity .
The min cut is the fewest-edge – cut times ; the structure reduces to counting the sparsest edge cut, connecting straight back to Menger's Theorem.
Edge case: The graph is undirected.
Model each undirected edge as two directed edges and each of capacity ; flow may use either direction but the pair shares the bottleneck logic. Tools like Dinic's Algorithm handle this uniformly.
Edge case: Capacities are given as fractions (rationals).
Scale all capacities by their common denominator to make them integers; termination and integrality then apply, and dividing the answer back recovers the fractional max flow.