Part VI · Graph Algorithms and Tree-Graph Techniques
40. Graph Matchings and Assignment
6 lessons•22 topics•Intermediate / Advanced
6 of 6 lessons published
40.011 animated
Matching basics
- Matched/unmatched vertices
- Alternating path
- Augmenting path
- Maximum vs maximal matching
40.022 animated
Bipartite matching
- DFS augmenting paths
- Hopcroft-Karp
- Matching size
- Vertex covers
40.031 animated
Konig's theorem
- Maximum matching equals minimum vertex cover in bipartite graph
- Construct cover from alternating BFS
40.041 animated
Weighted matching
- Hungarian assignment algorithm
- Cost matrix
- Dual variables
- Perfect matching
40.052 animated
General matching
- Blossom algorithm overview
- Odd-cycle contraction
- Tutte theorem overview
40.062 animated
Matching applications
- Job assignment
- Students-projects
- Domino tiling
- Scheduling
- Minimum path cover in DAG