Гамильтоново разложение

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

Гамильтоново разложение заданного графа — это разбиение рёбер графа на гамильтоновы циклы. Гамильтоновы разложения изучались как для неориентированных графов, так и для ориентированных графов. В случае неориентированного графа гамильтоново разложение может быть описано как 2-факторизация графа, такая что каждый фактор связен. Чтобы такое разложение существовало для неориентированного графа, он должен быть связным регулярным графом с чётной степенью. Ориентированный же граф с таким разложением должен быть сильно связен и все вершины должны иметь одинаковые полустепени захода и исхода, но эти степени не обязаны быть чётными[1].

Известно, что любой полный граф с нечётным числом вершин ${\displaystyle n}$ имеет гамильтоново разложение. Этот результат, являющийся специальным случаем задачи Обервольфаха разложения полных графов на изоморфные 2-факторы, Эдуард Люка в 1892 году приписывал Валецки. Построение Валецки помещает ${\displaystyle n-1}$ вершин в правильный многоугольник и покрывает полный граф на этом подмножестве вершин ${\displaystyle (n-1)/2}$ гамильтоновыми путями, идущими зигзагом через многоугольник с поворотом каждого пути на кратный ${\displaystyle \pi /(n-1)}$ угол. Пути могут затем быть дополнены до гамильтоновых циклов путём соединения их концов через оставшуюся вершину[2].

Ориентированные случай полных графов — это турниры. Отвечая на гипотезу Келли 1968 года, Даниэла Кюн и Дирик Остус доказали в 2012 году, что любой достаточно большой регулярный турнир имеет гамильтоново разложение[3].

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

Примечания

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.
2. Brian Alspach. The wonderful Walecki construction // Bulletin of the Institute of Combinatorics and its Applications. — 2008. — Т. 52. — С. 7–20.
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. — doi:10.1016/j.aim.2013.01.005. — arXiv:1202.6219.
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.