What is the Hungarian algorithm and what is Hall's theorem?

The Hungarian algorithm naturally cannot avoid Hall's theorem, which is: for a two-part graph G, there exists a matching M, so that all the vertices of X are saturated with respect to M. The sufficient condition is that for any subset A of X, the set of points neighboring A is T(A), which is constant: │T(A)│ >= │A│

The Hungarian algorithm is based on the idea of the Hall theorem of the proof of the sufficiency. The basic steps are:

1. Any given initial matching M;

2. If X is saturated then end, otherwise proceed to step 3;

3. Find a non-saturated vertex x0 in X as V1 ← {x0}, V2 ← Φ;

4. If T(V1) = V2 then stop because of unmatched, otherwise pick any point y ∈ T( V1)\V2;

5. If y is saturated then go to 6, otherwise make an augmentable path P from x0 → y, M ← M?E(P), go to 2;

6. Since y is saturated, there is an edge (y,z) in M, make V1 ← V1 ∪ {z}, V2 ← V2 ∪ {y}, go to 4;

Let the array up[1..n] --- Label the points in the upper half of the bipartite graph.

down[1..n] --- Mark the points in the lower half of the bipartite graph.

map[1..n, 1..n] --- Indicates the relationship between the points in the upper and lower parts of the bisecting map.

True - connected, false - not connected.

over1[1..n], over2[1..n] mark the covered points of the upper and lower parts.

use[1..n, 1..n] - Indicates whether the edge is covered or not .

First process the read-in data , for an edge (x, y), the start point goes into the set up and the end point goes into the set down. Mark the corresponding element in map as true.

1. Find an uncovered point in up .

2. From the uncovered point, search for a feasible route that starts at a thin edge, ends at a thin edge, and intersects the thin and thick edges.

3. If found, modify the elements of over1, over2, and use corresponding to the points on the route. Repeat step 1.

4. Count the number of covered edges in use, total, and subtract total from total.