Network Flows - Part 2

In Part 1, we motivated network flows with a supply chain example and outlined what this series will cover. Now let's get precise. In this part, we introduce the formal definitions — flow networks, flows, and cuts — and establish the first fundamental relationship between them.

Flow Networks

A flow network is a directed graph where each arc has a capacity — a limit on how much "stuff" can pass through it. There are two special vertices: a source, where flow originates, and a sink, where flow is consumed.

Definition 1. A flow network is a tuple $N = (D, s, t, c)$, where:

• $D = (V, A)$ is a directed graph,
• $s \in V$ is the source,
• $t \in V$ is the sink, with $s \neq t$,
• $c: A \rightarrow \mathbb{R}_{\geq 0}$ is the capacity function, assigning a non-negative capacity $c(a)$ to each arc $a \in A$.

Think of the arcs as pipes and the capacities as their diameters — a wider pipe can carry more water. The source is the reservoir where water enters the system, and the sink is where it drains out. Everything in between is just routing the water through.

Let's look at a small example. Consider the flow network with vertices $\{s, a, b, t\}$ and arcs $\{(s,a), (s,b), (a,b), (a,t), (b,t)\}$ with capacities $c(s,a) = 4$, $c(s,b) = 2$, $c(a,b) = 3$, $c(a,t) = 1$, and $c(b,t) = 5$. The source $s$ can push up to $4$ units through $a$ and $2$ through $b$, and the flow must eventually reach $t$.

We will use this example throughout this part to illustrate the definitions.

Flows

Now that we have the network, we can define what it means for something to "flow" through it. A flow assigns a value to each arc — how much is actually being transported — subject to two natural constraints: you can't exceed the capacity of an arc, and nothing gets created or destroyed at intermediate vertices.

Definition 2. A flow in a flow network $N = (D, s, t, c)$ is a function $f: A \rightarrow \mathbb{R}_{\geq 0}$ satisfying:

(i) Capacity constraint: $0 \leq f(a) \leq c(a)$ for every arc $a \in A$.

(ii) Flow conservation: For every vertex $v \in V \setminus \{s, t\}$, the total flow entering $v$ equals the total flow leaving $v$: $\sum_{(u,v) \in A} f(u,v) = \sum_{(v,w) \in A} f(v,w).$

The capacity constraint says we can't send more through a pipe than it can handle. Flow conservation says that at every intermediate vertex, what goes in must come out — nothing is lost, nothing is stored. Only the source and the sink are exempt: the source produces flow, and the sink absorbs it.

In our example, one valid flow is $f(s,a) = 3$, $f(s,b) = 2$, $f(a,b) = 2$, $f(a,t) = 1$, $f(b,t) = 4$. Let's verify: at vertex $a$, the incoming flow is $f(s,a) = 3$ and the outgoing flow is $f(a,b) + f(a,t) = 2 + 1 = 3$ — conservation holds. At vertex $b$, the incoming flow is $f(s,b) + f(a,b) = 2 + 2 = 4$ and the outgoing flow is $f(b,t) = 4$ — conservation holds again.

The most important number associated with a flow is how much total flow reaches the sink.

Definition 3. The value of a flow $f$, denoted $|f|$, is the net flow leaving the source: $|f| = \sum_{(s,w) \in A} f(s,w) - \sum_{(u,s) \in A} f(u,s).$

In most networks, no arcs point into the source, so the value is simply the total flow on all arcs leaving $s$. In our example, $|f| = f(s,a) + f(s,b) = 3 + 2 = 5$.

By flow conservation, the value of a flow also equals the net flow arriving at the sink — what enters the system must eventually leave it.

Observation 1. For any flow $f$, the net flow leaving the source equals the net flow entering the sink: $\sum_{(s,w) \in A} f(s,w) - \sum_{(u,s) \in A} f(u,s) = \sum_{(u,t) \in A} f(u,t) - \sum_{(t,w) \in A} f(t,w).$

Proof. Sum the flow conservation equation over all vertices $v \in V \setminus \{s,t\}$. On the left, we have the total flow on all arcs, counting each arc's flow once as incoming at its head. On the right, we have the total flow on all arcs, counting each arc's flow once as outgoing at its tail. Every arc with both endpoints in $V \setminus \{s,t\}$ appears on both sides and cancels. What remains on the left are arcs arriving from $s$ or from $t$, and on the right are arcs leaving toward $s$ or toward $t$. Rearranging gives the desired equality.

