Гипотеза Ловаса о гамильтоновом цикле
? классическая гипотеза в теории графов.
Сформулирована в четвёртом томе ≪
Искусства программирования
≫, но, скорее всего, была известна гораздо раньше.
Каждый конечный связный
вершинно-транзитивный граф
содержит
гамильтонов путь
.
-
Полный граф
.
-
Граф Петерсена.
-
Граф Коксетера.
Ни одно из пяти исключений не является
графом Кэли
.
Это наблюдение приводит к более слабой версии гипотезы
Для ориентированных графов Кэли гипотеза не верна.
- Известно, что ориентированный граф Кэли
абелевой группы
имеет гамильтонов путь.
- С другой стороны, циклические группы, порядок которых не является степенью простого числа, допускают ориентированный граф Кэли без гамильтонова цикла.
[1]
- В 1986 году Д. Витте доказал, что гипотеза верна для графов Кэли
p-групп
.
- Вопрос остаётся открытым для
диэдральных групп
.
Известно, что для
симметрической группы
гипотеза верна для следующих наборов образующих:
- (длинный цикл и
транспозиция
).
- (
образующие Кокстера
). В этом случае гамильтонов цикл строится
алгоритмом Штайнхаусa ? Джонсона ? Троттера
[англ.]
.
- .