 Гамільтонів розклад Валецького повного графа 
Га́мільтонів ро́зклад заданого графа — це розбиття ребер графа на гамільтонові цикли. Гамільтонові розкладм вивчалися як для неорієнтованих графів, так і для орієнтованих графів. У разі неорієнтованого графа гамільтонів розклад можна описати як 2-факторизацію графа, таку, що кожен фактор зв'язний. Щоб такий розклад існував для неорієнтованого графа, він має бути зв'язним регулярним графом із парним степенем. Орієнтований граф з таким розкладом має бути сильно зв'язним і всі вершини повинні мати однакові півстепені входу і виходу, але ці степені не мають бути парними.

Відомо, що будь-який повний граф з непарним числом вершин  має гамільтонів розклад. Цей результат, що є окремим випадком задачі Обервольфаха про розкладання повних графів на ізоморфні 2-фактори, Едуард Люка у 1892 приписував Валецькі. Побудова Валецькі поміщає  вершин у правильний многокутник і покриває повний граф на цій підмножині вершин  гамільтоновими шляхами, що йдуть зигзагом через многокутник із поворотом кожного шляху на кратний  кут. Шляхи можна потім доповнити до гамільтонових циклів, з'єднавши їхні кінців через вершину, що залишилася.

Орієнтовані випадки повних графів — це турніри. Відповідаючи на гіпотезу Келлі 1968, Даніела Кюн і Дірік Остус довели 2012 року, що будь-який досить великий регулярний турнір має гамільтонів розклад.

Перевірка, чи має довільний граф гамільтонів розклад, є NP-повною задачею як для орієнтованих, так і неорієнтованих графів.

Примітки



