К содержанию
Quantoros

Путь чередует свободные и выбранные рёбра, а его концы не покрыты паросочетанием. Почему смена принадлежности всех…

Quant ResearchУровень: ПрактикаAugmenting paths

Путь чередует свободные и выбранные рёбра, а его концы не покрыты паросочетанием. Почему смена принадлежности всех рёбер увеличивает размер ровно на один?

Подсказки
  • Посчитайте типы рёбер чередующегося пути.
  • Отдельно проверьте внутренние вершины и концы.

Ответ

Свободных рёбер на одно больше. Внутренние вершины теряют одно выбранное и получают одно, концы получают по одному. Условие паросочетания сохраняется, размер растёт на единицу.

Источник и лицензия: Oscar Levin — Discrete Mathematics: An Open Introduction, 3rd edition · CC-BY-SA-4.0 · ответ: редакция Quantoros · перевод: Quantoros

Похожие вопросы