Network Flows & Matching
Network Flows & Matching
A network flow assigns non-negative values to directed edges (capacities) and finds the maximum flow from source to sink. The max-flow min-cut theorem equates maximum flow to the minimum cut capacity — a profound duality. Matching theory pairs vertices with disjoint edges; Hall's theorem characterizes when a perfect matching exists in bipartite graphs. These results underlie assignment problems, scheduling, and network routing algorithms.
Maximum Flow & Min-Cut
A flow network has a source $s$, sink $t$, and capacity $c(u,v)\geq 0$ on each directed edge. A flow satisfies: capacity constraints $0\leq f(u,v)\leq c(u,v)$; conservation $\sum_u f(u,v)=\sum_w f(v,w)$ for $v\neq s,t$. The value $|f|=\sum_v f(s,v)$ is the flow out of $s$. An $s$-$t$ cut $(S,T)$ with $s\in S,t\in T$ has capacity $c(S,T)=\sum_{u\in S,v\in T}c(u,v)$. Ford-Fulkerson algorithm: augment along residual paths until no augmenting path exists.
Max-Flow Min-Cut Theorem
In any network, the maximum $s$-$t$ flow equals the minimum $s$-$t$ cut capacity: $$\max|f|=\min c(S,T).$$ Proof: (i) every flow $\leq$ every cut (by telescoping); (ii) Ford-Fulkerson terminates when no augmenting path exists; at termination, the reachable set $S$ from $s$ in residual graph defines a cut with $c(S,T)=|f|$. Applications: maximum bipartite matching (König's theorem: maximum matching = minimum vertex cover); vertex connectivity; disjoint paths (Menger's theorem).
Example 1
Apply Ford-Fulkerson to find max flow from $s$ to $t$ in a network with edges: $s\to a:4$, $s\to b:3$, $a\to t:3$, $b\to t:4$, $a\to b:1$.
Solution: Path 1: $s\to a\to t$: bottleneck 3, send 3. Residual: $s\to a:1$, $a\to t:0$, $t\to a:3$. Path 2: $s\to a\to b\to t$: bottleneck $\min(1,1,4)=1$, send 1. Residual: $s\to a:0$. Path 3: $s\to b\to t$: bottleneck $\min(3,3)=3$, send 3. Total flow: $3+1+3=7$. Min cut: $\{s,a,b\}|\{t\}$: capacity $(a,t)+(b,t)=3+4=7$ ✓. Or cut $\{s\}|\{a,b,t\}$: $c=4+3=7$.
Example 2
State and prove Hall's marriage theorem for bipartite graphs.
Solution: Hall's theorem: a bipartite graph $G=(A\cup B,E)$ has a perfect matching of $A$ iff for every $S\subseteq A$: $|N(S)|\geq|S|$ (Hall's condition). Proof: convert to max-flow: $s\to a_i:1$, $a_i\to b_j:1$ (if edge), $b_j\to t:1$. By max-flow min-cut, max matching $=n$ iff min cut $=n$. A cut $
Practice
- Describe the Edmonds-Karp algorithm (BFS augmentation) and prove it runs in $O(VE^2)$.
- Prove König's theorem: in a bipartite graph, max matching = min vertex cover.
- Show Menger's theorem: the max number of disjoint $s$-$t$ paths equals the min vertex cut separating $s$ from $t$.
- Apply matching to a bipartite scheduling problem: 5 jobs and 5 machines with compatibility constraints.
Show Answer Key
1. Edmonds-Karp uses BFS to find shortest augmenting paths. Each augmentation increases the shortest-path distance from $s$ to at least one vertex. Since distances are bounded by $V$, and each distance level has at most $E$ saturating augmentations, total augmentations $\le O(VE)$, each costing $O(E)$ for BFS. Total: $O(VE^2)$.
2. König's: in bipartite graphs, max matching $=$ min vertex cover. Proof: from a max matching $M$, apply alternating-path arguments from unmatched vertices. The set of vertices reachable defines a minimum vertex cover of size $|M|$.
3. Menger's: max number of internally vertex-disjoint $s$-$t$ paths $=$ min $s$-$t$ vertex cut. Proof: the $\le$ direction is clear (each path must use a vertex from any cut). The $\ge$ direction follows from the max-flow min-cut theorem applied to a transformed network.
4. Model as bipartite graph: jobs on one side, machines on the other. Edge $(j_i,m_k)$ if job $i$ can run on machine $k$. Find a maximum matching (e.g., via Hungarian algorithm). A perfect matching assigns all 5 jobs to compatible machines if one exists.