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

Перейти к навигации Перейти к поиску

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

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

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

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

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

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

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

Полный граф $K_{2}$ .
Граф Петерсена.
Граф Коксетера.

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

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

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

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

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

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

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

Ссылки

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

Похожие исследовательские статьи

Тео́рия гра́фов — раздел дискретной математики, изучающий графы, одна из ветвей топологии. В самом общем смысле граф — это множество точек, которые соединяются множеством линий. Теория графов включена в учебные программы для начинающих математиков, поскольку:

как и геометрия, обладает наглядностью;
как и теория чисел, проста в объяснении и имеет сложные нерешённые задачи;
не имеет громоздкого математического аппарата ;
имеет выраженный прикладной характер.

Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре.

Гамильтонов граф — граф, содержащий гамильтонов цикл. При этом гамильтоновым циклом является такой цикл, который проходит через каждую вершину данного графа ровно по одному разу; то есть простой цикл, в который входят все вершины графа.

По́лный граф — простой неориентированный граф, в котором каждая пара различных вершин смежна. Полный граф с $\text{[math]}$ вершинами имеет $\text{[math]}$ рёбер и обозначается $\text{[math]}$ . Является регулярным графом степени $\text{[math]}$ .

Граф Петерсена — неориентированный граф с 10 вершинами и 15 рёбрами; достаточно простой граф, используемый в качестве примера и контрпримера для многих задач в теории графов.

В теории графов вершинно-транзитивным графом называется граф G такой, что для любых двух вершин v₁ и v₂ графа G существует автоморфизм

\text{[math]}

В теории графов под графом Клебша понимается один из двух дополняющих друг друга графов, имеющих 16 вершин. Один из них имеет 40 рёбер и является 5-регулярным графом, другой имеет 80 рёбер и является 10-регулярным графом. 80-рёберный вариант — это половинный граф куба 5-го порядка. Назван графом Клебша в 1968 году Зайделем ввиду его связи с конфигурацией прямых поверхности четвёртого порядка, открытой 1868 году немецким математиком Альфредом Клебшем. 40-рёберный вариант – это складной граф куба 5 порядка. Он известен также под именем граф Гринвуда — Глизона после работы Гринвуда и Глизона, в которой они использовали этот граф для вычисления числа Рамсея R (3,3,3) = 17 .

<span class="mw-page-title-main">Турнир (теория графов)</span> ориентированный граф, полученный из неориентированного полного графа путём назначения направления каждому ребру

Турнир — это ориентированный граф, полученный из неориентированного полного графа путём назначения направления каждому ребру. Таким образом, турнир — это орграф, в котором каждая пара вершин соединена одной направленной дугой.

В теории графов нечётные графы O_n — это семейство симметричных графов с высоким нечётным обхватом, определённых на некоторых семействах множеств. Они включают и обобщают графы Петерсена.

<span class="mw-page-title-main">Дистанционно-транзитивный граф</span> такой граф, что для любых двух заданных вершин v и w, находящихся на расстоянии i, и любых двух вершин x и y, находящихся на том же расстоянии, су

Дистанционно-транзитивный граф — граф, в котором любая упорядоченная пара вершин переводится в любую другую упорядоченную пару вершин с тем же расстоянием между вершинами одним из автоморфизмов графа.

<span class="mw-page-title-main">Граф Дезарга</span> дистанционно-транзитивный кубический граф с 20 вершинами и 30 рёбрами

Граф Дезарга — дистанционно-транзитивный кубический граф с 20 вершинами и 30 рёбрами. Назван в честь Жерара Дезарга. Возникает в некоторых комбинаторных построениях, имеет высокую степень симметрии, это единственный известный непланарный кубический частичный куб и применяется в химических базах данных.

<span class="mw-page-title-main">Граф гиперкуба</span> регулярный граф с 2^n вершинами, 2^(n−1)n рёбрами и n рёбрами, сходящимися в одной вершине

В теории графов графом гиперкуба Q_n называется регулярный граф с 2ⁿ вершинами, 2ⁿ⁻¹n рёбрами и n рёбрами, сходящимися в одной вершине. Его можно получить как одномерный скелет геометрического гиперкуба. Например, Q₃ — это граф, образованный 8 вершинами и 12 рёбрами трёхмерного куба. Граф можно получить другим образом, отталкиваясь от семейства подмножеств множества с n элементами путём использования в качестве вершин все подмножества и соединением двух вершин ребром, если соответствующие множества отличаются только одним элементом.

Обобщённые графы Петерсена — семейство кубических графов, образованное соединением вершин правильного многоугольника с соответствующими вершинами звезды. В семейство входит граф Петерсена и обобщает один из путей построения графа Петерсена. Семейство обобщённых графов Петерсена ввёл в рассмотрение в 1950 году Коксетер и этим графам дал имя в 1969 году Марк Воткинс.

Куби́ческий граф — граф, в котором все вершины имеют степень три. Другими словами, кубический граф является 3-регулярным. Кубические графы называются также тривалентными.

Граф Коксетера — 3-регулярный граф с 28 вершинами и 42 рёбрам Все кубические дистанционно-регулярные графы известны, граф Коксетера — один из 13-ти таких графов.

В теории графов граф Науру — это симметричный двудольный кубический граф с 24 вершинами и 36 рёбрами. Граф был назван Дэвидом Эпштейном по аналогии с двенадцатилучевой звездой на флаге Науру.

Панциклический граф — ориентированный или неориентированный граф, который содержит циклы всех возможных длин от трёх до числа вершин графа. Панциклические графы являются обобщением гамильтоновых графов, графов, которые имеют циклы максимальной возможной длины.

Теорема Фляйшнера — утверждение в теории графов, дающее достаточное условие, чтобы граф содержал гамильтонов цикл: если граф $\text{[math]}$ является вершинно 2-связным графом, то квадрат графа $\text{[math]}$ гамильтонов. Названа именем Герберта Фляйшнера, опубликовавшего доказательство теоремы в 1974 году.

Гипотеза Барнетта — нерешённый вопрос в теории графов о существовании гамильтоновых циклов в графах. Гипотеза названа именем Дэвида В. Барнетта, эмерита калифорнийского университета в Дейвисе. Гипотеза утверждает, что любой двудольный граф многогранника с тремя рёбрами в каждой вершине имеет гамильтонов цикл.

Задача о гамильтоновом пути и задача о гамильтоновом цикле — это задачи определения, существует ли гамильтонов путь или гамильтонов цикл в заданном графе. Обе задачи NP-полны.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.