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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Гамильтонов путь в графе Кэли симметрической группы.

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

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

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

[править | править код]

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

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

[править | править код]

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

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

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

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

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

  1. 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.