Га мільтонів ро зклад заданого графа це розбиття ребер графа на гамільтонові цикли Гамільтонові розкладм вивчалися як дл

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

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

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

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

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

Див. також

Лінійна деревність — інший вид обмеженого розбиття на підграфи з найбільшим степенем 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.

[b-1] 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.

[a-2] Brian Alspach. The wonderful Walecki construction // Bulletin of the Institute of Combinatorics and its Applications. — 2008. — Т. 52. — С. 7–20.

[ko-3] 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-4] 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.