Generator

flow

A generator in the discrete library, called 6 times across 1 essays. Below: what it draws at its defaults 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.

At its defaults

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.

`show: "cuts"`

Every cut of four places and five roads, and the smallest. A table with one row per cut, giving the places on the source's side, the total capacity of the roads leaving that side, and which roads those are, sorted by capacity.

`show: "routes"`

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 road a to d is carrying its full 1 ×2
and it is also what reaches the sink ×1
and removing that many roads disconnects the two ends ×1
each route continues until it reaches the sink ×1
every road of this network has capacity one ×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
no cut is smaller than the flow, over every cut there is ×1
no road carries more than its capacity ×1
no two routes share a road ×1
the cut is either drawn or it is not ×1
the network is one this family draws ×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 smallest cut and the largest flow are the same number ×1
the smallest of them equals the largest flow ×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

Where it is called

Changing this generator changes every figure on this list. That is what makes the list worth publishing rather than keeping in a check script.

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.

The whole library · What the figures prove