Задача
COM-B2-M08-P017 Максимальность и увеличивающий путь
#17
★★★★☆ Уровень 4 из 5
Докажите: если относительно паросочетания существует увеличивающий путь, то паросочетание не является максимальным по размеру.
Переключите рёбра вдоль пути.
По определению увеличивающий путь начинается и заканчивается непокрытыми вершинами, а рёбра на нём чередуются. Переключение статуса рёбер вдоль пути сохраняет свойство быть паросочетанием и добавляет на одно ребро больше, чем удаляет. Значит, размер паросочетания увеличивается на \(1\). Следовательно, исходное паросочетание не было максимальным по размеру.
Одна сторона augmenting path theorem.