Foundations — Network flow — max-flow min-cut theorem, Ford-Fulkerson, Edmonds-Karp

This page assumes nothing. Before you can read the parent note Network Flow (parent), every squiggle it uses is built here from a picture. Read top to bottom; each block earns the next.

0. The picture we keep in our heads

Everything below lives on one drawing: dots joined by arrows, water flowing left-to-right from a tap $s$ into a bucket $t$.

Look at that figure. A dot is a place. An arrow is a pipe that only lets water go the way it points. That is the entire vocabulary — now we name each part precisely.

1. Graph, vertices, edges — the skeleton

The letters $u$ and $v$ are just stand-ins for any two dots — like "person X and person Y". When you see $(u,v)$, read it aloud as "some arrow from a dot I'll call $u$ to a dot I'll call $v$."

2. Source $s$ and sink $t$ — where water is born and dies

Picture: in figure s01, $s$ is on the far left (only arrows leaving), $t$ on the far right (only arrows arriving).

3. Capacity $c(u,v)$ — how fat each pipe is

The notation $c(u,v)$ reads: "the capacity function $c$, asked about the specific pipe from $u$ to $v$." A function is just a lookup table: you hand it a pipe, it hands you a number.

4. Flow $f(u,v)$ — how much water is actually moving

In figure s02 the middle dot has $3$ units arriving and must send $3$ out (say $2+1$). That balance is conservation. The symbol $\sum$ (capital Greek "sigma") just means "add up all of these" — here, add every flow arriving, then every flow leaving, and demand the two totals match.

5. Value of a flow $|f|$ — the score we maximise

The bars $|\cdot |$ here do not mean absolute value — they are just traditional notation for "size / value of the flow". This single number $|f|$ is the thing the whole topic wants to make as big as possible.

6. Cut $(S,T)$ — a wall that separates tap from bucket

Figure s03 draws a dashed wall. The amber arrows crossing left-to-right count toward $c(S,T)$; the cyan arrow crossing right-to-left is free. The symbol $u\in S$ reads "$u$ is a member of team $S$" ($\in$ = "belongs to").

7. Residual graph & residual capacity $c_f$ — the "undo" map

Once some flow is running, we redraw the network to show what moves are still legal. This redraw is the residual graph, and it powers every algorithm in the parent note.

An augmenting path is any route from $s$ to $t$ using only arrows with $c_f>0$. Its bottleneck is the smallest $c_f$ along it — the most water that whole route can carry.

8. Big-O notation $O(\cdot )$ — how we grade speed

We use it to compare algorithms: Ford–Fulkerson's speed depends on the capacity values ($O(E\cdot |f^{\ast }|)$), while Edmonds–Karp's does not ($O(V{E}^2)$) — a big deal when capacities are huge.

How these feed the topic

Read the map top-down: dots and arrows come first, then labels (capacity, flow), then the two headline objects — max flow and min cut — which the theorem glues together. The augmenting-path branch relies on BFS and leads toward Edmonds-Karp-style methods and Dinic's Algorithm. The theorem itself is a special case of a broader duality: see Linear Programming Duality and Menger's Theorem, and it underpins Bipartite Matching.

Equipment checklist

Cover the right side and test yourself — each line is question ::: answer.