Maximal matching of bipartite graph

Bipartite graph is such a graph, whose nodes could be divided into two sets, X and Y. Any node in either X or Y does not connect to the other node in the same set. Any edges connect one node in X and one node in Y. Given a bipartite graph, G, M is a subset of the edges in G. If any two edges do not connect to the same node, we call M is a match. In addition, if M contains the maximal number of edges, M is a maximal match.
There are mainly two methods to find maximal matching, max flow algorithm and Hungarian algorithm. Hungarian algorithm use the idea behind max flow algorithm, but simplified the max flow algorithm based on the properties of bipartite matching and improve the performance.
Before we read those algorithm, another definition need to be clarified, augmenting path. If P is the path that connects two unmatched nodes, and the nodes in M and not M appear alternately, then we call P is a augmenting path on M. Then we could generalize 4 conclusions as follows:

• The length of P must be odd; the first edge and the last edge should not belongs to M;
• All the odd number edges are not in M, and all the even number edges are in M;
• A bigger match M` could be found by “invert” P. Here, “invert” means put all odd number edges into M, and remove all even number edges in P from M. So there must be one more match.
• M is the maximal match, if and only if, there is not augmenting path in G;

So the key to solve the max flow algorithm is finding the augmenting path. The basic steps are as follows:

Initialize the Maximal Match, MM, as null;
while( augmenting path exists )
{
    Add the augmenting path into MM;
    
}

The main idea of the algorithm above is keeping searching augmenting paths, which could increase the number of matching. In matching problem, augmenting path looks like a zigzag. If the first edge of a graph does not in match, its second edge should be in, and so on. If we could invert the selection of matches, we could find one more match legally.
Further Properties:

• Minimal covering: find the minimal set of node, m, and make each edge connects to an arbitrary node in m. So,

            minimal covering = the maximal matching

• The minimal path covering = |N| – maximal match.

Use minimal number of unoverlapping edges cover all the nodes in the graph, G. We could build up a bipartite model. All the nodes are divided into two sets, X and Y. If there is a edge i->j, then we add edge(i->j`). If the maximal match is m, then the result is n-m;

• Max independent set = (node number) – (bipartite maximal  match)

In a graph which have N nodes, we select m nodes, and each pair of the m nodes are not connected. Then find the maximal m. If G satisfies bipartite, then we could use bipartite matching to find result, as the minimal path covering = |N| – maximal match