Challenge: Bipartite Matchings

Apply max flow algorithms to solve matching problems.

In this lesson, we’ll apply our maximum flow implementation to solve matching problems in bipartite graphs. Recall that an undirected graph is called bipartite if we can partition its nodes into two sets (the left and the right partition) such that there are no edges inside a partition. We learned previously how to identify bipartite graphs in the challenge lesson of the graph traversal chapter.

The maximum matching problem

Bipartite graphs can be used to formulate various kinds of matching problems. For example, assume that you are the CEO of a company and assign tasks to your employees. There are n1n_1 employees and n2n_2 ​​ tasks, but not every employee can perform each task. Your goal is to assign employees to tasks, such that the number of working employees is maximized. The assignment should be 1 to 1, meaning that every employee would only perform one task, and every task would be done by only one employee.

We can model this problem using a bipartite graph. There are n1n_1 nodes in the left partition, representing the workers, and n2n_2 nodes in the right partition, representing the tasks. We’ll draw an edge from an employee uu to a task vv if uu can perform the task vv. The resulting bipartite graph might look like this:

Get hands-on with 1200+ tech skills courses.