Анализ структуры циклов некоторых графов Кэли на симметрической группе Медведев Алексей Николаевич

Введение к работе

Актуальность и степень разработанности темы исследований. В данной диссертации исследуются графы Кэли на симметрической группе. Изучение структуры данных графов представляет собой теоретический, а также практический интерес, поскольку графы Кэли на симметрической группе используются как модели построения компьютер-ных сетей [,], а также имеют применение в молекулярной биологии [,28,] и в теории кодирования [26]. Обзор задач на графах Кэли на симметрической группе можно найти в ]. Приведем основные определения.

Графом Кэли группы G c порождающим множеством S С G называется граф Г = Cay(G,S) = (V,E), вершинами которого являются элементы группы, а ребра соответствуют умножению элементов на порождающие, или, другими словами, V = G и Е = {{g,gs} : д Є G, s Є S}. В данной работе рассматриваются связные простые графы без петель и кратных ребер, поэтому на порождающее множество S накладываются следующие условия: е ф S и S = S^-1, где е обозначает единичный элемент группы G, а S^-1 обозначает множество обратных элементов к элементам из S. В этом случае, граф Кэли является неориентированным, ^-регулярным и вершинно-транзитивным.

Перестановкой называется взаимно-однозначное отображение 7Г множества {1,2,... , п} на себя. Будем записывать перестановки в виде строки 7Г = [7Гі 7Г2 ... 7г_га], где тгі = тг(і) для любого г Є {1,2,... ,п}. Определим симметрическую группу Sym(n) как группу всех перестановок множества {1,2,... ,п} с операцией умножения справа, определяемой следующим образом. Пусть тг,т Є Sym(n), тогда произведение 7Г г имеет следующий вид:

7Г Г = ["Л"! 7Г2 . . . 7Г_га][т\ Т2 Т_п] = ["7Г_Г1 7Г_Г2 . . . 7Г_Гп].

Сегментом [i,j] перестановки 7Г = [-л^-! ... 7Tj ... TTj ... 7г_га] будем называть все элементы, заключенные между тгі и ttj включительно. Приведем определения графов Кэли на группе Sym(n), рассматриваемых в данной работе.

Pancake графом называется Граф Кэли Р_п = Cay(Sym(n),PR) с порождающим множеством PR = {гі Є Sym(n), 2 ^ і ^ п} всех префикс-реверсалов г\ = [і (і — 1)... 1 (і + 1) ... п], меняющих порядок элементов внутри сегмента [1,г] перестановки 7Г на обратный при умножении на нее справа:

["Л"! 7Г2 . . . 7Гг—1 7Гі 7Гі₊і . . . 7Г_га] Г і = [їїі "Кі-\ ... 7Г2 7Гі TVi+l ТГга]

Star графом называется Граф Кэли S_n = Cay(Sym(n),ST) с порождающим множеством ST = {ti Є Sym(n),2 ^ і ^ п} всех транспозиций ti = (І і), меняющих местами

первый и -ый элемент перестановки при умножении на нее справа:

[! 2 . . . г—1 j і₊і . . . _га] j = [і 2 . . . j_i і i+l . . . _п].

Pancake граф получил свое название благодаря Pancake проблеме, поставленной Дж. Гудманом в 1975 году под названием “Harried Waite” ]:

“Шеф ресторана готовит блины разного размера и кладет их в стопку на тарелку. Официант берет тарелку с блинами и по пути к гостю должен отсортировать блины по размеру, беря стопку блинов сверху и переворачивая ее (совершая операцию FLIP). Переворачивая столько раз, сколько нужно, блины должны быть отсортированы от самого большого внизу, до самого маленького наверху. Если у официанта на тарелке блинов, за какое минимальное количество переворачиваний (операций FLIP) он может это сделать?”

В 2012 году было показано, что данная задача является NP-трудной [8].

Pancake проблема тесно связана с задачей поиска диаметра Pancake графа (_п), которая в общем случае тоже является NP-трудной. Первые оценки на диаметр были полу-чены независимо Э. Дьори и Д. Тураном в 1978 году ] и Б. Гейтсом и Х. Пападимитроу

