KM algorithm can be used to solve the maximum weight matching for a weighted binary graph if there is a perfect match.

If there is no perfect match for this binary graph, there are two methods. One is to solve the network flow problem. The other is to add some points and edges of zero weight to make it a fully weighted bisection graph.

Obviously, any binary graph can be transformed into a perfect matching binary graph by the second method, and the result will not change. Therefore, KM algorithm can solve the maximum weight matching of all weighted binary graphs.

Several concepts used in KM algorithm: feasibility label, phase equal subgraph, staggered tree.

L[u] represents the label of U, w[u, v] represents the weight of two connecting edges.

Feasibility label: if for weighted bisection graph G = (X,Y) L[X] + L[Y] >= W [X,Y] (X ∈ X,Y ∈ Y). Then L[] is the feasibility label.

The feasibility label for a weighted bipartite diagram always exists.

A trivial possible vertex label is for u ∈(X∪Y), there is

If u ∈X, L[u] = Max (w[u, y]).

If U ∈Y, L[v] = 0.

Phase DengZi diagram: a G is an empowerment figure, G to {edge (x, y) | x ∈ x, y ∈ y, L [x] [y] = = w + L (x, y)} for edge set generated subgraph DengZi G phase diagram.

Let the phase subgraph of G be G ‘, then G ‘is the same as the point set of G.

In view of the limited narrative ability, the figure above is directly shown:

The edges of graph G are stored as an adjacency matrix.

​

FIG. G and its trivial label:

​

Phase subgraph of G:

​

I was really stumped by this idea of staggered trees when I learned this algorithm. You have to write that down.

Staggered path: let M be a match of G, P be a path of G, and E(G) be the edge set of graph G. If edges in P alternate between M and E(G) -m, P is said to be m-interleaved.

Staggered tree: let M be a match of G, and u be the M unsaturated point of X. If there is a tree H contained in G, and the following two conditions are met:

1. U ∈ V (H);

2. For each vertex V of H, the only U-V path in H is an M-staggered path.

Then H is said to be an M-staggered tree with u as the root.

Continue with the image above:

In figure G, the thick line is a match M of G.

​

Staggered tree with root x1.

​

KM algorithm:

Let G be the weighted dichotomy graph, L[] be the feasible top standard of G, and GL be the phase subgraph of G determined by L[].

If G is not a complete bipartite graph, some vertices and edges of weight 0 are added, and L[] is initialized to a trivial vertex label.

1. For L[], determine the phase subgraph GL of G.

2. The Hungarian algorithm is used to find the perfect match M for GL. If M exists, then M is the maximum weight match and the algorithm terminates. Otherwise the Hungarian algorithm must terminate at a staggered tree H, go to step 3.

3. The calculation of alpha = min {L [y] – [x] + L w (x, y) | x, y ∈ V (H), x ∈ x, y ∈ (y – studying y V (H))}. And press to update L[].

​

Then go to step 1.

Each update L[] has:

1. For the edge with two endpoints in the staggered tree, its properties will not be affected, that is, the edge that existed in the phase subgraph still exists in the phase subgraph.

2. For the edge whose two endpoints are not in the staggered tree, 2 will not affect its properties, that is, the edge that existed in the phase subgraph still exists in the phase subgraph, and vice versa.

3. For an edge with only one endpoint in the staggered tree, it is possible to change its properties, that is, to be removed or moved into the phase subgraph.

1. When the X endpoint is in the staggered tree, L[X] + L[y] decreases, so it is possible to enter.

2. When Y endpoints are on staggered trees, L[x] + L[Y] increases, so deletion is possible.

* This paper only remembers the operation process of the algorithm, for proof see “Graph Theory and Algorithm”, “Graph Theory and Network Flow Theory” and other related books. Please point out any errors.