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

При положительных m,n когда у полного двудольного K(m,n) есть гамильтонов путь и когда цикл?

Quant ResearchУровень: ПрактикаAlternating path constraint

При положительных m,n когда у полного двудольного K_(m,n) есть гамильтонов путь и когда цикл?

Подсказки
  • Выпишите чередование долей вдоль пути.
  • Для цикла баланс долей должен совпадать.

Ответ

Путь чередует доли, поэтому |m-n|≤1; полнота делает условие достаточным. Для цикла нужны равные доли m=n≥2. При m=n=1 есть путь-ребро, но нет простого цикла.

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

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