Network Flow Fundamentals

A flow network is a directed graph $G = (V, E)$ in which every edge $(u, v) \in E$ has a nonnegative capacity $c(u, v) \geq 0$, representing the maximum rate at which material can travel along that edge. Two special vertices are distinguished: a source $s$, which produces material, and a sink $t$, which consumes it. By convention, if $(u,v) \notin E$ we set $c(u,v) = 0$, so capacities are defined for all ordered pairs. A flow is a function $f : V \times V \to \mathbb{R}$ satisfying three properties: 1. Capacity constraint: for every edge, $0 \leq f(u,v) \leq c(u,v)$. A flow can never exceed a pipe's rated capacity, and (in the standard single-commodity model) flow is nonnegative. 2. Skew symmetry: $f(u,v) = -f(v,u)$. This is a bookkeeping convention: sending 5 units from $u$ to $v$ is equivalent to sending $-5$ units from $v$ to $u$. It makes later formulas (like net flow into a vertex) clean. 3. Flow conservation: for every vertex $u \in V \setminus \{s, t\}$,

In words: at every vertex other than the source and sink, total flow in equals total flow out — material neither accumulates nor is created out of thin air at intermediate junctions. The value of a flow $f$, denoted $|f|$, is the net flow leaving the source:

A standard exercise (proved below) shows this equals the net flow arriving at the sink, so "how much leaves the source" and "how much arrives at the sink" are always the same number — flow doesn't leak or vanish anywhere in between. The central computational question this article sets up — and which Ford-Fulkerson Method answers algorithmically — is the maximum-flow problem: find a flow $f$ of maximum value $|f|$. To solve it, we need a way to detect when a flow can still be improved, and that requires a second graph built from the current flow: the residual graph $G_f$. For each edge $(u,v)$, the residual capacity is

the amount of additional flow that could still be pushed from $u$ to $v$. Crucially, the residual graph also contains a "back edge" $(v, u)$ with residual capacity $c_f(v,u) = f(u,v)$, representing the ability to cancel flow already sent along $(u,v)$. This is what lets an algorithm correct earlier suboptimal routing decisions without ever explicitly reasoning about the past — it is the single most important idea in this article, and the reason simple greedy strategies (which lack this undo mechanism) can get stuck at suboptimal flows. An augmenting path is a simple path from $s$ to $t$ in the residual graph $G_f$ using only edges of strictly positive residual capacity. If one exists, the flow is not yet maximum, because we can push additional units — equal to the minimum residual capacity along the path, called the bottleneck capacity — from $s$ to $t$ and strictly increase $|f|$.

Before any augmenting-path search can run, we must be able to (1) validate that a candidate assignment is a legitimate flow, (2) compute the value of a flow, and (3) construct the residual graph from a flow. These three primitives are the mechanical heart of every max-flow algorithm; understanding them precisely is what this article delivers.

Step 1 — Represent the network. Store $G$ as an adjacency list (see Graph Representations: Adjacency Lists and Matrices), annotating each edge with its capacity. It is convenient to also store, for every edge $(u,v)$ present in the input, an explicit reverse entry with capacity 0, so the residual graph never needs to allocate new edges — only update capacities.

Step 2 — Validate a flow. Check capacity constraints on every edge and conservation at every non-terminal vertex.

Step 3 — Compute residual capacities. For every pair with an edge in either direction, $c_f(u,v) = c(u,v) - f(u,v)$.

Step 4 — Find an augmenting path (if one exists). Run a graph search (BFS or DFS — the choice affects later complexity guarantees, discussed in the max-flow article) restricted to edges with $c_f > 0$.

