Graph Theory37 sections · 1633 units
Open in Course

Problem - Maximum Matching

(General bipartite graph)

Generic maximum bipartite matching problem: Given a bipartite graph with two groups and a set of edges connecting them, find the largest possible matching. You will see this pattern in many forms: assigning resources, pairing items, scheduling events, allocating workers to jobs.

The solution is always the same: build the bipartite graph and run Kuhn's algorithm to find the maximum matching. Practice recognizing this structure.