К паросочетанию нельзя просто добавить свободное ребро. Обязательно ли оно максимального размера? Приведите…
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