Shulou(Shulou.com)06/02 Report--

What is the Hungarian algorithm? aiming at this problem, this article introduces the corresponding analysis and solution in detail, hoping to help more partners who want to solve this problem to find a more simple and feasible way.

1 bipartite graph

Bipartite graph, also known as bipartite graph, is a special model in graph theory. Let G = (V∈ E) be an undirected graph. If vertex V can be divided into two disjoint subsets (A ∈ B), and the two vertices I and j associated with each edge in the graph belong to these two different vertex sets (I and J) respectively, then G is called a bipartite graph.

To put it simply, if all vertices in a graph can be divided into two sets, and the heads and tails of all edges in the graph do not belong to the same vertex set, but span two sets, then the graph is a bipartite graph.

For example, the graph shown in figure 1.1, no matter how the vertex set is divided, can not guarantee that the heads and tails of all edges belong to different sets, so the graph shown in figure 1.1 is not a bipartite graph.

Figure 1.1

For example: the undirected graph shown in figure 1.2:

Figure 1.2

Taking the vertex a _

Figure 1.3

It can be seen that the vertices in the graph can be divided into two sets An and B, and the head and tail of any edge belong to set An and set B. therefore, this graph is a bipartite graph.

2 matching

Matching: in graph theory, a matching is a set of edges where any two edges have no common vertices.

For example, the red edge in figure 2.1 can be a match of the diagram shown in figure 1.3.

Figure 2.13 maximum match

Maximum matching: the matching with the largest number of matching edges in all matches of a graph is called the maximum matching of this graph. Figure 3.1 is a maximum match, which contains four matching edges.

Figure 3.14 perfect match

Perfect match: if all vertices in a graph are matching points, then it is a perfect match. A perfect match must be the maximum match (any point of the perfect match has already been matched, and adding a new matching edge must conflict with the existing matching edge), but not every graph has a perfect match.

5 alternate paths

Alternate path: starting from an unmatched point, passing through unmatched edges, matching edges, and unmatched edges in turn. The resulting path is called alternating path.

6 augmentation path

Augmented path: alternate paths are taken from one unmatched point. If another unmatched point is passed (the starting point is not counted), the alternate path is called augmented path (agumenting path).

Augmented path properties:

The path length of      (1) P must be odd, and neither the first edge nor the last edge belongs to M, because the two endpoints belong to two sets and do not match.

     (2) P can get a larger matching M'by taking the inverse operation.

     (3) M is the maximum match of G if and only if there is no augmentation path relative to M.

7 Hungarian algorithm

Hungarian algorithm: the maximum matching algorithm for finding bipartite graphs using augmented paths is called Hungarian algorithm. (proposed by Hungarian mathematician Edmonds in 1965).

The basic idea: by looking for the augmentation path, the matching edges and non-matching edges in the augmentation path are exchanged with each other, so that there will be one more matching edge until the augmentation path cannot be found.

For example, taking the bipartite graph shown in figure 2.1 as an example, the Hungarian algorithm is used to solve the maximum matching of the graph.

The main results are as follows: (1) starting from vertex a, following the alternating path, the first unmatched edge is, and the first unmatched edge is the unmatched point, which forms the augmented path. Let it be a matching edge, and the vertex aQuery e is a matching vertex.

(2) starting from vertex b, the first unmatched edge is to reach vertex e, select matching edge, reach a, select unmatched edge, g is unmatched point, and find an augmented path.

(3) the matching edges and unmatched edges in the exchange augmentation path are matched as follows.

(4) starting from vertex c, the first unmatched edge is to reach vertex e, and then follow the alternating path to vertex b, and can't move on.

(5) starting from vertex c, select the second unmatched edge.

(6) starting from vertex d, select unmatched edges, reach vertex g, select matching edges, reach vertex a, select unmatched edges to reach vertex e, select matching edges, reach the top b, no edges can be selected, and no augmentation path is found.

(7) continue to start from vertex d, select unmatched edges, find the augmented path, change the edges into matching edges, and the algorithm ends.

8 conclusion

Hungarian algorithms are often used in assignment problems, such as task matching problems. By transforming it into the form of bipartite graph, the maximum matching is solved to ensure the optimal allocation.

The answer to the question about what the Hungarian algorithm is is shared here. I hope the above content can be of some help to you. If you still have a lot of doubts to be solved, you can follow the industry information channel to learn more about it.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.