Гипотеза Ловаса о гамильтоновом цикле
Перейти к навигации
Перейти к поиску
Гипотеза Ловаса о гамильтоновом цикле — классическая гипотеза в теории графов.
Сформулирована в четвёртом томе «Искусства программирования», но, скорее всего, была известна гораздо раньше.
Формулировка
[править | править код]Каждый конечный связный вершинно-транзитивный граф содержит гамильтонов путь.
Вариации и обобщения
[править | править код]- Любой конечный связный вершинно-транзитивный граф, кроме пяти исключений, содержит гамильтонов цикл; исключения составляют:
- Полный граф ,
- Граф Петерсена и граф, полученный из него заменой каждой вершины на треугольник,
- Граф Коксетера и граф, полученный из него заменой каждой вершины на треугольник.
-
Полный граф .
-
Граф Петерсена.
-
Граф Коксетера.
Ни одно из пяти исключений не является графом Кэли. Это наблюдение приводит к более слабой версии гипотезы
- Любой граф Кэли конечной группы содержит гамильтонов цикл.
Для ориентированных графов Кэли гипотеза не верна.
Частные случаи
[править | править код]- Известно, что ориентированный граф Кэли абелевой группы имеет гамильтонов путь.
- С другой стороны, циклические группы, порядок которых не является степенью простого числа, допускают ориентированный граф Кэли без гамильтонова цикла.[1]
- В 1986 году Д. Витте доказал, что гипотеза верна для графов Кэли p-групп.
- Вопрос остаётся открытым для диэдральных групп.
Известно, что для симметрической группы гипотеза верна для следующих наборов образующих:
- (длинный цикл и транспозиция).
- (образующие Кокстера). В этом случае гамильтонов цикл строится алгоритмом Штайнхаусa — Джонсона — Троттера[англ.].
- .
Ссылки
[править | править код]- ↑ Holsztyński, W.; Strube, R. F. E. (1978), "Paths and circuits in finite groups", Discrete Mathematics, 22 (3): 263—272, doi:10.1016/0012-365X(78)90059-6, MR 0522721.