Как правильно гулять по графам Кэли?

Современная математика, к сожалению, изъясняется на языке очень высокого уровня: зачастую чтобы понять, чем же таким интересным занимаются ученые, необходимо уже знать достаточно много. Тем ценнее редкие примеры, которые можно объяснить простыми словами и рассказать при этом про вполне современные вопросы. Одному такому «венгерскому» сюжету и посвящена настоящая заметка.

Вершинно-транзитивные графы

В центре нашего рассказа будут так называемые вершинно-транзитивные графы, т. е. такие, что для любых двух вершин A, B найдется, как говорят, автоморфизм графа, переводящий A в B. Автоморфизмом при этом называют отображение графа в себя, которое переводит соседние вершины (т. е. соединенные ребром) в соседние. Приведем (рис. 1) несколько примеров вершинно-транзитивных графов (направления ребер и их цвета пока стоит игнорировать, их смысл будет пояснен ниже).

Рис. 1

‌

Среди прочих возник вопрос: можно ли в вершинно-транзитивном графе обойти все вершины по ребрам графа, побывав в каждой вершине ровно один раз, и вернуться при этом назад (в случае конечного графа)? Такой обход графа называют «гамильтоновым циклом».

Первое, что приходит на ум, это воспользоваться каким-нибудь условием гамильтоновости. Например, хорошо известной теоремой Оре (cм. [1]), которая состоит в следующем. Для гамильтоновости графа из N вершин достаточно, чтобы сумма степеней (т. е. количество ребер, содержащих эту вершину) любых двух не соединенных ребром вершин была не менее чем N. То есть degA + degB ≥ N.

Легко проверить, что все графы на рис. 1 гамильтоновы, хотя условие Оре для них не выполнено. Может быть, тогда все вершинно-транзитивные графы (с более чем двумя вершинами) обязательно гамильтоновы? Это не так. Приведем два примера негамильтоновых, но вершинно-транзитивных графов (рис. 2).

Рис. 2

‌

Удивительно, но привести другие примеры вершинно-транзитивных, но не гамильтоновых графов не получается. Так и возникает вопрос, который называют гипотезой Ловаса, сформулированный впервые, по всей видимости, Ласло Ловасом в работе [2].

Гипотеза 1 (Lovasz conjecture). Верно ли, что вершинно-транзитивные графы с более чем двумя вершинами (за исключением графа Петерсона, графа Кокстера и графов, полученных из них заменой каждой вершины на треугольник) будут обладать гамильтоновым циклом?

Теоремы Оре и других достаточных условий гамильтоновости, про которые можно почитать в [3], недостаточно. Что же делать? Естественно, для начала попробовать найти отличие перечисленных нами «особенных» графов от прочих вершинно-транзитивных графов. Кроме того, для численных экспериментов хотелось бы найти обширный источник вершинно-транзитивных графов. И тут возникает еще один замечательный математический объект — графы Кэли.

Графы Кэли

Чтобы определить понятие графа Кэли, нам потребуется еще один важный математический объект — группа. Множество M, оснащенное операцией ∗, мы будем называть группой G = (M,∗), если выполнены три условия:

1. ассоциативность: a∗(b∗c) = (a∗b)∗c для любых трех элементов a, b, c;

2. есть нейтральный элемент e ∈ M, такой, что e∗a = a∗e = a для любого a;

3. есть обратный элемент b для каждого a, т. е. a∗b = b∗a = e.

Традиционными примерами групп являются (относительно операции сложения) целые и рациональные числа. Отметим: ни целые, ни рациональные числа при этом не образуют группу относительно операции умножения. Более содержательным примером группы оказываются автоморфизмы графа. Такая группа, заметим, не будет некоммутативной: от порядка применения автоморфизмов результат меняется. Еще одним важным примером является группа перестановок S_n, т. е. множество взаимнооднозначных отображений в себя n–элементного множества. Несложно заметить, что таких «перемешиваний» ровно n!. Подробное и доступное школьнику введение в теорию групп см. в [4].

Если у нас есть группа G, мы можем выделить в ней набор элементов g₁…g_k, таких, что любой элемент группы представляется в виде конечного произведения этих элементов. Такой набор называют системой образующих данной группы. Например, в группе целых чисел по сложению из единицы можно получить любое целое число, складывая или вычитая. Другим примером системы образующих для целых чисел будет пара 2,3.

