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

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

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

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

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

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