Гамільтонів розклад
Га́мільтонів ро́зклад заданого графа — це розбиття ребер графа на гамільтонові цикли. Гамільтонові розкладм вивчалися як для неорієнтованих графів, так і для орієнтованих графів. У разі неорієнтованого графа гамільтонів розклад можна описати як 2-факторизацію графа, таку, що кожен фактор зв'язний. Щоб такий розклад існував для неорієнтованого графа, він має бути зв'язним регулярним графом із парним степенем. Орієнтований граф з таким розкладом має бути сильно зв'язним і всі вершини повинні мати однакові півстепені входу і виходу, але ці степені не мають бути парними[1].
Відомо, що будь-який повний граф з непарним числом вершин має гамільтонів розклад. Цей результат, що є окремим випадком задачі Обервольфаха про розкладання повних графів на ізоморфні 2-фактори, Едуард Люка у 1892 приписував Валецькі. Побудова Валецькі поміщає вершин у правильний многокутник і покриває повний граф на цій підмножині вершин гамільтоновими шляхами, що йдуть зигзагом через многокутник із поворотом кожного шляху на кратний кут. Шляхи можна потім доповнити до гамільтонових циклів, з'єднавши їхні кінців через вершину, що залишилася[2].
Орієнтовані випадки повних графів — це турніри. Відповідаючи на гіпотезу Келлі 1968, Даніела Кюн і Дірік Остус довели 2012 року, що будь-який досить великий регулярний турнір має гамільтонів розклад[3].
Перевірка, чи має довільний граф гамільтонів розклад, є NP-повною задачею як для орієнтованих, так і неорієнтованих графів[4].
Див. також[ред. | ред. код]
- Лінійна деревність — інший вид обмеженого розбиття на підграфи з найбільшим степенем 2
Примітки[ред. | ред. код]
- ↑ Bermond J.-C. Hamiltonian decompositions of graphs, directed graphs and hypergraphs // Annals of Discrete Mathematics. — 1978. — Т. 3. — С. 21–28. — DOI:10.1016/S0167-5060(08)70494-1.
- ↑ Brian Alspach. The wonderful Walecki construction // Bulletin of the Institute of Combinatorics and its Applications. — 2008. — Т. 52. — С. 7–20.
- ↑ Daniela Kühn, Deryk Osthus. Hamilton decompositions of regular expanders: a proof of Kelly's conjecture for large tournaments // Advances in Mathematics. — 2013. — Т. 237. — С. 62–146. — arXiv:1202.6219. — DOI:10.1016/j.aim.2013.01.005.
- ↑ Péroche B. NP-completeness of some problems of partitioning and covering in graphs // Discrete Applied Mathematics. — 1984. — Т. 8, вип. 2. — С. 195–208. — DOI:10.1016/0166-218X(84)90101-X.