Введение
Проблема в теории графов
В теории графов, гипотеза Ловаса (1969) — это классическая задача о гамильтоновых путях в графах. Она утверждает:
Любой конечный связный вершинно-транзитивный граф содержит гамильтонов путь. Изначально Ласло Ловас сформулировал проблему в обратном виде, но эта версия стала стандартной. В 1996 году Ласло Бабаи опубликовал гипотезу, резко противоречащую данной гипотезе, однако обе гипотезы остаются широко нерешенными. Даже не известно, приведет ли единственный контрпример к последовательности контрпримеров.
In graph theory, the Lovász conjecture (1969) is a classical problem on Hamiltonian paths in graphs. It says:
Every finite connected vertex transitive graph contains a Hamiltonian path. Originally László Lovász stated the problem in the opposite way, but
this version became standard. In 1996, László Babai published a conjecture sharply contradicting this conjecture, but both conjectures remain widely open. It is not even known if a single counterexample would necessarily lead to a series of counterexamples.
Исторические замечания
Проблема поиска гамильтоновых путей в сильносимметричных графах достаточно стара. Как описывает Дональд Кнут в 4-м томе "Искусства программирования", эта проблема возникла в британском колокольном звоне (кампанологии). Такие гамильтоновы пути и циклы также тесно связаны с кодами Грея. Во всех случаях построения являются явными.
График Кайли с направлением
Для ориентированных графов Кейли (диграфов) гипотеза Ловаса не верна. Различные контрпримеры были получены Робертом Александром Рэнкином. Однако, многие из нижеприведенных результатов остаются справедливыми и в этой ограниченной постановке.
Особые случаи
Каждый направленный граф Кейли абелевой группы имеет гамильтонов путь; однако, каждая циклическая группа, порядок которой не является степенью простого числа, имеет направленный граф Кейли, не имеющий гамильтонов цикл. В 1986 году Д. Витте доказал, что гипотеза Ловаса выполняется для графов Кейли p-групп. Она остаётся открытой даже для диэдрических групп, хотя для специальных наборов генераторов был достигнут определённый прогресс. Когда группа является симметрической группой, существует множество привлекательных генерирующих множеств. Например, гипотеза Ловаса выполняется в следующих случаях генерации множеств: (длинный цикл и транспозиция), (генераторы Коксетера). В этом случае гамильтонов цикл генерируется алгоритмом Стейнхауса — Джонсона — Троттера, а также любым набором транспозиций, соответствующих помеченному дереву на . Стронг показал, что гипотеза выполняется для графа Кейли венка произведений Zm wr Zn с естественным минимальным генерирующим множеством, когда m чётно или равно трём. В частности, это относится к кубически связанным циклам, которые могут быть сгенерированы как граф Кейли венка произведений Z2 wr Zn.
(long cycle and a transposition). (Coxeter generators). In this case a Hamiltonian cycle is generated by the Steinhaus–Johnson–Trotter algorithm. any set of transpositions corresponding to a labelled tree on
Stong has shown that the conjecture holds for the Cayley graph of the wreath product Zm wr Zn with the natural minimal generating set when m is either even or three. In particular this holds for the cube connected cycles, which can be generated as the Cayley graph of the wreath product Z2 wr Zn.