Step 5 — Augment. Push the bottleneck capacity along the path, updating $f$ (and hence $c_f$) on every edge and its reverse. Here is pseudocode for the core primitives — building the residual graph and performing one augmentation step — which together form the inner loop that later algorithms iterate to convergence. ``` // Graph G given as capacities c[u][v] for all (u,v) with an edge, // and c[u][v] = 0 if no edge (u,v) exists. // Flow f[u][v] initialized to 0 for all pairs; f[u][v] = -f[v][u]. function RESIDUAL-CAPACITY(u, v): return c[u][v] - f[u][v] function BUILD-RESIDUAL-GRAPH(G, f): G_f = empty graph on same vertex set as G for each pair (u, v) such that c[u][v] > 0 or c[v][u] > 0: r = RESIDUAL-CAPACITY(u, v) if r > 0: add edge (u, v) to G_f with capacity r return G_f function FIND-AUGMENTING-PATH(G_f, s, t): // Any graph search restricted to positive-capacity edges works; // BFS here (as in Edmonds-Karp) finds a SHORTEST augmenting path. parent = array indexed by vertex, initialized to NIL visited = {s} queue = [s] while queue is not empty: u = queue.dequeue() for each edge (u, v) in G_f with capacity c_f(u, v) > 0: if v not in visited: visited.add(v) parent[v] = u if v == t: return RECONSTRUCT-PATH(parent, s, t) queue.enqueue(v) return NIL // no augmenting path exists function AUGMENT(f, path): // path is a list of vertices s = v0, v1, ..., vk = t bottleneck = +infinity for i = 0 to k - 1: bottleneck = min(bottleneck, RESIDUAL-CAPACITY(path[i], path[i+1])) for i = 0 to k - 1: u, v = path[i], path[i+1] f[u][v] = f[u][v] + bottleneck f[v][u] = -f[u][v] // maintain skew symmetry return bottleneck function COMPUTE-FLOW-VALUE(f, s): total = 0 for each vertex v: total = total + f[s][v] return total ``` Repeatedly calling `FIND-AUGMENTING-PATH` followed by `AUGMENT` until no augmenting path remains is precisely the augmenting-path method — the general strategy that Ford-Fulkerson Method instantiates and analyzes for correctness and running time. This article's job is to make sure every ingredient in that loop — flow, capacity, conservation, residual capacity, bottleneck — is airtight before that story continues.

Representing a flow and validating it takes $O(V + E)$ time: checking the capacity constraint is $O(1)$ per edge, and checking conservation requires summing incident edges once per vertex, which totals $O(E)$ across all vertices using an adjacency list. Space is $O(V + E)$ for the graph plus $O(E)$ for the flow values (one per edge, or $O(V^2)$ if an adjacency-matrix representation is used).

Building the residual graph is $O(E)$ — for every original edge we examine its current flow value and derive at most two residual entries (forward and backward), each in $O(1)$.

Finding one augmenting path via BFS or DFS is $O(V + E)$, standard for graph traversal.

Augmenting along a found path touches at most $V - 1$ edges (a simple path has fewer than $V$ vertices), so it is $O(V)$ per augmentation. Honesty about scope: this article only analyzes the primitives. The number of augmentations needed to reach a maximum flow, and whether that number is polynomial, is precisely the subject of Ford-Fulkerson Method — with badly chosen augmenting paths and irrational capacities, the method can in principle fail to terminate, while BFS-based selection (Edmonds–Karp) guarantees termination in $O(VE)$ augmentations. What we can prove here, rigorously, are the structural facts that make the whole theory work.

Claim 1 — flow out of $s$ equals flow into $t$. Sum the conservation equation $\sum_v f(u,v) = 0$ over all $u \in V \setminus \{s,t\}$. By skew symmetry, every term $f(u,v)$ for two internal vertices cancels with $f(v,u) = -f(u,v)$ in the corresponding sum for $v$, leaving only terms touching $s$ or $t$:

so $\sum_v f(s,v) = -\sum_v f(t,v)$, i.e. net flow out of $s$ equals net flow into $t$. This is why $|f|$ can be measured at either terminal — a useful sanity check when validating an implementation.

Claim 2 — capacity constraints bound $|f|$. For any partition of $V$ into a set $S$ containing $s$ and $T = V \setminus S$ containing $t$ (a cut), one can show (by a telescoping argument identical in spirit to Claim 1, restricted to vertices inside $S$) that

So the value of any flow is at most the capacity of any cut. This inequality — weak duality between flows and cuts — is the seed from which the Max-Flow Min-Cut Theorem grows, and it already tells us something concrete now: once we exhibit a flow and a cut whose capacities match, we know instantly, without further search, that the flow is maximum.

Claim 3 — the residual graph correctly represents "room to improve." If $c_f(u,v) > 0$, there is genuine freedom to change $f$: either $f(u,v) < c(u,v)$ (send more forward, still legal by the capacity constraint) or $f(v,u) > 0$ (cancel some flow currently going the other way, which is legal since flows may be any value down to 0). Conversely, pushing $\delta$ units of flow along a full augmenting path — where $\delta$ is the bottleneck — preserves both the capacity constraint (since $\delta \leq c_f$ on every edge of the path by definition of bottleneck) and conservation (since at every intermediate vertex, the extra $\delta$ arriving via one edge is exactly matched by $\delta$ leaving via the next). Hence `AUGMENT` always produces a new valid flow, and its value strictly increases by $\delta > 0$. This is the correctness core: an augmenting path is not just a heuristic signal but a certificate that improvement is possible, and the augmentation step is guaranteed to preserve feasibility while strictly growing $|f|$.

