Lesson 183
Bipartite Matching
Augmenting Paths · König & Hall · Assignment
1:00How to pair two disjoint sets of vertices optimally using augmenting paths, and the theorems — Berge, König, Hall — that govern what is possible.
By the end, you can
- Define a bipartite graph and verify bipartiteness using 2-coloring or odd-cycle detection.
- Determine whether a set of edges is a valid matching, and distinguish maximal from maximum.
- Trace an augmenting path on a small graph and apply the flip to grow the matching.
- Explain why Berge's theorem gives a correct stopping criterion for augmenting-path algorithms.
- Compare the complexity of Kuhn's algorithm and Hopcroft–Karp and explain why Hopcroft–Karp is faster.
- State König's theorem and use it to read off the minimum vertex cover size from the maximum matching.
- Apply Hall's marriage condition to decide whether a complete matching from the left side is possible.
- Outline the four steps of the Hungarian algorithm and state its O(n³) complexity.
- Identify real-world problems (job assignment, kidney exchange, ad allocation, ride-hail dispatch) as bipartite matching instances.
Up next in Algorithms & Graph Algorithms
