Электронная библиотека диссертаций и авторефератов России
dslib.net
Библиотека диссертаций
Навигация
Каталог диссертаций России
Англоязычные диссертации
Диссертации бесплатно
Предстоящие защиты
Рецензии на автореферат
Отчисления авторам
Мой кабинет
Заказы: забрать, оплатить
Мой личный счет
Мой профиль
Мой авторский профиль
Подписки на рассылки



расширенный поиск

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

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

Диссертация - 480 руб., доставка 10 минут, круглосуточно, без выходных и праздников

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Медведев Алексей Николаевич. Анализ структуры циклов некоторых графов Кэли на симметрической группе: диссертация ... кандидата Физико-математических наук: 01.01.09 / Медведев Алексей Николаевич;[Место защиты: Институт математики им. С.Л.Соболева Сибирского отделения Российской академии наук], 2016.- 81 с.

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

Актуальность и степень разработанности темы исследований. В данной диссертации исследуются графы Кэли на симметрической группе. Изучение структуры данных графов представляет собой теоретический, а также практический интерес, поскольку графы Кэли на симметрической группе используются как модели построения компьютер-ных сетей [,], а также имеют применение в молекулярной биологии [,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Г2 . . . 7ГГп].

Сегментом [i,j] перестановки 7Г = [-л-! ... 7Tj ... TTj ...га] будем называть все элементы, заключенные между тгі и 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 графом называется Граф Кэли Sn = 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 графах Sn,n ^ 3.

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

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

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

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

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

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

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

  1. <^2 = Т2;

  2. Cfc = (Cfc-i rk)k~l (fc_i, к > 2,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  2. Найдено число циклов малой длины в Pancake графах Рп, п ^ 3, где = 6,7,8, и Star графах Sn, п ^ 3, где = 6,8,10. Получена асимптотическая оценка числа циклов длины 2d в Star графах Sn, п ^ 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 таблиц.