Proof of the correctness of Kuhn's algorithm for finding the maximum matching

Question

Proof of the correctness of Kuhn's algorithm for finding the maximum matching

Many places write that its correctness obviously follows from Berge's theorem. However, it is not clear why, if the increasing chain exists, the algorithm will find it?

6

алгоритм графы

Author: αλεχολυτ, 2013-01-30

Source

1 answers

score 3 · Accepted Answer

If I understand correctly, the idea is this.

Let it be true that there is an increasing chain. Since we iterate over all the starting vertices, we will try to start from the starting vertex of the increasing chain (which, as we assumed, exists). We are essentially iterating through all the alternating chains (in terms of the text from the link @ReinRaus) from this vertex, so that when we iterate, we must get to the same existing chain.