Гамільтонів розклад

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

Гамільтонів розклад Валецького повного графа ${\displaystyle K_{9}}$

Відомо, що будь-який повний граф з непарним числом вершин ${\displaystyle n}$ має гамільтонів розклад. Цей результат, що є окремим випадком задачі Обервольфаха про розкладання повних графів на ізоморфні 2-фактори, Едуард Люка у 1892 приписував Валецькі. Побудова Валецькі поміщає ${\displaystyle n-1}$ вершин у правильний многокутник і покриває повний граф на цій підмножині вершин ${\displaystyle (n-1)/2}$ гамільтоновими шляхами, що йдуть зигзагом через многокутник із поворотом кожного шляху на кратний ${\displaystyle \pi /(n-1)}$ кут. Шляхи можна потім доповнити до гамільтонових циклів, з'єднавши їхні кінців через вершину, що залишилася^[2].

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

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

Див. також

• Гіпогамільтонів граф
• Лінійна деревність — інший вид обмеженого розбиття на підграфи з найбільшим степенем 2