Задача
COM-B2-M08-P010 Увеличивающий путь
#10
★★★☆☆ Уровень 3 из 5
Пусть относительно паросочетания найден путь, который начинается и заканчивается непокрытыми вершинами, а его рёбра чередуются: не выбранное, выбранное, не выбранное и так далее. Докажите, что размер паросочетания можно увеличить на \(1\).
Поменяйте статус всех рёбер пути.
Удалим из паросочетания выбранные рёбра этого пути и добавим невыбранные рёбра пути. Так как путь чередуется, общих концов у новых выбранных рёбер не появится.
Путь начинается и заканчивается непокрытыми вершинами, поэтому невыбранных рёбер на пути на одно больше, чем выбранных. Следовательно, размер паросочетания увеличится на \(1\).
Подготовка к критерию максимальности.