Graph Theory37 sections · 1633 units
Open in Course

Bipartite Matching

(Classic flow application)

A bipartite graph has two sets of nodes, and edges only connect nodes from different sets. A matching is a subset of edges where no two edges share a node. Maximum bipartite matching finds the largest matching. This is a max flow problem in disguise.

Add a source connected to all nodes in the left set, and a sink connected to all nodes in the right set. All edges have capacity 11. Max flow equals the maximum matching size.