Гамильтонов путь в графе Кэли симметрической группы.
Гипотеза Ловаса о гамильтоновом цикле
? классическая гипотеза в теории графов.
Сформулирована в четвёртом томе ≪
Искусства программирования
≫, но, скорее всего, была известна гораздо раньше.
Каждый конечный связный
вершинно-транзитивный граф
содержит
гамильтонов путь
.
-
Полный граф
![{\displaystyle K_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/57e1b324cf5b68f2729a8634ff76e396b634b75d)
.
-
Граф Петерсена.
-
Граф Коксетера.
Ни одно из пяти исключений не является
графом Кэли
.
Это наблюдение приводит к более слабой версии гипотезы
Для ориентированных графов Кэли гипотеза не верна.
- Известно, что ориентированный граф Кэли
абелевой группы
имеет гамильтонов путь.
- С другой стороны, циклические группы, порядок которых не является степенью простого числа, допускают ориентированный граф Кэли без гамильтонова цикла.
[1]
- В 1986 году Д. Витте доказал, что гипотеза верна для графов Кэли
p-групп
.
- Вопрос остаётся открытым для
диэдральных групп
.
Известно, что для
симметрической группы
гипотеза верна для следующих наборов образующих:
(длинный цикл и
транспозиция
).
(
образующие Кокстера
). В этом случае гамильтонов цикл строится
алгоритмом Штайнхаусa ? Джонсона ? Троттера
[англ.]
.
.