в 1979 году [15]:

— ^ (_п) ^ — ( + 1).

Позднее, М. Хейдари и И. Садбороу в 1997 году ] и И. Садбороу в 2009 году [4] были

показаны улучшенные оценки на диаметр:

— ^ \_п) ^ —.
14 11

Данные результаты основываются на исследовании различных способов сортировки префи-кс-реверсалами и нахождении перестановок наибольшей и наименьшей сложности. Извест-ны также точные значения диаметра Pancake графов _п при ^ 19 ,.

Название Star графа связано с так называемыми транспозиционными графами, определяющими его порождающее множество. Пусть порождающее множество симметрической группы () состоит из транспозиций, тогда транспозиционным графом порождающего множества называется граф () = (,) с вершинами = {1,2,... ,} и ребро {,} Є , если транспозиция () Є . Название Star графов произошло от структуры транспозиционного графа порождающего множества : им является і_>п-і, который в теории графов называется графом "звезды". Для Star графа, известен алгоритм построения кратчайших путей и точное значение его диаметра ]:

(_n) = [3( — 1)/2_|.

Графы Кэли широко используются для построения компьютерных сетей, поэтому важно знать не только их глобальные свойства, но также и локальную структуру. Одним из аспектов локальной структуры является структура циклов. Изучение структуры циклов особенно интересно на графах, для которых еще не известно точное значение диаметра. Первый вопрос, возникающий в данном контексте - это вопрос возможности вложения циклов в качестве индуцированных подграфов. В 1996 году А. Каневским и Ч. Фенгом было показано, что Pancake граф Р_п,п ^ 3, является почти пан-цикличным, и в него вкладываются циклы длины , где 6 ^ ^ п! — 2 и = п! [], а вложимость цикла длины = п! — 1 была установлена Дж. Шеу и др. в 2006 году []. Ввиду того, что порождающее множество ST состоит из транспозиций, Star граф является двудольным и, поэтому, не содержит циклов нечетной длины. Возможность вложения циклов четной длины , где 6 ^ ^ п!, в Star графы была показана Дж. Джо и др. в 1991 году ].

В упомятнутых работах показано лишь существование циклов, однако полного их описания представлено не было. При решении некоторых задач, в частности, при поиске хроматического числа графа, важен не только сам факт наличия в нем циклов, но и их точное описание ]. В диссертации приведено полное описание циклов малой длины в Pancake графах Р_п, п ^ 3, и Star графах S_n,n ^ 3.

Гамильтоновым циклом в графе называется простой цикл проходящий через все его вершины. Задача поиска гамильтоновых циклов в графах Кэли представляет отдельный интерес [. В 1969 году была выдвинута следующая гипотеза ]:

Гипотеза. Любой связный граф Кэли является гамильтоновым.

Данная гипотеза до сих пор не опровергнута, и все известные примеры графов Кэли являются гамильтоновыми.

В 1975 году было доказано, что графы Кэли на симметрической группе являются гамильтоновыми, если порождающее множество состоит из транспозиций . Поскольку порождающее множество ST состоит из транспозиций, то гамильтоновость Star графа вытекает из упомянутого выше результата.

В 1984 году С. Закс показал гамильтоновость Pancake графов ]. Стоит отметить, что его работа была написана безотносительно к самому графу: в статье был предложен алгоритм последовательного порождения перестановок посредством суффикс-реверсалов, которые очевидным образом соответствуют операции префикс-реверсалов. Опишем алгоритм Закса применительно к Pancake графу.

Для построения гамильтонова цикла в графе Р_п,п ^ 3, строится последовательность

