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;

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

## No comments:

## Post a Comment