Before learning maximum bipartite matching let us understand the meaning of bipartite graph. A graph is said to be bipartite if the vertices in the graph can be partitioned into two set A and  set B such that no two vertices within the same set are connected. i.e all the vertices in set A have end points in set B.


Maximum Bipartite MatchingWhat is matching?

A matching is an independent set of edges with no common endpoints i.e no two edges are adjacent. for example the set of edges comprised of 0-1,2-5, and 3-6  are called a matching.

What is maximum bipartite matching?

A Bipartite matching is called maximum matching when, if we add any edge in it(matching), it is no longer a matching.


How to find Max Bipartite Matching


There is simple approach to find max bipartite matching. simply keep adding edges from bipartite graph to the matching until no more edges can be added.  The max bipartite matching problem can be solved using Ford Fulkerson flow method but we need to convert the given bipartite graph as a flow network. The max bipartite matching would be the maximum flow of the flow network. To know about max flow network problem using Ford Fulkerson method follow the link http://wikistack.com/max-flow-problem-ford-fulkerson-algorithm/.

Let us find max bipartite matching in below given graph

Maximum Bipartite MatchingFig: 1.0

Step 1:

Convert the above graph as a flow network.

Maximum Bipartite Matching

Fig: 1.1

We can notice in the figure 1.1  that two new vertices are being added to the graph. one is source vertex (10) and another is sink vertex(11). From source vertex there are directed edge going from source vertex (10) to the left side veritces and there are incoming edges to the sink vertex (11) from right side vertices. All undirected edges between left to right vertices are now directed edges.

Step 2:

Assign flow capacity 1 to all edges.

Step 3:

Apply Ford Fulkerson on the graph to solve max flow problem. The max flow of the network is max bipartite matching.


The below sample code implementation run  Ford-Fulkerson method on graph (Fig: 1.1). The Graph has been represented as the adjacency matrix.

Output:

Ref:

http://pages.cs.wisc.edu/~shuchi/courses/787-F09/scribe-notes/lec5.pdf

https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/matching.pdf