Berge's lemma¶
Berge's lemma is an important theory of maximum matching.
- Alternating path: a path that begins with an unmatched vertex and whose edges belong alternately to the matching and not to the matching.
- Augmenting path: an alternating path that starts from and ends on free (unmatched) vertices.
The number of unmatched edges on an augmenting path is one more than the number of matched edges. If the matched edges are changed to unmatched edges, or vice versa, the matching size will increase by one and still be an alternating path.
As shown in the figure, the number of matches increases from 2 to 3 - we call this augmentation.
According to Berge's lemma, the maximum matching is found when there's no augmenting path.
From this theorem, we can understand the core idea of maximum matching.
Core
Enumerate all unmatched vertices and find the augmenting path until there's no one to be found.
In fact, we only need to enumerate once for each vertex.
Suppose that after a round of augmentation along the augmenting path , there's an augmenting path starting from , then must intersect .
Suppose intersects for the first time. Remebering that is an alternating path, which means that the intersection points are of different types (marked by red and blue in the figure), then can reach an unmatched vertex in before the augmentation, which indicates that there already exists an augmenting path starting from .
buildLast update and/or translate time of this article，Check the history
editFound smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github
peopleContributor of this article accelsao
translateTranslator of this article Visit the original article!
copyrightThe article is available under CC BY-SA 4.0 & SATA ; additional terms may apply.