Unit 3.9 · about 2 h
112 / 324Flow and matching at recognition depth
Flows and matchings are recognition vocabulary at this stage: routing, assignment and cut problems recur across ML systems, and naming the reduction correctly is the transferable skill.
- explain
You can now
- State the max-flow min-cut theorem and explain how an equal-value cut certifies a claimed maximum flow.
- Reduce bipartite matching to max flow with a source, a sink and unit capacities, and read a matching back from the flow.
- Recognize flow-shaped problems (capacities, bottlenecks, conflict-free assignment) and name what a full implementation would still need.
Covers
- Flow and matching at recognition depth
Study, in this order
2 steps
- Maximum Flows and Minimum Cuts, Chapter 10Algorithms - graph chapters
10.1 Flows, 10.2 Cuts, 10.3 The Maxflow-Mincut Theorem and 10.4 Ford and Fulkerson's augmenting-path algorithm (printed pp. 328-336)
- Flow applications including bipartite matching, Chapter 11Algorithms - graph chapters
11.1 Edge-Disjoint Paths and 11.3 Bipartite Matching with the source-sink unit-capacity reduction (printed pp. 353-357)
Depth · Read the reductions and state the constructions; skip implementing Dinic or push-relabel here.
Focus on
- Recognition signals: capacities on edges plus a bottleneck question means flow; two-sided assignment with conflicts (left set, right set, allowed pairs) means bipartite matching.
- The certificate is the cut: a flow of value \(F\) with a cut of capacity \(F\) is maximum by the theorem. Always exhibit both.
- Bipartite matching is flow with unit capacities: source to left, allowed edges left to right, right to sink; integer flow of value \(k\) is a matching of size \(k\).
- Explicit non-goals: residual-graph implementation at scale, Dinic or push-relabel, general (non-bipartite) matching and spectral methods stay in the section's leave-for-later list.
Reproduce closed-book
[(0,1,3),(0,2,2),(1,2,1),(1,3,2),(2,3,3)] from 0 to 3 and report max flow 5. Exhibit the certifying cut (\(\{0\}\) versus \(\{1, 2, 3\}\)) with capacity 3 + 2 = 5.Traps
- Augmenting without residual backward edges: the greedy path choice gets stuck below maximum because it cannot undo earlier flow. Backward edges with residual capacity are the algorithm, not an optimization.
- Confusing bipartite check with bipartite matching: two-coloring decides a partition exists; matching finds the largest conflict-free edge set given one. LC 785 does not solve LC 1349.
- Undirected edges as single arcs: an undirected edge of capacity
cbecomes two opposite arcs of capacityc. One arc forbids flow in the other direction and can silently lower the maximum.
Practice
LeetCode 1349: Maximum Students Taking Exam
The three listed examples (mixed boards with blocked seats)
Recognition framing only: state the column-parity reduction to bipartite matching, solve with a simple augmenting-path matcher, and verify against brute force on \(2 \times 3\) boards. Do not implement Dinic. After-attempt reference is Erickson Section 11.3.
Self-test
-
State the max-flow min-cut theorem and its use as a certificate.
The value of a maximum \(s\)-\(t\) flow equals the capacity of a minimum \(s\)-\(t\) cut. A flow of value \(F\) plus a cut of capacity \(F\) proves optimality without trusting the solver: no flow can exceed any cut's capacity. -
Give the bipartite-matching-to-flow reduction exactly.
Source \(s\) to each left vertex capacity 1, each allowed left-right pair capacity 1, each right vertex to sink \(t\) capacity 1. Integer max flow of value \(k\) saturates \(k\) disjoint pairs: a matching of size \(k\), and every matching yields such a flow. -
Why does LC 1349 admit a matching model?
Color seats by column parity. Every conflict (left, right, upper-left, upper-right) joins an even column to an odd one, so the conflict graph is bipartite. The answer is a maximum independent set of free seats, which on a bipartite graph equals the number of free seats minus a maximum matching (Konig's theorem). A checkerboard coloring fails: diagonal neighbors share a color. -
What stays deliberately excluded, and why can you stop?
Dinic, push-relabel, general-graph matching and spectral methods: the section checkpoint needs recognition plus a small checked construction, and the section's leave-for-later list names the rest.
Completion criterion
Stop when
Your blank-file script prints max flow 5 with the capacity-5 cut, and you can reduce a new assignment narrative to source-sink-unit capacities or explain why it is not a flow problem.
Mark passed, then open 4.1 Only mark this when you can do it without notes.Leads to
- 5.9 Dynamic programming as shortest paths, formulations and limits Reductions are the shared move: this unit reduces matching to flow the way later units reduce problems to shortest paths.
- stage 04 · Classical Machine Learning Assignment and matching structure reappears in data association and ranking evaluation.
Comes after
- 3.8 Graph certificates and exhaustive small-graph validationCarry the checker habit into matching: a cut of equal value certifies a flow.
Resources for this unit
- Algorithms - graph chapters Use the basic graph, depth-first search, minimum spanning tree, shortest path and flow chapters, and lecture note 11 Disjoint Sets for union-find, for correctness proofs and counterexamples to tempting wrong algorithms.
Also in this section
- DSA Handbook - graphs Study all of Part 8 in order. For each algorithm, write the representation, invariant, forbidden input assumptions and independently checkable output before reading the implementation.
- AlgoMaster DSA - graph slice Attempt Number of Islands, Course Schedule II and Network Delay Time cold. They cover traversal, dependency modeling and weighted shortest paths; add one narrative problem only if graph modeling remains weak.
- Hypothesis - generated graph tests Generate small sparse, dense, disconnected, cyclic, parallel-edge and weighted graphs. Compare optimized results with exhaustive or deliberately simple references and retain shrunk failures.
- NeetCode - unseen graph problems Use two unseen story problems without graph tags. Grade the model, assumptions, certificate and tests as well as the final answer.