Группу перестановок можно породить при помощи транспозиций соседних элементов, т. е. преобразований, которые меняют местами i и i + 1, а остальные элементы оставляют на месте. Чтобы убедиться в этом, достаточно вспомнить про сортировку пузырьком. Другой системой образующих будет пара из транспозиции и цикла длины n (т. е. перестановка, которая «сдвигает» элементы j, j < n направо, т. е. j → j + 1, а последний элемент переставляет в начало: n→1).

Теперь мы готовы определить понятие графа Кэли для группы G = (M,∗) при фиксированной системе образующих g₁…g_k. В качестве вершин графа возьмем множество M и будем говорить, что между вершинами a, b есть направленное ребро цвета g_i, если ag_i = b. Легко убедиться, что полученный граф (если забыть про цвета и направления ребер) будет вершинно-транзитивным. Собственно, чтобы перевести вершину A в вершину B, достаточно устроить автоморфизм следующим образом: m → B ∗ A^-1∗ m, m ∈ M. Несложно видеть, что вершина A при этом перейдет в B. Ну а проверку того, что соседние вершины всегда переходят в соседние, оставим читателю.

Возвращаясь к нашему рис. 1 поясним, что в центре изображен граф Кэли для группы S₄, порожденной циклом длины 3 и циклом длины 4, а справа изображен граф мультипликативной группы кватернионов ℚ₈. Что это за группа и какие другие свойства есть у графов Кэли, можно почитать в [5, 6].

Сразу скажем, что вполне осмысленно рассмотреть и гамильтоновы циклы, учитывающие направленность ребер, т. е. цикл должен не только быть гамильтоновым, но и двигаться можно только по направлению ребра. В таком «строгом варианте» есть много примеров направленных графов Кэли без такого цикла (даже для коммутативных групп). Есть и работы, в которых строятся бесконечные серии таких графов. Углубляться в исследование направленных графов мы не будем и далее графы Кэли будем понимать как неориентированные.

Теоретико-групповой подход

Удивительное наблюдение состоит в том, что все перечисленные нами негамильтоновы графы (в частности, оба графа с рис. 1), не будут при этом и графами Кэли! И, наоборот, все известные нам (человечеству, а не только автору текста) графы Кэли (понимаемые как неориентированные) будут обязательно обладать гамильтоновым циклом. Доказать это, правда, пока никому не удалось.

Cформулируем то, что часто называют слабой проблемой Ловаса, хотя впервые этот вопрос обсуждался за десять лет до работы Ловаса [2] в статье Эльвиры Рапопорт-Штрассер [7].

Гипотеза 2 (Weak Lovasz conjecture). Верно ли, что каждый граф Кэли, понимаемый как неориентированный, обладает гамильтоновым циклом?

Для неориентированного графа Кэли оказывается непросто доказать, что у любой конечно порожденной группы найдется разумная (т. е. не очень большая) система образующих, в которой граф Кэли будет гамильтоновым. Очень серьезное продвижение было получено в работе [10]. Было показано, что у всякой конечной группы G найдется система образующих с не более чем log₂ |G| элементов, такая, что соответствующий граф Кэли будет гамильтонов.

Впрочем, для широкого класса групп гамильтоновость (всех!) их графов Кэли доказана. Некоторые результаты собраны в обзоре [8]. Например, доказана гамильтоновость в случае групп, содержащих для простых p², p³, pq, pqr элементов, для попарно различных простых p, q, r. Одним из недавних продвижений является работа [9], в которой наличие гамильтонового цикла показано для еще одного семейства вершинно-транзитивных графов.

При этом слабая гипотеза Ловаса не решена при n > 5 даже для групп перестановок S_n. Впрочем, читатель может в качестве упражнения самостоятельно проверить, что для систем образующих, которые мы обсудили выше, оба графа Кэли группы S_n , n > 2 будут гамильтоновыми. Увы, но к общему ответу для произвольной системы образующих эти упражнения не ведут.

Подробнее о современном состоянии слабой проблемы Ловаса можно почитать в обзоре [11].

Польза в народном хозяйстве

Хотя математикой, вольно цитируя известную фразу Фейнмана про физику, занимаются и не ради практических результатов, всё же у проблемы Ловаса есть и прикладное значение. Мы остановимся на связи гамильтоновых циклов в графах с так называемыми кодами Грея.

