Русская Википедия:Гипотеза Ловаса о гамильтоновом цикле
Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску
Гипотеза Ловаса о гамильтоновом цикле — классическая гипотеза в теории графов.
Сформулирована в четвёртом томе «Искусства программирования», но, скорее всего, была известна гораздо раньше.
Формулировка
Каждый конечный связный вершинно-транзитивный граф содержит гамильтонов путь.
Вариации и обобщения
- Любой конечный связный вершинно-транзитивный граф, кроме пяти исключений, содержит гамильтонов цикл; исключения составляют:
- Полный граф <math>K_2</math>,
- Граф Петерсена и граф, полученный из него заменой каждой вершины на треугольник,
- Граф Коксетера и граф, полученный из него заменой каждой вершины на треугольник.
-
Полный граф <math>K_2</math>.
-
Граф Петерсена.
-
Граф Коксетера.
Ни одно из пяти исключений не является графом Кэли. Это наблюдение приводит к более слабой версии гипотезы
- Любой граф Кэли конечной группы содержит гамильтонов цикл.
Для ориентированных графов Кэли гипотеза не верна.
Частные случаи
- Известно, что ориентированный граф Кэли абелевой группы имеет гамильтонов путь.
- С другой стороны, циклические группы, порядок которых не является степенью простого числа, допускают ориентированный граф Кэли без гамильтонова цикла.[1]
- В 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>.
Ссылки
Категории:
- Страницы с неработающими файловыми ссылками
- Русская Википедия
- Алгебраическая теория графов
- Математические гипотезы
- Конечные группы
- Теория графов
- Теория групп
- Гамильтоновы пути и циклы
- Страницы, где используется шаблон "Навигационная таблица/Телепорт"
- Страницы с телепортом
- Википедия
- Статья из Википедии
- Статья из Русской Википедии