Русская Википедия:Гипотеза Ловаса о гамильтоновом цикле

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Файл:Steinhaus-Johnson-Trotter-Permutohedron.svg

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

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

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

Формулировка

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

Вариации и обобщения

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

• Полный граф <math>K_2</math>.

  Полный граф <math>K_2</math>.

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

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

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

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

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

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

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

Частные случаи

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

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

• <math>a = (1,2,\dots,n), b = (1,2)</math> (длинный цикл и транспозиция).
• <math>s_1 = (1,2), s_2 = (2,3), \dots, s_{n-1} = (n-1,n)</math> (образующие Кокстера). В этом случае гамильтонов цикл строится Шаблон:Iw.
• <math>a =(1,2), b = (1,2)(3,4)\cdots, c = (2,3)(4,5)\cdots</math>.