A matching of a graph is a subset of edges such that no two edges share a vertex. A maximum matching of a graph is a matching with the maximum number of edges (matching as many vertices as possible).
For the convenience of description, we assume ( n vertices and m edges, and a set M if no two edges in M have a common vertex) and partition the graph into two disjoint sets - left and right. All matching edges connects to both left and right sets. One common example of bipartite graph matching is matching a group of men and women.
Because the length of augmenting path is odd, and the starting vertex of the path is either on the left or right, we first consider finding the augmenting path from the unmatched vertices on the left.
Please note that because of the alternating path, the odd-numbered edges on the augmenting path are all unmatched edges, and the even-numbered edges are all matched edges. So left-to-right edges are all unmatched, and right-to-left edges are all matched.
So we define the direction for the bipartite graph, and the problem is converted to finding a directed path starting from a given vertex to an unmatched vertex in a directed graph, which is actually equivalent to whether the given starting vertex s can reach the ending vertex t.
This means that we can just do the DFS traversal from the starting vertex until a certain unmatched vertex is found. The time complexity for this step is O(m) .
When the augmenting path has not been found, the path formed was called an alternating tree.
alternating tree: a tree whose root is an unmatched vertex. All root-to-leaf paths in an alternating tree are alternating paths with respect to M . If we can add an unmatched vertex other than the root vertex to an alternating tree, we have found an augmenting path.
Because we want to enumerate n points, the overall time complexity is O(nm) .
Bipartite graph maximum matching can be converted into the flow network model. The Dinic's algorithm can also be used to compute the maximum flow in a network.
Connect all vertices on the left to the source vertex, and all points on the right to the sink vertex. All of these edges have a capacity of 1. Each original edge is connected from left to right with capacity 1 as well . The maximum flow is the maximum match, which can be found in O(\sqrt{n}m) .
Dinic's algorithm contains two parts. The first part uses BFS to construct network flow in O(m) time complexity; The second part performs DFS for augmentation in O(nm) time complexity.
But because the capacity is 1 , the actual time complexity is O(m) .
Next, for the first O(\sqrt{n}) rounds, the time complexity is O(\sqrt{n}m) . After O(\sqrt{n}) rounds, the length of each augmenting path is at least \sqrt{n} , and the number of such path does not exceed \sqrt{n} .
So it only needs to run \sqrt{n} rounds. The overall time complexity is O(\sqrt{n}m) .
Choose the minimum vertices to satisfy the requirement that at least one endpoint of each edge is selected. It is not difficult to find that the complement set is an independent set.
In bipartite graphs, the minimum vertex cover = n - maximum independent set.
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.