Concept

Capacity

The most a road, pipe or edge of a network can carry per unit of time. Capacities bound every flow, and the cheapest set of roads separating two places, added up by capacity, is exactly the most that can travel between them.

Named by 2 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

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.

Certificate Flow Bipartite matching Conservation Convexity Cut Cycle Duality Edge disjoint paths Linear program Min-max theorem Shadow price

All concepts