Путь чередует свободные и выбранные рёбра, а его концы не покрыты паросочетанием. Почему смена принадлежности всех…
Quant ResearchУровень: ПрактикаAugmenting paths
Путь чередует свободные и выбранные рёбра, а его концы не покрыты паросочетанием. Почему смена принадлежности всех рёбер увеличивает размер ровно на один?
Подсказки
- Посчитайте типы рёбер чередующегося пути.
- Отдельно проверьте внутренние вершины и концы.
Ответ
Свободных рёбер на одно больше. Внутренние вершины теряют одно выбранное и получают одно, концы получают по одному. Условие паросочетания сохраняется, размер растёт на единицу.
Источник и лицензия: Oscar Levin — Discrete Mathematics: An Open Introduction, 3rd edition · CC-BY-SA-4.0 · ответ: редакция Quantoros · перевод: Quantoros