(_п префикс-реверсалов следующим рекурсивным образом:

1. <^2 = Т2;

2. Cfc = (Cfc-i r_k)^k~^l (_fc_i, к > 2,

где степень означает конкатенацию последовательности, записанной внутри скобок. По-следовательность (_пг_п, примененная к произвольной перестановке 7Г Є Sym(n), задает последовательность обхода ребер графа Р_п, образующая гамильтонов цикл.

Такие гамильтоновы циклы в графах Кэли на группе комбинаторных объектов, кото-рые могут быть построены простым и эффективным алгоритмом, неразрывно связаны с кодами Грея. Комбинаторным кодом Грея называется метод порождения комбинаторных объектов, так что каждый последующий отличается от предыдущего некоторым заданным образом []. Д. Кнут определяет комбинаторное порождение в следующем виде [23]:

“Коды Грея относятся к эффективным алгоритмам полного порождения комбинаторных объектов (кортежей, перестановок, разбиений, деревьев).”

Понятие префикс-реверсального кода Грея как отдельного класса было впервые введено в 2013 году А. Вильямсом в ], где в частности был предложен новый алгоритм построения гамильтонова цикла в Pancake графе, основанный на так называемом жадном подходе. Рассмотрим упорядоченное множество префикс-реверсалов GR = {r_mi, г_т2,... , ^rm_k} ^ PR, где к ^ п — 1. Тогда жадным гамильтоновым циклом называется гамильтонов цикл, образованный последовательным применением префикс-реверсалов г_ті Є GR с наименьшим возможным индексом г на каждом шаге. Последовательность GR называется жадной последовательностью. Конструкция Вильямса имеет жадную последовательность GRw = {т_п, г_га_і,... ,Гз, Гг}, и было замечено, что конструкция Закса также является жадным гамильтоновым циклом с жадной последовательностью GRz = {т'2, ?"з, ,f'n-\, Тп\. В статье [] ставится открытый вопрос о существовании других жад-ных гамильтоновых циклов в Pancake графе. В диссертации найдены новые префикс-реверсальные коды Грея в графе Р^, доказано необходимое условие существования жадных гамильтоновых циклов, а также предложена новая конструкция гамильтоновых циклов на основе независимых циклов в Pancake графах Р_п для любых п ^ 4.

Задача подсчета малых циклов широко известна в теории графов. Ей занимались такие крупные специалисты, как Н. Алон [, а первая статья была опубликованна в данном направлении Дж. Бонди и М. Симоновитсом в 1974 году ]. На основе описания циклов малой длины в Pancake и Star графах в диссертации получено точное число этих циклов.

Однако, для Star графа известен алгоритм построения кратчайших путей, описанный С. Акерсом и Б. Кришнамурти в []. На основе данного алгоритма и дистанционного распределения вершин, описанного Л. Вангом и др. в ], в диссертации представлен альтерна-тивный подход, позволяющий получить число малых циклов в Star графах без их полного описания.

Основой альтернативного подхода является исследование циклов длины 2d, проходящих через данную вершину, и состоящих из двух вершинно-непересекающихся кратчайших путей длины d до некоторой другой вершины. Исследование количества таких циклов имеет отдельный практический интерес ], который состоит в следующем. Рассмотрим семейство графов G_n = (V_n,E_n) с выделенными вершинами s и t, такое что V_n,E_n —> оо при п —> оо. Широко известна модель ориентированной перколяции на графах [], представляющая собой произвольное удаление ребер с вероятностью 0 < р < 1 и нахождение критического значения р_с при п —> оо, такого что для любого р > р_с вероятность нахождения пути между вершинами s и t равна нулю при п —> оо, а для любого р < р_с такая вероятность положительна. Эта практическая задача была решена для гиперкуба Н_п Дж. Филлом и Р. Пемантлом в статье [], где разработан метод исследования задачи перколяции, применимый к вершинно-транзитивным графам, основой которого является подсчет и оценка циклов, образованных двумя непересекающимися кратчайшими путями. В диссертации исследуется число таких циклов.

Исследование числа таких циклов является основой описанного выше метода и позволит решить задачу ориентированной перколяции для Star графа в будущем.

Цель диссертации состоит в исследовании структуры циклов малой и большой длины в графах Кэли на симметрической группе с порождающим множеством префикс-реверсалов (Pancake графы) и префикс-транспозиций (Star графы).

Научная новизна и значимость работы. Работа носит теоретический характер. Все основные результаты диссертации являются новыми, снабжены подробными доказа-тельствами и вносят вклад в теорию графов Кэли. Результаты работы могут быть использованы для дальнейшего исследования структурных свойств графов Кэли на симметрической группе. Отдельные результаты данной диссертации включены в спецкурсы для студентов и аспирантов, специализирующихся в области дискретной математики ].

