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

К паросочетанию нельзя просто добавить свободное ребро. Обязательно ли оно максимального размера? Приведите…

Quant ResearchУровень: ПрактикаGreedy matching trap

К паросочетанию нельзя просто добавить свободное ребро. Обязательно ли оно максимального размера? Приведите контрпример на пути.

Подсказки
  • Возьмите среднее ребро пути из четырёх вершин.
  • Разрешите заменять рёбра, а не только добавлять.

Ответ

Нет: на пути 1-2-3-4 выберите 2-3. Добавить ребро нельзя, но пара 1-2 и 3-4 имеет размер два. Не расширяемое добавлением паросочетание не обязательно наибольшее.

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

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