The Maximum Flow Problem

Given a flow network, we naturally want to push as much flow as possible from source to sink. This is the central question of the series.

Maximum Flow Problem. Given a flow network $N = (D, s, t, c)$, find a flow $f$ of maximum value $|f|$.

In our example, can we do better than $|f| = 5$? The source can push at most $c(s,a) + c(s,b) = 4 + 2 = 6$ units total. But can all $6$ units reach $t$? It turns out the answer is $5$ — we'll see why after we introduce cuts.

Cuts

If a flow represents how much we can push through a network, a cut represents a bottleneck — a place where the network can be severed to separate the source from the sink. The capacity of the narrowest such bottleneck gives an upper bound on how much flow we can send.

Definition 4. An $s$-$t$-cut in a flow network $N = (D, s, t, c)$ is a partition of the vertex set $V$ into two sets $S$ and $T = V \setminus S$ such that $s \in S$ and $t \in T$.

Definition 5. The capacity of an $s$-$t$-cut $(S, T)$ is the total capacity of all arcs going from $S$ to $T$: $c(S, T) = \sum_{\substack{(u,v) \in A \\ u \in S, \, v \in T}} c(u,v).$

Notice that we only count arcs going from $S$ to $T$, not the other way around. Arcs from $T$ to $S$ don't contribute to the cut capacity — they carry flow in the "wrong" direction.

In our example, consider the cut $S = \{s, a\}$, $T = \{b, t\}$. The arcs from $S$ to $T$ are $(s,b)$ with capacity $2$, $(a,b)$ with capacity $3$, and $(a,t)$ with capacity $1$. So $c(S,T) = 2 + 3 + 1 = 6$. Another cut is $S = \{s\}$, $T = \{a, b, t\}$, which gives $c(S,T) = c(s,a) + c(s,b) = 4 + 2 = 6$. And the cut $S = \{s, a, b\}$, $T = \{t\}$ gives $c(S,T) = c(a,t) + c(b,t) = 1 + 5 = 6$.

Interestingly, all three cuts in this example have capacity $6$. That won't always be the case — different cuts can have very different capacities.

Weak Duality

Now we arrive at the key relationship between flows and cuts. It turns out that the value of any flow is bounded above by the capacity of any cut. This is a powerful result: every cut provides a certificate that no flow can exceed a certain value.

Lemma 1 (Weak Duality). For any flow $f$ and any $s$-$t$-cut $(S, T)$ in a flow network, we have $|f| \leq c(S, T).$

Proof. We first show that the value of any flow can be expressed using any cut. By summing the flow conservation equation over all vertices in $S \setminus \{s\}$ and adding the definition of $|f|$, we get: $|f| = \sum_{\substack{(u,v) \in A \\ u \in S, \, v \in T}} f(u,v) - \sum_{\substack{(u,v) \in A \\ u \in T, \, v \in S}} f(u,v).$

This says the value of the flow equals the net flow crossing the cut from $S$ to $T$¹. Now, the second sum is non-negative, so: $|f| \leq \sum_{\substack{(u,v) \in A \\ u \in S, \, v \in T}} f(u,v) \leq \sum_{\substack{(u,v) \in A \\ u \in S, \, v \in T}} c(u,v) = c(S, T),$

where the last inequality uses the capacity constraint $f(u,v) \leq c(u,v)$.

Let's verify this in our example. We found a flow of value $5$ and three cuts, each with capacity $6$. The lemma confirms $5 \leq 6$. But is the maximum flow actually $5$, or can we do better? And what is the minimum cut capacity? Trying cuts by hand is tedious and error-prone — we need a systematic approach. We'll develop exactly that in the next part, where we introduce residual graphs and prove the Max-Flow Min-Cut Theorem: the statement that the maximum flow value always equals the minimum cut capacity.

Looking Ahead

We've set up the formal framework: flow networks, flows, cuts, and the weak duality between them. The natural question is: can weak duality be strengthened to an equality? In the next part, we'll answer this with the Max-Flow Min-Cut Theorem — one of the most important results in combinatorial optimization. To prove it, we'll introduce residual graphs and augmenting paths, which will also lead us directly to the first algorithms for computing maximum flows.