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