При каких n≥2 можно пройти каждое ребро полного графа Kn ровно раз и вернуться в начало?
Quant ResearchУровень: ПрактикаEuler tour feasibility
При каких n≥2 можно пройти каждое ребро полного графа K_n ровно раз и вернуться в начало?
Подсказки
- Вход и выход используют рёбра попарно.
- Подставьте степень вершины полного графа.
Ответ
Ровно при нечётных n. Граф связен, степень каждой вершины n-1. Для эйлерова цикла все степени должны быть чётными; в связном графе этого достаточно.
Источник и лицензия: Oscar Levin — Discrete Mathematics: An Open Introduction, 3rd edition · CC-BY-SA-4.0 · ответ: редакция Quantoros · перевод: Quantoros