Chapter 34 — Key Takeaways

Network Flow and Matching. The one-page reference: reread this before an exam.

Core definitions

Term Definition (compressed)
Flow network Directed graph $G=(V,E)$ + capacity $c\colon E\to\mathbb{R}_{\ge 0}$ + source $s$ + sink $t$ ($s\neq t$). Non-edges have $c=0$.
Flow $f$ $f\colon E\to\mathbb{R}_{\ge 0}$ with (1) capacity $0\le f(u,v)\le c(u,v)$ and (2) conservation in $=$ out at every $v\neq s,t$.
Value $\lvert f\rvert$ Net flow out of $s$. Equals net flow into $t$ (by conservation).
Saturated edge $f(u,v)=c(u,v)$ (used to its limit; a candidate bottleneck).
Residual capacity $c_f(u,v)=\underbrace{(c(u,v)-f(u,v))}_{\text{forward slack}}+\underbrace{f(v,u)}_{\text{cancellable back-flow}}$.
Residual network $G_f$ Edges = pairs with $c_f>0$: forward edges (spare capacity) + back edges $v\to u$ of capacity $f(u,v)$.
Augmenting path $s\to t$ path in $G_f$; bottleneck = min residual capacity on it.
s–t cut $(S,T)$ Partition $V$ with $s\in S,\ t\in T$. Capacity $c(S,T)=\sum_{u\in S}\sum_{v\in T} c(u,v)$ — only $S\to T$ edges count.
Matching Edge set $M$ with no two edges sharing a vertex. Maximum matching = largest such $M$.
Bipartite matching Matching in a bipartite graph (parts $X,Y$; edges cross only). Saturates a side if it covers every vertex there.

Key theorems & formulas

Result Statement
Value across a cut $\lvert f\rvert=\sum_{u\in S,v\in T} f(u,v)-\sum_{u\in S,v\in T} f(v,u)$ (measure flow at any cut).
Weak duality For every flow and every cut: $\lvert f\rvert\le c(S,T)$.
Max-flow min-cut $\displaystyle \max_f \lvert f\rvert=\min_{(S,T)} c(S,T)$.
Optimality (3-way equiv.) $f$ max $\iff$ no augmenting path in $G_f$ $\iff$ $\lvert f\rvert=c(S,T)$ for some cut.
Min-cut construction At a max flow, $S=$ residual-reachable set of $s$; all $S\to T$ edges are saturated, all $T\to S$ edges carry 0.
Integrality Integer capacities $\Rightarrow$ Ford–Fulkerson (from zero flow) returns an integer max flow.
Matching = flow Max bipartite matching size $=$ max-flow value on the unit-capacity reduction.
Hall's theorem $X$-saturating matching exists $\iff \lvert N(W)\rvert\ge\lvert W\rvert$ for all $W\subseteq X$.

Ford–Fulkerson / Edmonds–Karp (the algorithm)

f <- 0                                  # start from the zero flow
while G_f has an s->t path p:           # an augmenting path
    Δ <- min residual capacity on p     # bottleneck
    for each step u->v on p:
        if forward edge:  f(u,v) += Δ   # push
        if back edge:     f(v,u) -= Δ   # CANCEL existing flow
return f                                # max flow when no path remains
  • Path choice = which algorithm. BFS (shortest path) ⇒ Edmonds–Karp, $O(VE^2)$.
  • Why it's correct: halting means "no augmenting path" = condition (ii) ⇒ flow is max (theorem).

Bipartite matching → max flow (reduction recipe)

Step Add
1 source $s$, sink $t$
2 $s\to x$, capacity 1, for each $x\in X$
3 $x\to y$, capacity 1, for each original edge $x{-}y$
4 $y\to t$, capacity 1, for each $y\in Y$

Run max_flow(s,t). Matching = middle edges $x\to y$ carrying 1 unit; size = flow value. Unit caps force ≤1 per vertex on each side.

Decision aid — "what do I compute?"

Goal Compute Read off
Max throughput $s\to t$ max flow value $\lvert f\rvert$
Prove flow optimal residual-reachable set of $s$ matching cut of equal capacity
Cheapest disconnect of $s,t$ min cut ($=$ max flow) the saturated cut edges
Largest set of compatible pairs matching → max flow reduction flow-carrying middle edges
"Can everyone be assigned?" max flow vs. $\lvert X\rvert$ (or Hall) deficient $W$ if not
Foreground/background split (vision) min cut $S$ = foreground side

Common pitfalls

  • ⚠️ A back edge $v\to u$ subtracts from $f(u,v)$ — it is not a new edge in the original graph. The original edge set never changes.
  • ⚠️ A flow below some cut proves nothing. Optimality needs a cut of equal capacity (the min cut), not any cut.
  • ⚠️ Cut capacity counts only $S\to T$ edges. $T\to S$ and within-side edges contribute 0.
  • ⚠️ Bipartite matching needs the integer max flow; fractional flows don't correspond to matchings (integrality saves you with integer capacities).
  • ⚠️ Naive "push on any spare forward path" greed is wrong — it can't undo a bad commitment. You need residual back edges.

Toolkit additions (dmtoolkit/graphs.py)

Function Signature Returns
max_flow max_flow(g, s, t) maximum flow value (Edmonds–Karp; BFS augmenting paths)

Composes with Graph (Ch. 27), bfs/dfs (Ch. 28), dijkstra (Ch. 29), mst_kruskal (Ch. 32). Feed it the unit-capacity reduction ⇒ bipartite matching size. Used in the Chapter 39 Track B social-network analyzer.

One-line mental model

Max flow = min cut. The most you can push equals the cheapest way to sever the network — a maximization and a minimization that are secretly the same number (strong duality). Find a flow and a cut of equal value, and you have proved both optimal.