Flow networks

Shortest paths ask how to get one thing from A to B quickly. Network flow asks how much can get from A to B at once, when every line has a limit. The question looks narrow, but matching, scheduling, cutting a network in two and many other problems turn out to be flow problems in disguise.

Capacities, a source and a sink

A flow network is a directed graph with:

• a capacity c(u, v) ≥ 0 on each edge u → v: the most that can pass along it per unit of time. In this station the edges are railway lines and capacities are trains per hour;
• a source s, where everything starts, and a sink t, where everything ends.

The figure’s network has six stations. Its plates first show the capacities only; from the second step they read flow/capacity.

The two rules of a flow

A flow gives each edge a number f(u, v), how much actually passes, and keeps two rules:

Conservation says that stations in the middle neither keep trains nor make new ones. Step through the figure: the first variant checks both rules on a plan, and the second breaks each rule in turn. The second broken plan is the important one: every number is within its capacity, and the plan is still wrong.

The value of a flow

The value of a flow, written |f|, is the total flow out of s minus the total flow into s. The maximum flow problem asks for a flow of the largest value.

Proof: for each vertex v, take (flow out of v) − (flow into v), and add these numbers up over all vertices. Each edge u → v adds f(u, v) once (out of u) and takes it away once (into v), so the sum is 0. Conservation makes the term of every vertex except s and t equal to 0. So the term for s plus the term for t is 0: what leaves s is what reaches t. Lesson 4 uses the same sum over a set of vertices, which gives the flow across a cut.

Checking a proposed flow takes one pass over the edges, keeping a running total of “out minus in” for each vertex: O(V + E), where V is the number of vertices and E the number of edges. That is FLOW-P1, Is this a flow?

Fitting other problems to the shape

Real problems often have several sources or sinks, or limits on stations as well as on lines. Small changes to the graph fix that:

• Several sources or sinks. Add a new source with an edge of very large capacity to each real source, and a new sink with such an edge from each real sink. A flow from the new source to the new sink is a flow between the real ones.
• A limit on a station. If a station v can handle at most k trains an hour, split it into v_in and v_out, send every edge into v to v_in and every edge out of v from v_out, and add v_in → v_out with capacity k.
• Two-way lines. A line that can be used either way, up to c in total, becomes two edges, u → v and v → u, each of capacity c. A flow never needs to use both at once: sending a along one and b along the other is the same as sending a − b along one.
• Repeated edges. Two edges from u to v act like one edge with the sum of their capacities, but a program can simply keep both.

Lesson 2 asks how to find a maximum flow. The obvious idea, sending along any path that still has room, is almost right, and the one thing it is missing is the subject of the whole lesson.