Flow — where it appears
Named by 7 essays across one field — each of them below, with the objects they name alongside it.
The bottleneck is the whole story
However much a network can carry from one place to another, there is a way of cutting it in two whose total capacity is exactly that number. One quantity is a maximum over ways of routing and the other a minimum over ways of severing, and they are never off by even one.
When several pairs share the roads
For one pair of places, the most that can travel between them equals the cheapest cut that separates them. Give three pairs a hub of three roads to share and the two numbers come apart: the pairs can send 3/2 between them, while separating every pair costs 2. Two pairs still meet their cut, but only by splitting units in half.
One tree for every cut
A network of six places has fifteen pairs, and each pair has its own cheapest cut. All fifteen can be read off a tree with five numbers on it: the cheapest cut between any two places is the smallest number on the tree's path between them. Gomory and Hu proved in 1961 that such a tree always exists, and building it takes five cuts, not fifteen.
Three places cut apart
Separating two places as cheaply as possible is solved exactly by a flow. Separating three from one another is a different problem: no flow measures it, the pairwise answers do not add up to it, and the best shortcut known in 1994 — cut each place off on its own and throw the dearest cut away — is guaranteed only to within a third of the truth.
The cheapest way to send
Put a price on every road as well as a capacity and ask for the cheapest way to send four units. Twenty-eight ways exist and one is cheapest, and two certificates prove it without comparing it with the other twenty-seven: no cycle of roads it leaves unused costs less than nothing to push round, and there are prices at the places that every usable road fails to beat.
A search for room that never ends
The textbook way to find the most that a network can carry is to find any route that still has room, push as much along it as it will take, and repeat until no route has room left. With whole-number capacities that must stop. Give one road a capacity of 0.618…, the golden ratio's reciprocal, and choose the routes badly, and it never stops: every push is positive, the flow converges, and it converges to 4.236 when the network can carry 5. The same choice made carelessly in floating point does stop — because of rounding, at the wrong answer, convinced it has finished.
Out before the table says so
Detroit has 49 wins and 27 games left, so it can reach 76, and the leader has 75. On paper it is alive. It is not: the four teams ahead must play 27 games among themselves, and whoever wins them, those four finish with an average above 76. Finding that takes one maximum flow, and it is checked against every possible result of every game.
Named alongside it
The objects these essays reach for when they reach for this one.
CutCertificateMin-max theoremCapacityCounterexampleDualityExhaustive searchLinear programGraphAlgorithmApproximationBipartite matching