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

Почему любое вершинное покрытие не меньше любого паросочетания? Всегда ли минимальный и максимальный размеры равны?

Quant ResearchУровень: ПродвинутыйDual combinatorial bounds

Почему любое вершинное покрытие не меньше любого паросочетания? Всегда ли минимальный и максимальный размеры равны?

Подсказки
  • Используйте непересечение рёбер.
  • Проверьте равенство на минимальном нечётном цикле.

Ответ

Этот ответ — часть менторства

К продвинутым вопросам есть полный разбор и тренировочное собеседование с практикующим квант-ресерчером. Первый созвон бесплатный.

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

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