В теории графов , то гипотеза Lovász (1969) представляет собой классическая задача о гамильтоновых путях в графах. Он говорит:
- Каждый конечный связный вершинно-транзитивный граф содержит гамильтонов путь .
Первоначально Ласло Ловас формулировал проблему противоположным образом, но эта версия стала стандартной. В 1996 году Ласло Бабай опубликовал гипотезу, резко противоречащую этой гипотезе [1], но обе гипотезы остаются широко открытыми. Неизвестно даже, приведет ли один контрпример к серии контрпримеров.
Исторические заметки
Проблема поиска гамильтоновых путей в высокосимметричных графах довольно старая. Как Дональд Кнут описывает его в томе 4 Искусство программирования для ЭВМ , [2] проблема возникла в британском campanology (колокольный звон). Такие гамильтоновы пути и циклы также тесно связаны с кодами Грея . В каждом случае конструкции явные.
Варианты гипотезы Ловаса
Гамильтонов цикл
Другая версия гипотезы Ловаса утверждает, что
- Каждый конечный связный вершинно-транзитивный граф содержит гамильтонов цикл, за исключением пяти известных контрпримеров.
Есть 5 известных примеров вершинно-транзитивных графов без гамильтоновых циклов (но с гамильтоновыми путями): полный граф , То граф Петерсена , то граф Кокстера и два графика получен из Петерсен и Кокстера графики, заменяя каждую вершину треугольника с. [3]
Графики Кэли
Ни один из 5 вершинно-транзитивных графов без гамильтоновых циклов не является графом Кэли. Это наблюдение приводит к более слабой версии гипотезы:
- Каждый конечный связный граф Кэли содержит гамильтонов цикл .
Преимущество формулировки графа Кэли состоит в том, что такие графы соответствуют конечной группе и генераторная установка . Таким образом, можно спросить, какой а также гипотеза скорее верна, чем атаковать ее в целом.
Направленный граф Кэли
Для ориентированных графов Кэли (орграфов) гипотеза Ловаса неверна. Различные контрпримеры были получены Робертом Александром Ранкиным . Тем не менее, многие из приведенных ниже результатов остаются в силе при такой ограничительной настройке.
Особые случаи
Каждый ориентированный граф Кэли абелевой группы имеет гамильтонов путь; однако каждая циклическая группа, порядок которой не является степенью простого числа, имеет ориентированный граф Кэли, не имеющий гамильтонова цикла. [4] В 1986 г. Д. Витте доказал, что гипотеза Ловаса верна для графов Кэли p-групп . Он открыт даже для диэдральных групп , хотя для специальных наборов образующих был достигнут некоторый прогресс.
Когда группа является симметричной группой , существует множество привлекательных образующих. Например, гипотеза Ловаса верна в следующих случаях порождающих множеств:
- (длинный цикл и транспозиция ).
- ( Генераторы Кокстера ). В этом случае гамильтонов цикл генерируется алгоритмом Штейнхауса – Джонсона – Троттера .
- любой набор транспозиций, соответствующий помеченному дереву на.
Стонг показал, что гипотеза верна для графа Кэли сплетения Z m wr Z n с естественным минимальным порождающим множеством, когда m либо четно, либо равно трем. В частности, это справедливо для кубосвязных циклов , которые могут быть сгенерированы как граф Кэли сплетения Z 2 wr Z n . [5]
Общие группы
Для общих конечных групп известно лишь несколько результатов:
- ( Генераторы Ранкина )
- ( Генераторы Рапапорта – Штрассера )
- ( Генераторы Пак - Радойчича [6] )
- где (здесь (2, s, 3) - представление , теорема Гловера – Марушича). [7]
Наконец, известно, что для любой конечной группы существует генераторный набор размером не более такой, что соответствующий граф Кэли является гамильтоновым (Пак-Радойчич). Этот результат основан на классификации конечных простых групп .
Гипотеза Ловаса была также установлена для случайных порождающих множеств размера . [8]
Рекомендации
- ^ Бабай, Ласло (1996), "Группы автоморфизмов, изоморфизм, реконструкция" , Справочник по комбинаторике , 2 , Elsevier, стр. 1447–1540, ISBN 9780262571715
- ^ Кнут, Дональд Э. (2014), «§7.2.1.2 Генерация всех перестановок», Комбинаторные алгоритмы, часть 1 , Искусство компьютерного программирования , 4A , Addison-Wesley, ISBN 978-0-13-348885-2
- ^ Ройл, Гордон, кубические симметричные графы (перепись Фостера) , заархивировано из оригинала 20 июля 2008 г.
- ^ Holsztyński, W .; Штрубе, РС (1978), "Путь и цепей в конечных группах", дискретная математика , 22 (3): 263-272, DOI : 10.1016 / 0012-365X (78) 90059-6 , МР 0522721.
- ^ Стонг, Ричард (1987), «О гамильтоновых циклах в графах Кэли сплетений», Дискретная математика , 65 (1): 75–80, DOI : 10.1016 / 0012-365X (87) 90212-3 , MR 0891546
- ^ Пак, Игорь ; Radoičić, Rados (2009), "гамильтонова пути в графах Кэли" (PDF) , дискретная математика , 309 (17): 5501-5508, DOI : 10.1016 / j.disc.2009.02.018
- ^ Гловер, Генри H .; Марушич, Драган (2007), «Гамильтоничность кубических графов Кэли», Журнал Европейского математического общества , 9 (4): 775–787, arXiv : math / 0508647 , doi : 10.4171 / JEMS / 96 , MR 2341831
- ^ Кривелевич Михаил ; Судаков, Бенни (2003), «Разреженные псевдослучайные графы являются гамильтоновыми», Journal of Graph Theory , 42 : 17–33, CiteSeerX 10.1.1.24.553 , doi : 10.1002 / jgt.10065