Single-Commodity Network Flow

Introduces flow networks for routing a single commodity (such as passengers) through a capacitated directed graph. Covers the definition of a flow, the capacity and conservation constraints, the value of a flow, and how to increase it by augmenting along an s-t path.

Step 1 of 157%

Tutorial

Flow Networks and Valid Flows

A flow network is a directed graph $G=(V,E)$ together with a nonnegative capacity $c(u,v) \geq 0$ on each edge, and two distinguished vertices: a source $s$ and a sink $t$ . We interpret $c(u,v)$ as the maximum amount that can travel along edge $(u,v)$ . In a routing context, $c(u,v)$ is the number of seats available on the flight from airport $u$ to airport $v$ .

A flow is a function $f$ assigning a value $f(u,v)$ to every edge so that two rules hold:

Capacity constraint: $0 \leq f(u,v) \leq c(u,v)$ for every edge $(u,v) \in E$ .
Conservation: for every vertex $v \neq s, t$ ,

\sum\limits_{u : (u,v)\in E} f(u,v) \;=\; \sum\limits_{w : (v,w)\in E} f(v,w).

Conservation says that no internal airport accumulates passengers — everyone who arrives must depart.

For a small illustration, take the two-edge network $s \to a \to t$ with $c(s,a) = 5$ and $c(a,t) = 5$ . Setting $f(s,a) = f(a,t) = 3$ gives a valid flow: $3 \leq 5$ on each edge, and vertex $a$ has $3$ units in and $3$ units out.