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

При каких 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

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