# Maximum Bipartite Matching

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.

*What 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

*Step 1: *

*Step 1:*

*Convert the above graph as a flow network.*

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: *

*Step 2:*

*Assign flow capacity 1 to all edges.
*

*Step 3: *

*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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
#include <iostream> #include <string.h> using namespace std; #define N 11 #define INF 9999999 // flow network int Flow[N][N]; // visited array bool visited[N]; // the flow network graph shown in the above example fig: 1.1 //0 1 2 3 4 5 6 7 8 9 10 int graph[N][N] = { {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0}, //0 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1}, //1 {0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0}, //2 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1}, //3 {0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0}, //4 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1}, //5 {0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0}, //6 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1}, //7 {0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0}, //8 {1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0}, //9 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, //10 }; int dfs (int s, int t, int minimum) { visited[s] = true; // if source and sink is same if (s == t) return minimum; for (int i = 0; i < N; i++) { int flow_capacity = graph[s][i] - Flow[s][i]; if (!visited[i] && flow_capacity > 0) { // find min capacity in dfs path if (int sent = dfs (i, t, min (minimum, flow_capacity))) { // adjust the capacity Flow[s][i] += sent; Flow[i][s] -= sent; return sent; } } } return false; } int main () { // initialize initial flow capacity 0 memset (Flow, 0, sizeof (Flow)); // initialize visited array false initially memset (visited, 0, sizeof (visited)); int s = 9; int t = 10; int max_flow = 0; // while there is augmenting path , from s and t // with positive flow capacity while (int sent = dfs (s, t, INF)) { max_flow += sent; // reset visited array , for searching next path memset (visited, 0, sizeof (visited)); } cout <<"The max bipartite is : "<< max_flow; cout <<endl; } |

*Output:*

1 |
The max bipartite is : 3 |

Ref:

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

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

## Leave a Reply