Interested Article - Гипотеза Ловаса о гамильтоновом цикле
megan
- 2021-08-18
- 1
Гипотеза Ловаса о гамильтоновом цикле — классическая гипотеза в теории графов.
Сформулирована в четвёртом томе « Искусства программирования », но, скорее всего, была известна гораздо раньше.
Формулировка
Каждый конечный связный вершинно-транзитивный граф содержит гамильтонов путь .
Вариации и обобщения
-
Любой конечный связный
вершинно-транзитивный граф
, кроме пяти исключений, содержит
гамильтонов цикл
; исключения составляют:
- Полный граф ,
- Граф Петерсена и граф, полученный из него заменой каждой вершины на треугольник,
- Граф Коксетера и граф, полученный из него заменой каждой вершины на треугольник.
-
Полный граф .
-
Граф Петерсена.
-
Граф Коксетера.
Ни одно из пяти исключений не является графом Кэли . Это наблюдение приводит к более слабой версии гипотезы
- Любой граф Кэли конечной группы содержит гамильтонов цикл .
Для ориентированных графов Кэли гипотеза не верна.
Частные случаи
-
Известно, что ориентированный граф Кэли
абелевой группы
имеет гамильтонов путь.
- С другой стороны, циклические группы, порядок которых не является степенью простого числа, допускают ориентированный граф Кэли без гамильтонова цикла.
- В 1986 году Д. Витте доказал, что гипотеза верна для графов Кэли p-групп .
- Вопрос остаётся открытым для диэдральных групп .
Известно, что для симметрической группы гипотеза верна для следующих наборов образующих:
- (длинный цикл и транспозиция ).
- ( образующие Кокстера ). В этом случае гамильтонов цикл строится .
- .
Ссылки
megan
- 2021-08-18
- 1