По определению, кодом Грея называется способ кодировки линейно упорядоченного множества (последовательности слов или символов), при котором соседние элементы отличаются цифрой в одной позиции. Например, если мы хотим закодировать последовательность {A, B, C, D} при помощи двоичной записи, то получим следующее: A → 00; B → 01; C → 10; D → 11. Среди областей применения кодов такого типа — передача сигнала в различных датчиках, генетические алгоритмы и кодирование дорожек в жестких дисках. А еще они связаны со старинной задачей о ханойских башнях (см., например, [12]).

Но при чем же здесь гипотеза Ловаса? Давайте разберемся, как обобщить понятие кода Грея для кодирования вершин графа. Соседние вершины, которым нужно присвоить похожие числа, — это, понятное дело, вершины, которые соединены ребром. Стало быть, чтобы построить код Грея, нам нужно построить гамильтонов цикл в нашем графе, а дальше действовать как «в обычном случае». Соответственно, существование кода Грея упирается в существование гамильтонова цикла, или, в более слабом виде, гамильтонова пути — если мы разрешим, чтобы две вершины (начальная и конечная) были закодированы «похоже», но при этом не были соединены.

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

С практической точки зрения, заметим, можно ограничиться не одним большим гамильтоновым циклом, а несколькими циклами поменьше. В такой постановке возникает вопрос о том, насколько большой цикл можно гарантировать в вершинно-транзитивном графе, если уж мы не умеем доказывать, что можно пробежать все вершины. Здесь можно отметить работу [14], в которой было доказано, что в любом вершинно-транзитивном графе из N вершин обязательно найдется гамильтонов цикл длины хотя бы $\sqrt{3N}$.

Напоследок

В чем прелесть гипотезы Ловаса? Она связывает теорию групп и вопросы гамильтоновости графов — два понятия, связь между которыми абсолютно не очевидна ни на первый, ни на второй взгляд. При этом и методы, которые используются для ее решения, далеко не исчерпываются выдумыванием новых трюков с графами (чем, честно говоря, грешат многие другие разделы теории графов). Так что маловероятно, что гипотезу Ловаса решит какой-нибудь продвинутый школьник.

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

Впрочем, поживем — увидим! Как говорится, хорошо, что проблема не решена. Значит, она пока не решена!

Андроник Арутюнов, cт. науч. сотр. Института проблем управления РАН им. В. А. Трапезникова,
преподаватель Свободного университета, куратор раздела «Математика» в «Яндекс.Кью»

Иллюстрации: «Википедия»

1. Ore O. Note on Hamilton circuits. American Mathematical Monthly. — 1960. — Т. 67, вып. 1. 

2. Lovász L. Problem 11. In Combinatorial Structures and Their Applications (Proc. Calgary Internat. Conf., Calgary, Alberta, 1969), page 497. Gordon and Breach, New York, 1970.

3. Ronald J. Gould. Updating the Hamiltonian Problem — A Survey. J. GRAPH THEORY, 1991.

4. Алексеев В. Б. Теорема Абеля в задачах и решениях. — М.: МЦНМО, 2001.

5. Богопольский О. В. Введение в теорию групп. — М. — Ижевск: ИКИ, 2002.

6. Клячко А. А. Спецкурс «Теория групп».

7. Rapaport-Strasser E. Cayley color groups and Hamilton lines. Scripta Math., 24: 51–58, 1959.

8. Kutnar K., Marusic D. Hamilton cycles and paths in vertex-transitive graphs — Current directions. Discrete Mathematics 309 (2009) 5491–5500.

9. Du S., Kutnar K., Marusic D. Resolving The Hamiltonian Problem for Vertex-Transitive Graphs of Order a Product of Two Primes. Combinatorica 41, 507–543 (2021). DOI: 10.1007/s00493-020-4384-6

10. Pak I., Radoičić R., Hamiltonian paths in Cayley graphs, Discrete Math. 309 (2009) 5501–5508.

11. Lanel G. H. A survey on Hamiltonicity in Cayley graphs and digraphs on different groups. Discrete Mathematics, Algorithms and Applications Vol. 11, No. 5 (2019),

12. Кноп К. Ханойская башня. Элементы, 2012.

13. Mütze T. Combinatorial Gray codes-an updated survey, arXiv:2202.01280.

14. Babai L. Long cycles in vertex-transitive graphs, J. Graph Theory 3 (1979) 301–304.