Гипотеза Ловаса о гамильтоновом цикле

Гипотеза Ловаса о гамильтоновом цикле — классическая гипотеза в теории графов.

Гамильтонов путь в графе Кэли симметрической группы.

Сформулирована в четвёртом томе «Искусства программирования», но, скорее всего, была известна гораздо раньше.

ФормулировкаПравить

Каждый конечный связный вершинно-транзитивный граф содержит гамильтонов путь.

Вариации и обобщенияПравить

• Любой конечный связный вершинно-транзитивный граф, кроме пяти исключений, содержит гамильтонов цикл; исключения составляют:
  • Полный граф $K_2$$K_{2}$ ,
  • Граф Петерсена и граф, полученный из него заменой каждой вершины на треугольник,
  • Граф Коксетера и граф, полученный из него заменой каждой вершины на треугольник.

•  

  Полный граф $K_2$$K_{2}$ .

•  

  Граф Петерсена.

•  

  Граф Коксетера.

Ни одно из пяти исключений не является графом Кэли. Это наблюдение приводит к более слабой версии гипотезы

• Любой граф Кэли конечной группы содержит гамильтонов цикл.

Для ориентированных графов Кэли гипотеза не верна.

Частные случаиПравить

• Известно, что ориентированный граф Кэли абелевой группы имеет гамильтонов путь.
  • С другой стороны, циклические группы, порядок которых не является степенью простого числа, допускают ориентированный граф Кэли без гамильтонова цикла.
• В 1986 году Д. Витте доказал, что гипотеза верна для графов Кэли p-групп.
• Вопрос остаётся открытым для диэдральных групп.

Известно, что для симметрической группы гипотеза верна для следующих наборов образующих:

• $a=(1,2,\dots <!--\; \dots \; -->,n),b=(1,2)$$a=(1,2,\dots ,n),b=(1,2)$  (длинный цикл и транспозиция).
• $s_1=(1,2),s_2=(2,3),\dots <!--\; \dots \; -->,s_{n-<!--\; -\; -->1}=(n-<!--\; -\; -->1,n)$$s_{1}=(1,2),s_{2}=(2,3),\dots ,s_{n-1}=(n-1,n)$  (образующие Кокстера). В этом случае гамильтонов цикл строится алгоритмом Штайнхаусa — Джонсона — Троттера^[en].
• $a=(1,2),b=(1,2)(3,4)\cdots <!--\; \cdots \; -->,c=(2,3)(4,5)\cdots <!--\; \cdots \; -->$$a=(1,2),b=(1,2)(3,4)\cdots ,c=(2,3)(4,5)\cdots$ .