Hungarian algorithm for the maximum match (assignment problem):
Talking about the Hungarian algorithm naturally avoids the Hall theorem, that is, for the two figures g, there is a matching M so that all vertices of X for M saturation is: for any of the X, any subset A, and A adjacency Point set is T (a), Hengs: | T (a) |> = | A |
The Hungarian algorithm is the idea of adequate proven in the Hall theorem, and its basic steps are:
1. RMB initial match M;
2. If x is saturated, the third step is performed;
3. Find a unsaturated vertex X0 in X, made V1 ← {x0}, V2 ← φ;
4. If T (V1) = V2 is stopped because it cannot match, it will optionally be a little y ∈T (V1) / V2;
5. If Y is saturated, turn to 6, otherwise it will be made from X0 → Y, the increased road P, M ← M⊕e (P), and 2;
6. Since Y is saturated, there is a side (Y, Z) in m, which is V1 ← V1 ∪ {z}, V2 ← V2 ∪ {y}, turn 4;