Tradeoff to flag honestly: none of this yet proves that when no augmenting path exists, the flow is maximum (that is exactly the min-cut theorem, proved via Claim 2's cut argument in the sequel). What is established here is the machinery — feasibility, residual capacity, bottleneck augmentation — on which that later proof entirely depends.

Consider the network from the diagram: $s \to a$ (cap 3), $s \to b$ (cap 2), $a \to b$ (cap 4), $a \to t$ (cap 2), $b \to t$ (cap 3). We trace two augmentations by hand.

Initial state: $f \equiv 0$ everywhere. Residual capacities equal original capacities; no back edges are usable (all zero).

Augmentation 1: BFS from $s$ finds path $s \to a \to t$ (via forward residual edges, both positive). Bottleneck $= \min(c_f(s,a), c_f(a,t)) = \min(3, 2) = 2$. Push 2 units.

Flow value so far: $|f| = 2$.

Augmentation 2: BFS from $s$: $s\to a$ has residual 1 (usable), $a \to t$ is now saturated (residual 0, unusable), but $a \to b$ has residual 4 and $b \to t$ has residual 3 — so the path $s \to a \to b \to t$ is found. Bottleneck $= \min(c_f(s,a), c_f(a,b), c_f(b,t)) = \min(1, 4, 3) = 1$. Push 1 unit.

Flow value so far: $|f| = 3$.

Augmentation 3: BFS from $s$: $s \to a$ is now saturated (residual 0). $s \to b$ has residual 2 — usable — then $b \to t$ has residual 2. Path $s \to b \to t$ found. Bottleneck $= \min(2, 2) = 2$. Push 2 units.

Flow value now: $|f| = 5$.

Termination check: From $s$, both $s\to a$ and $s \to b$ are now saturated (residual 0), and no back edges from $a$ or $b$ lead anywhere new that reaches $t$ (they only lead back to $s$, already visited). No augmenting path exists — BFS from $s$ can only reach $\{s\}$ itself via forward edges, since both outgoing edges of $s$ are saturated. The algorithm halts with $|f| = 5$.

Confirming optimality via Claim 2: take the cut $S = \{s\}$, $T = \{a, b, t\}$. Its capacity is $c(s,a) + c(s,b) = 3 + 2 = 5$, exactly matching $|f| = 5$. By weak duality ($|f| \leq$ capacity of any cut), no flow can exceed 5 — so this flow is provably maximum, without needing the full min-cut theorem machinery, just Claim 2 applied to one well-chosen cut.

The theory of network flows was born from very concrete Cold War logistics questions: how much traffic can move through a rail or highway network, and how would an adversary sabotage it most efficiently by removing the fewest links? These questions, posed to RAND Corporation researchers in the 1950s, led directly to the formalization of flow networks and cuts as dual objects — the same duality this article's Claim 2 previews.

Flow networks are not a theoretical curiosity confined to textbooks — they are load-bearing infrastructure in real systems. Internet traffic engineering models link capacities and routes packets to maximize throughput, directly using max-flow and min-cut reasoning to detect bottleneck links. Bipartite matching — assigning workers to tasks, students to schools, or organ donors to recipients — reduces exactly to a flow problem with unit capacities, letting hospitals and matching markets compute optimal, conflict-free assignments efficiently. Image segmentation in computer vision (the classic "GrabCut" style algorithms) casts foreground/background separation as a min-cut on a grid graph where edge weights encode pixel similarity. Airlines use flow models for crew scheduling and aircraft routing, where capacities represent seat or crew limits and conservation ensures every leg is properly staffed. Distribution and logistics companies solve multi-commodity flow variants — a generalization of the single-commodity model here — to route packages through warehouses under road and vehicle capacity limits. Even the theoretical computer science of project scheduling and bipartite covering problems, and reductions used in NP-hardness proofs (flow-based gadgets appear throughout complexity theory), lean on the exact definitions of flow, cut, and residual graph developed in this article. Every one of these applications ultimately runs an augmenting-path or push-relabel algorithm underneath — meaning the residual-graph mechanics taught here are the literal inner loop executing, millions of times a second, inside production routing and scheduling systems.

Ask the tutor: How does the choice of BFS versus DFS for finding augmenting paths affect the total number of iterations Ford-Fulkerson needs to converge?