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

Гамильтоново разложение заданного графа — это

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

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

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

У этой статьи есть несколько проблем, помогите их исправить: Необходимо проверить качество перевода c неуказанного языка, исправить содержательные и стилистические ошибки. Вы можете помочь улучшить эту статью (см. также рекомендации по переводу). Оригинал не указан. Пожалуйста, укажите его. (6 мая 2019) Стиль этой статьи неэнциклопедичен или нарушает нормы литературного русского языка. Статью следует исправить согласно стилистическим правилам Википедии. (6 мая 2019) Пожалуйста, после исправления проблемы исключите её из списка параметров. После устранения всех недостатков этот шаблон может быть удалён любым участником.