Методы исследования. В работе используются методы теории графов, методы алгебраического и комбинаторного анализа, перечислительной комбинаторики.

Основные результаты диссертации.

1. Предложен подход на основе иерархического строения для описания циклов малой

длины в Pancake и Star графах. Данный подход применен для описания циклов малой длины в Pancake графах Р_п для любых п ^ 3, и Star графах S_n для любых п ^ 3. Получено полное описание циклов длины в Pancake графах Р_п, п ^ 3, где = 6, 7, 8, и Star графах S_n, п ^ 3, где = 6, 8.

2. Предложена новая конструкция гамильтоновых циклов на основе независимых циклов в Pancake графах Р_п для любых п ^ 4. Предложенная конструкция включает в себя все известные конструкции префикс-реверсальных кодов Грея, соответствующих гамильтоновым циклам в графах Р_п, п ^ 4, а также описывает новые конструкции префикс-реверсальных кодов Грея в графе Р^. Доказаны теоремы о несуществовании гамильтоновых циклов, основанных на независимых циклах, в графах Р_п, п ^ 5, с использованием нового понятия скрепляющих циклов. Доказано необходимое условие существования жадных префикс-реверсальных кодов Грея.

3. Найдено число циклов малой длины в Pancake графах Р_п, п ^ 3, где = 6,7,8, и Star графах S_n, п ^ 3, где = 6,8,10. Получена асимптотическая оценка числа циклов длины 2d в Star графах S_n, п ^ 3, где 3 ^ d ^ п.

Публикации. По теме диссертации автором опубликовано 11 работ, в том числе 4 статьи в журналах из списка ВАК. Часть работ опубликована в неразделимом соавторстве с Е.В. Константиновой.

Апробация работы. Результаты диссертации докладывались на следующих научных семинарах:

семинаре Института Математики им. С.Л. Соболева “Теория графов”, “Теория кодирования”;

общеинститутском научного семинаре Института Математики им. С.Л. Соболева в 2013 и 2016 годах;

семинаре для аспирантов (PhD student seminar) в Центральном Европейском Университете (Central European University), г. Будапешт, Венгрия, в 2013 и 2015 году;

математическом исследовательском семинаре (Mathematical Research seminar) в Университете Приморска (University of Primorska), г. Копер, Словения, в 2015 году.

Результаты диссертации докладывались на следующих научных конференциях:

на Международной Научной Студенческой Конференции (Новосибирск, 2010, 2012);

на Седьмой Словенской Международной Конференции по теории графов “BLED-2011” (Словения, 2011);

на международной конференции “Дискретный анализ и исследование операций” (Новосибирск, 2013);

на международной конференции “Symmetries of Graphs and Networks IV” (Словения, 2014);

на международной конференции “Graphs and Groups, Cycles and Coverings” (Новосибирск, 2014);

на международной конференции “Graphs and Groups, Algorithms and Automata” (Екатеринбург, 2015).

Часть результатов диссертации была включена в список важнейших результатов Института Математики им. С.Л. Соболева в 2013 году.

Структура работы. Диссертация состоит из введения, трех основных глав, заключения, списка литературы (64 наименования), 17 рисунков и 4 таблиц.