Maximum flow

Flow networks, feasible flows, residual graph and augmenting paths, the Ford-Fulkerson algorithm, cuts and the max-flow min-cut theorem.

The outline, topic by topic

Each topic is weighted the way the exam weighs it.

Flow network: what is it?
Show the answer
A directed graph whose arcs each carry a capacity, with a source where the flow starts and a sink where it ends.
It models pipes, roads, cables: an arc's capacity is the largest rate it can carry.
In this network (arcs S→A capacity 10, S→B 8, A→B 2, A→T 7, B→T 9), what is the capacity of the cut {S, A} against {B, T}?
- 17
- 18
- 16
- 36
Show the answer
17
The arcs going from {S, A} to {B, T} are S→B (8), A→B (2) and A→T (7): 17. S→A stays inside the first set. 18 would count only the arcs leaving S, 16 those entering T, 36 all the arcs.
The conservation law requires that at every vertex other than the source and the sink, the sum of … flows equals the sum of … flows.
Show the answer
The conservation law requires that at every vertex other than the source and the sink, the sum of incoming flows equals the sum of outgoing flows.
An intermediate vertex stores nothing and creates nothing: what arrives leaves again. Only the source (which emits) and the sink (which absorbs) are exceptions.
Feasible flow: what is it?
Show the answer
A value given to each arc that never exceeds its capacity and that, at every vertex other than the source and the sink, lets out as much as comes in.
Two constraints to check: capacity on every arc, conservation at every intermediate vertex. The value of the flow is what leaves the source.