При положительных 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