Graph Theory37 sections · 1633 units
Open in Course

Augmenting Paths

Alternating matched and unm...

An augmenting path is a path from an unmatched vertex in LL to an unmatched vertex in RR that alternates between non-matching and matching edges. Why does this matter?

If you find an augmenting path, you can flip the edges (matched becomes unmatched, unmatched becomes matched) and increase your matching size by 11. This is the core idea behind all matching algorithms. Keep finding augmenting paths until none exist.