- 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.
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
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.