Network Flows, Cuts & Matching

a flow network

Picture a system of one-way water pipes joining a source pump to a drain. Each pipe can carry only so much water per second, junctions cannot store water, and you want to push as much as you can from the pump to the drain. A flow network is the mathematical version of exactly this picture, and it turns out to model far more than water: traffic on roads, packets on the internet, goods through a supply chain, even matching workers to jobs.

Formally, a flow network is a directed graph G = (V, E) with two special vertices, a source s and a sink t. Every edge (u, v) carries a nonnegative capacity c(u, v) >= 0, the most that edge may carry. A flow assigns each edge a number f(u, v) with 0 <= f(u, v) <= c(u, v) (you cannot exceed a pipe's capacity), and at every vertex other than s and t the total flow in must equal the total flow out (junctions neither create nor destroy flow). The goal is usually to maximize the value of the flow, the net amount leaving s, which by conservation equals the net amount arriving at t.

Flow networks matter because a single clean model captures a huge family of problems, and that model comes with a beautiful theory: the max-flow min-cut theorem ties the best possible flow to the cheapest way to sever s from t, and efficient algorithms (Edmonds-Karp, Dinic) solve it in polynomial time. The art in practice is modeling: turning a scheduling, selection, or matching question into a network so that its maximum flow answers the original question. One convention worth knowing: capacities are normally given only on the edges that exist; a missing edge is treated as capacity 0.

A tiny network: s -> a (capacity 3), s -> b (2), a -> t (2), b -> t (3), a -> b (1). One valid flow sends 2 along s->a->t and 2 along s->b->t, for value 4. Could we do better by also using the a->b pipe? Checking capacities and conservation is how we test any candidate flow.

Every edge respects its capacity and every interior vertex balances in equals out — that is what makes an assignment a legal flow.

A flow network is the model, a flow is one filling of it, and the max-flow value is the answer you usually want. Keep the three apart: changing the capacities changes the network; changing f changes only the flow inside a fixed network.

Also called
flow graphcapacitated network網路流容量網路