How much can you push through a network?
Network flow and min-cut (topic 06), its special case the transportation problem (18), which keeps only two flat layers of nodes, matching and assignment (07), and shortest paths with dynamic programming (08): the structure real shipping, scheduling and routing problems have.
Flow problems are the friendliest corner of the whole field, and it is worth knowing why: they are integer problems that behave like continuous ones. Give a network whole-number capacities and the linear program will hand you a whole-number flow all by itself, with no branching required. That is a structural gift, not a coincidence: see the mathematics below.
The max-flow/min-cut theorem is the kind of result that feels like a magic trick until you see it from the right angle, at which point it becomes obvious. Any cut is a wall between source and sink; all flow must cross it; so no flow can exceed any cut's capacity. That much is easy. The hard and beautiful half is that the best flow always exactly achieves the cheapest wall. There is never a gap.
The practical payoff is that a min-cut tells you where to invest. Widening any pipe not on the cut does nothing at all. It is the same lesson as shadow prices in topic 03, arriving from a completely different direction.
Maximise the flow value while conserving flow at every intermediate node and respecting capacities:
maximise Σ f(s,v)
s.t. f(u,v) ≤ c(u,v) for every edge
Σ f(u,v) = Σ f(v,w) for every v ≠ s,t
f ≥ 0
Max-flow min-cut theorem (Ford & Fulkerson, 1956): the maximum flow value equals the minimum capacity over all source–sink cuts. It is precisely LP duality specialised to this structure (the cut is the dual solution) which is why topics 03 and 06 keep rhyming.
The integrality gift comes from total unimodularity: a network's incidence matrix is totally unimodular, so with integer capacities every vertex of the feasible polytope is integral, and since simplex returns a vertex, it hands back a whole-number flow with no branching at all. (An interior-point method can land between vertices on a tie, which is why solvers apply a crossover step to finish at one.) This is why max-flow is polynomial while its cousin the integer multicommodity flow is NP-hard: remove the structure and the gift goes with it.
Algorithms: Ford–Fulkerson (augmenting paths), Edmonds–Karp (O(VE²) by choosing shortest augmenting paths), Dinic's algorithm, and push-relabel. All are polynomial and all are fast in practice.
Everything above assumes the network already exists and asks how much flows through it. Network design asks the harder question one level up, which edges should even get built, and the nice structure vanishes the moment you ask it. The cleanest version, the Steiner tree problem (connect a given set of terminal nodes at minimum total edge cost, allowed to use other nodes as waypoints), is NP-hard, unlike the max-flow problem it superficially resembles. The practical version, fixed-charge network design, pays a fixed cost to open each edge before any flow can use it at all, which destroys the total-unimodularity that made ordinary flow easy, and is exactly why building a telecom backbone or expanding a road network is a genuinely harder planning problem than routing traffic through one that already exists.
Where the grid will actually break Transmission planners model the network as a flow problem to find which combination of line failures would island a region: the min-cut is the answer, and it is rarely the line anyone was worried about. The same computation appears as image segmentation in computer vision (cutting a picture into foreground and background is literally a min-cut), as baseball elimination (is this team mathematically out?), and as project selection where the cut separates projects you fund from projects you don't.
Check yourself
What does the max-flow min-cut theorem say?
Any cut caps the flow, and the best flow always exactly achieves the cheapest cut: there is never a gap. So widening a pipe that is not on the min-cut does nothing.