Задача
COM-B2-M08-P018 Критерий максимального паросочетания
Докажите, что паросочетание максимально по размеру тогда и только тогда, когда относительно него нет увеличивающего пути.
Если есть большее паросочетание, рассмотрите симметрическую разность двух паросочетаний.
Если увеличивающий путь есть, то размер паросочетания можно увеличить, значит, оно не максимально.
Обратно, пусть существует паросочетание \(M'\) большего размера, чем \(M\). Рассмотрим граф, состоящий из рёбер, которые входят ровно в одно из \(M\) и \(M'\). В этом графе степени вершин не превосходят \(2\), поэтому его компоненты — пути и циклы, где рёбра из \(M\) и \(M'\) чередуются.
Так как \(|M'|>|M|\), в какой-то компоненте рёбер из \(M'\) больше, чем рёбер из \(M\). Цикл имеет поровну рёбер обоих типов, значит, это путь. Он начинается и заканчивается рёбрами из \(M'\), а его концы не покрыты \(M\). Следовательно, это увеличивающий путь относительно \(M\). Противоречие отсутствию увеличивающих путей.
Сильная задача уровня 5; важна для алгоритмического мышления.