Matpic
mathematics, in pictures
Concept

Flow — where it appears

An assignment of amounts to the roads of a network that stays within every road's capacity and passes on at each junction exactly what arrives there. Its value is what leaves the source, and the largest value possible is certified by a cut of the same capacity.

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 Three places cut apart for 13. A network of eight places with road capacities, three of them lettered, coloured by which of the three sides of the cheapest three-way cut each place falls on, with the cut roads dashed.

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.

discrete · Network flow The cheapest way to send 4 units, for 25. A directed network from s to t with a capacity and a price on each road, showing the whole-number flow of 4 units with the least total cost, the arrows thickened by the amount they carry.

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.

discrete · Network flow

Named alongside it

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

CertificateCutCounterexampleDualityLinear programMin-max theoremCapacityExhaustive searchGraphApproximationBipartite matchingConservation

All concepts