Matpic
mathematics, in pictures
Concept

Min-max theorem

A theorem saying that the largest value of one quantity equals the smallest value of another that bounds it from above. Max-flow min-cut, linear-programming duality and the minimax theorem are the standard cases, and each turns a claim of optimality into a checkable certificate.

Named by 5 essays across one field — each of them below, with the objects they name alongside it.

A largest flow of 5 through two wide ends and a narrow middle. A network with a capacity on every road, the amount a largest flow sends along each, and the cut whose capacity equals that flow's value drawn as a line separating the places.

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.

discrete · Network flow Three pairs of places sharing one hub. A hub with three spokes of capacity one, the three pairs of outer places each routing half a unit through it, beside the total that can be sent fractionally, in whole units, and the cost of the cheapest set of roads separating every pair.

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.

discrete · Network flow A network of six places and the tree that holds all fifteen of its cheapest cuts. A network with capacities on its roads beside a tree on the same places, whose edge numbers give the cheapest cut between any two places as the smallest number on the path joining them.

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.

discrete · Network flow A flow that climbs for ever and falls short. 0:p0 +1.000000 → 1.000000; 1:p1 +0.618034 → 1.618034; 2:p2 +0.618034 → 2.236068; 3:p1 +0.381966 → 2.618034; 4:p3 +0.381966 → 3.000000; 5:p1 +0.236068 → 3.236068; 6:p2 +0.236068 → 3.472136; 7:p1 +0.145898 → 3.618034; 8:p3 +0.145898 → 3.763932; maximum 5.

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.

discrete · Network flow A season's games as a flow. Whether Detroit can still finish first: the games among the others are the left column, 27 wins to place, and each rival can absorb at most 76 minus its wins; the maximum flow is 26, so 1 wins have nowhere to go, and Detroit is out.

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.

discrete · Network flow

Named alongside it

The objects these essays reach for when they reach for this one.

CutFlowCertificateCapacityCounterexampleExhaustive searchAlgorithmBipartite matchingConservationDualityEdge-disjoint pathsFloating-point

All concepts