WikiDer > Гипотеза Ловаса - Википедия

В теория графов, то Гипотеза Ловаса (1969) - классическая проблема Гамильтоновы пути в графиках. Он говорит:

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

Изначально Ласло Ловас поставил проблему наоборот, но эта версия стала стандартной. В 1996 г. Ласло Бабай опубликовал гипотезу, резко противоречащую этой гипотезе,^[1] но обе гипотезы остаются широко открытыми. Неизвестно даже, контрпример обязательно приведет к серии контрпримеров.

Исторические заметки

Проблема поиска гамильтоновых путей в высокосимметричных графах довольно старая. В качестве Дональд Кнут описывает это в томе 4 Искусство программирования,^[2] проблема возникла в Британский кампанология (колокольный звон). Такие гамильтоновы пути и циклы также тесно связаны с Коды Грея. В каждом случае конструкции явные.

Варианты гипотезы Ловаса

Гамильтонов цикл

Другая версия Гипотеза Ловаса утверждает, что

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

Есть 5 известных примеров вершинно-транзитивных графов без гамильтоновых циклов (но с гамильтоновыми путями): полный график ${ displaystyle K_ {2}}$, то Граф Петерсена, то Граф Кокстера и два графа, полученные из графов Петерсена и Кокстера путем замены каждой вершины треугольником.^[3]

Графики Кэли

Ни один из 5 вершинно-транзитивных графов без гамильтоновых циклов не является графом Кэли. Это наблюдение приводит к более слабой версии гипотезы:

Каждая конечная связная Граф Кэли содержит гамильтонов цикл.

Преимущество формулировки графа Кэли состоит в том, что такие графики соответствуют конечная группа ${ displaystyle G}$ игенераторная установка ${ displaystyle S}$. Таким образом, можно спросить, какой ${ displaystyle G}$ и ${ displaystyle S}$ гипотеза верна, а не критикует ее в целом.

Направленный граф Кэли

Для ориентированных графов Кэли (орграфов) гипотеза Ловаса неверна. Различные контрпримеры были получены Роберт Александр Ранкин. Тем не менее, многие из приведенных ниже результатов остаются в силе при такой ограничительной настройке.

Особые случаи

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

Каждый ориентированный граф Кэли абелева группа имеет гамильтонов путь; однако каждая циклическая группа, порядок которой не является степенью простого числа, имеет ориентированный граф Кэли, не имеющий гамильтонова цикла.^[4]В 1986 г. Д. Витте доказал, что гипотеза Ловаса верна для графов Кэли p-группы. Он открыт даже для диэдральные группы, хотя для специальных комплектов генераторов был достигнут некоторый прогресс.

Когда группа ${ displaystyle G = S_ {n}}$ это симметричная группа, есть много привлекательных генераторных установок. Например, гипотеза Ловаса верна в следующих случаях порождающих множеств:

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

Стонг показал, что гипотеза верна для графа Кэли венок Z_м писатьZ_п с естественным минимальным порождающим множеством, когда м либо четное, либо три. В частности, это верно для кубические циклы, который может быть сгенерирован как граф Кэли сплетения Z₂ писатьZ_п.^[5]

Общие группы

Для общих конечных групп известно лишь несколько результатов:

• ${ Displaystyle S = {a, b }, (ab) ^ {2} = 1}$ (Ранкин генераторы)
• ${ Displaystyle S = {a, b, c }, a ^ {2} = b ^ {2} = c ^ {2} = [a, b] = 1}$ (Рапапорт-Штрассер генераторы)
• ${ Displaystyle S = {a, b, c }, a ^ {2} = 1, c = a ^ {- 1} ba}$ (Пак–Радойчич генераторы^[6])
• ${ Displaystyle S = {a, b }, a ^ {2} = b ^ {s} = (ab) ^ {3} = 1,}$ куда ${ Displaystyle | G |, s = 2 ~ mod ~ 4}$ (здесь имеем (2, s, 3) -презентация, Теорема Гловера – Марушича^[7]).

Наконец, известно, что для любой конечной группы ${ displaystyle G}$ существует генераторный набор размером не более ${ displaystyle log _ {2} | G |}$ такой, что соответствующий граф Кэли является гамильтоновым (Пак-Радойчич). Этот результат основан на классификация конечных простых групп.

Гипотеза Ловаса была также установлена ​​для случайных порождающих множеств размера ${ Displaystyle Omega ( log ^ {5} | G |)}$.^[8]

Рекомендации