Matching or independent set of edges is a set with no common edges in a graph. Finding a match in a bipartite graph is equivalent to the network flow problem.

Graph matching algorithm are commonly used in OI. It can be generally divided into maximum matching and maximum weight matching. We will first introduce the bipartite graph, and then propose solutions for general graphs.

Matching

In graph theory, suppose the graph G=(V,E) , where V is vertex set and E is the edge set.

A set of edges that have no common vertices in pairs (M(M\in E)) is called the matching of this graph.

Define the size of the match as the number of edges |M| , and the largest number of edges M is the maximum match.

When the graph is weighted, the match with maximum sum of edges' weights is maximum weight matching.

The edges in the match are called matched edges, and the opposite are called unmatched edges.

If a vertex belongs to M and is the end vertex of at most one edge, it is called matched vertex, otherwise it is called unmatched vertex.

Maximal matching: No more matching edges can be added. It may not be the maximum match. Maximum matching: The match with the maximum number of matches. Perfect matching/Complete matching/1-factor: All vertices belong to the matching, and also meet the maximum match. Near-perfect matching: The number of vertices in the graph is odd, and there is exactly one vertex that is not in the match. The graph after removing this vertex is called factor-critical graph.

Maximal matching graph-match-1 maximum matching graph-match-2

Bipartite graph matching

The matching on a bipartite graph is called bipartite matching. graph-match-3

Let G be a bipartite graph. If there are no common vertices in any two edges in the subgraph M of G , then M is called a match of the bipartite graph G , and the number of edges in M is the number of matches.

Complete match

Let G=<V_1, V_2, E> be a bipartite graph, where |V_1| \leq |V_2| . M is a maximum matching in G , and |M|=2|V_1| . In this case, M is called a complete match from V_1 to V_2 .

Hall's Theorem

Let bipartite graph G=<V_1, V_2, E> , where |V_1| \leq |V_2| . Then there exists a complete match between V_1 and V_2 in G if and only for any S \ subset V_1 , |S|\leq|N(S)| , where N(S)=\Cup_{v_i \in S}{N(V_i)} is the neighborhood of S .

Maximum matching

Finding maximum number of matching edges in bipartite graph is called the maximum matching problem.

Algorithm

A basic problem in combinatorial optimization is to find maximum matching.

Bipartite graph maximum matching

In the unweighted bipartite graph, the Hopcroft-Karp algorithm can be used to solve the problem in O(\sqrt{V}E) .

Bipartite graph maximum weight matching

In the weighted bipartite graph, it can be solved by Hungarian algorithm.

If the Bellman–Ford algorithm is used to find the shortest path, the time complexity is O(V^2E) . If Dijkstra algorithm or Fibonacci heap is used, it can be solved in O(V^{2}\log {V}+VE) .

General graph maximum matching

In the unweighted general graph, the Edmonds' blossom algorithm can be used to solve the problem in O(V^2E) .

General graph maximum weight matching

In the weighted general graph, the Edmonds' blossom algorithm can be used to solve the problem in O(V^2E) .

References

buildLast update and/or translate time of this article，Check the history
editFound smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github
peopleContributor of this article accelsao
translateTranslator of this article Visit the original article!
copyrightThe article is available under CC BY-SA 4.0 & SATA ; additional terms may apply.

Comments