Generator

A largest flow of 5 through four places and five roads

A generator in the discrete library, called 26 times across 5 essays. Below: what it draws with nothing chosen and at each mode an essay asks for, what it checks while drawing, and everywhere it is used.

flow is one function. Everything below came out of it during this build, at parameters taken from the essays rather than invented for this page — so a figure here is the same figure a reader meets in an essay, and if the generator changes, this page changes with it.

With nothing chosen

A largest flow of 5 through four places and five roads. 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.

A network of six places and the tree that holds all fifteen of its cheapest cuts

The cheapest cut between every pair of six places, and what the tree says

The cheapest cuts among every three of six places

Building the tree from five cheapest cuts

How many different cheapest-cut values 200 six-place networks have

What it checks while it draws

Collected by running the family and recording what it asserted, not written here. The count is how many separate times the claim was put to the test while these drawings were made.

the tree gives the cheapest cut between places 0 and 1 ×15
with 3 spokes the pairs share k/2 ×5
the road a to d is carrying its full 1 ×2
a dearer flow leaves a cycle of negative cost ×1
a flow is cheapest exactly when it leaves no cycle of negative cost ×1
a road cheaper than the price difference is full ×1
a road dearer than the price difference carries nothing ×1
a road used but not full has reduced price nought ×1
A's isolating cut is no dearer than the boundary of its side ×1
among A, B and C the two smallest cheapest cuts are equal ×1
among A, B and D the two smallest cheapest cuts are equal ×1
among A, B and E the two smallest cheapest cuts are equal ×1
among A, B and F the two smallest cheapest cuts are equal ×1
among A, C and D the two smallest cheapest cuts are equal ×1
among A, C and E the two smallest cheapest cuts are equal ×1
among A, C and F the two smallest cheapest cuts are equal ×1
among A, D and E the two smallest cheapest cuts are equal ×1
among A, D and F the two smallest cheapest cuts are equal ×1
among A, E and F the two smallest cheapest cuts are equal ×1
among B, C and D the two smallest cheapest cuts are equal ×1
among B, C and E the two smallest cheapest cuts are equal ×1
among B, C and F the two smallest cheapest cuts are equal ×1
among B, D and E the two smallest cheapest cuts are equal ×1
among B, D and F the two smallest cheapest cuts are equal ×1
among B, E and F the two smallest cheapest cuts are equal ×1
among C, D and E the two smallest cheapest cuts are equal ×1
among C, D and F the two smallest cheapest cuts are equal ×1
among C, E and F the two smallest cheapest cuts are equal ×1
among D, E and F the two smallest cheapest cuts are equal ×1
and in whole units a matching of leaves gets through ×1
and in whole units only one pair can be served ×1
and is within 2 − 2/k of it ×1
and it is also what reaches the sink ×1
and removing that many roads disconnects the two ends ×1
and separating every pair takes all but one spoke ×1
B's isolating cut is no dearer than the boundary of its side ×1
between 50 and 400 networks ×1
C's isolating cut is no dearer than the boundary of its side ×1
each extra unit costs at least as much as the one before ×1
each road is priced at one half ×1
each route continues until it reaches the sink ×1
every network falls in one bar ×1
every place is placed in the tree drawing ×1
every road of this network has capacity one ×1
every road's price is non-negative ×1
every route carries a whole or half unit, as Hu's theorem allows ×1
every route costs at least 1 at the prices ×1
every two-pair network in the family meets its cut, as Hu's theorem says it must ×1
every usable road pays its way at these prices ×1
every way of splitting the middle places is a cut and is listed ×1
everything arriving at a leaves again ×1
everything arriving at b leaves again ×1
everything arriving at c leaves again ×1
everything arriving at d leaves again ×1
everything arriving at e leaves again ×1
everything arriving at f leaves again ×1
family sizes between 20 and 200 ×1
fifteen cheapest cuts take at most five values ×1
for two pairs the largest shared flow equals the cheapest separating cut ×1
no cut is smaller than the flow, over every cut there is ×1
no network breaks the 4/3 guarantee ×1
no road carries more than its capacity ×1
no two places overlap in the tree drawing ×1
no two routes share a road ×1
nothing is drawn over the headings ×1
pushing round the cycle lowers the cost by its price times the amount ×1
some flow delivers 4 ×1
stars with 3 to at most 8 spokes ×1
the amount sent is a whole number between 1 and 5 ×1
the cheapest flow leaves no cycle of negative cost to push round ×1
the cheapest set of roads separating every pair has 2 roads ×1
the cut is either drawn or it is not ×1
the drawn flow is a flow ×1
the drawn roads add up to the cut's value ×1
the fifteen cheapest cuts take at most five values ×1
the linear program is bounded ×1
the network is one this family draws ×1
the number of networks is a whole number between 200 and 5000 ×1
the prices add up to exactly the flow's value, so both are optimal ×1
the road a to c is carrying its full 2 ×1
the road a to t is carrying its full 1 ×1
the road b to d is carrying its full 2 ×1
the road b to t is carrying its full 4 ×1
the road s to b is carrying its full 3 ×1
the road s to c is carrying its full 3 ×1
the shortcut never beats the cheapest cut ×1
the smallest cut and the largest flow are the same number ×1
the smallest of them equals the largest flow ×1
the three pairs can share 3/2 units at once, and no more ×1
the three sides' boundaries count every cut road twice ×1
the two cheapest isolating cuts together separate all three places ×1
the two pairs compete: together they send less than apart ×1
the value is what leaves the source ×1
the view is one the family draws ×1
there are as many routes as the flow's value ×1
whole units fall short of the shared flow here ×1
whole-number flow ≤ fractional flow ≤ cheapest separating cut ×1

Where it is called

Every figure on this list is drawn by the same rule, so a change to the rule changes all of them at once. That is why the list is published.

Discrete

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

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

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

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

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.

The whole library · What the figures prove