Matpic
mathematics, in pictures
Concept

Cut — where it appears

A division of a network's places into two sides, priced by the total capacity of the roads that cross between them. Everything travelling from one side to the other is bounded by a cut's price, so the cheapest cut is the tightest bound there is.

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

Also named here as flow, min-max theorem — the same set of essays touches all of them, so they are one junction rather than several.

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

Named alongside it

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

CertificateFlowMin-max theoremCounterexampleBipartite matchingCapacityConservationDualityEdge disjoint pathsExhaustive searchGraphIntegrality

All concepts