Matching in Graphs

Math for CS · Axiom Academy

Maximum matchings, Hall's theorem, and the Hungarian algorithm Maximum matching: A matching with the largest possible number of edges Perfect matching: Every vertex is matched — requires |V| to be even and |M| = |V|/2 Maximal matching: No edge can be added without violating the matching property (not necessarily maximum) Matching is especially clean and well-understood in bipartite graphs G = (U, W, E) . The question becomes: how many elements of U can be paired with distinct elements of W ? The condition is called Hall's condition . It says: every group of applicants must collectively be qualified for at least as many jobs as there are applicants in the group. The key algorithmic idea for finding maximum matchings is the augmenting path . Alternates between non-matching and matching edges Ends at another unmatched vertex If an augmenting path exists, we can "flip" the matching status of every edge along it — unmatched edges become matched and vice versa. This increases |M| by 1. Algorithms for Maximum Bipartite Matching The Hungarian algorithm (Kuhn-Munkres) finds a maximum matching in a bipartite graph. For the unweighted case, it repeatedly finds augmenting paths using BFS/DFS. For each unmatched vertex in U , search for an augmenting path via BFS If found, augment M along the path Repeat until no augmenting path exists An improvement that finds multiple augmenting paths simultaneously using BFS to find shortest augmenting paths, then DFS to augment along them.

This is the written version of the interactive lesson above. See the full Math for CS course.