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

Гамільтонів розклад Валецького повного графа $K_9$

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

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

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

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

Див. також

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