Understanding the solution to maximum bipartite matching problem
The maximum bipartite matching problem can be solved by converting it into a maximum flow problem. To solve the problem, we create the corresponding flow network for the bipartite graph and run an algorithm to find the maximum flow in the flow network. The maximum flow in the flow network is the maximum matching of the bipartite graph. We will prove this later in the course.
Consider a bipartite graph with nodes separated in two disjoint sets, L and R, with some edges connecting nodes in these sets.
An example bipartite graph.
Algorithm
The first step in solving the maximum bipartite matching problem is to create the corresponding flow network of the bipartite graph. We define a corresponding flow network for the graph by adding a source and sink node, where the source has a directed edge towards all nodes in the set L, edges between nodes in the sets L and R are converted to directed edges, and all nodes in the set R have a directed edge towards the sink. All edges in the flow network are set to have a capacity of 1 unit.
The corresponding flow network of the example bipartite graph.
Liking the course? Check our discounted plans to continue learning.