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

• Медведев Алексей Николаевич
• кандидат наук
• 2016

Оглавление диссертации кандидат наук Медведев Алексей Николаевич

1.1 Предварительные сведения

1.2 Описание циклов в Pancake графе

1.2.1 Циклы длины шесть

1.2.2 Циклы длины семь

1.2.3 Циклы длины восемь

1.3 Описание циклов в Star графе

1.3.1 Технические Леммы

1.3.2 Циклы длины шесть

1.3.3 Циклы длины восемь

2 Гамильтоновы циклы в Pancake графах

2.1 Предварительные сведения

2.2 Гамильтоновы циклы на независимых циклах: случай Р4

2.3 Семейство независимых циклов четной длины

2.4 Гамильтоновы циклы на независимых циклах: общий случай

2.4.1 Скрепляющие циклы Hn(m,j) и Нп(n,j)

2.4.2 Скрепляющий цикл Нп(т,£)

2.5 Необходимое условие существования жадных префикс-реверсальных кодов Грея

3 Исследование (^,г^)-циклов в Star графах

3.1 Предварительные сведения

3.2 Технические Леммы

3.3 Число малых (ж,г^)-циклов в Star графе

3.4 Применение (n,id)-циклов

3.4.1 Число 10-циклов в Star графе

3.4.2 Асимптотическая оценка числа малых циклов в Star графе

4 Заключение

Список литературы

Введение диссертации (часть автореферата) на тему «Анализ структуры циклов некоторых графов Кэли на симметрической группе»

Введение

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

Графом Кэли группы 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. В этом случае, граф Кэли является неориентированным, IS|-регулярным и вершинно-транзитивным.

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

п • Т = [^1 . . . Кп][т1 Т2 ... тп] = \жТ1 -КТ2 ... ПТп].

Сегментом [i,j] перестановки -к = [ж1 ... жi ... nj ... будем называть все элементы, заключенные между -кг и -Kj включительно. Приведем определения графов Кэли на группе Sym(n), рассматриваемых в данной работе.

Pancake графом называется Граф Кэли Рп = Cay(Sym(n),PR) с порождающим мно-

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

... К— -Kj ... Кп] Ti = [Kj -Kj-i ... . . .

Star графом называется Граф Кэли Sn = Cay(Sym(n),ST) с порождающим множеством ST = {ti Е Sym(n), 2 ^ г ^ п} всех транспозиций ti = (1 г), меняющих местами первый и г-ый элемент перестановки -к при умножении на нее справа:

[^1 Ж2 . . . Пг-i Щ ni+i . . . ti = [щ Ж2 . . . ^i-1 . . . Кп].

Будем ассоциировать вершины данных графов с соответствующими им перестановками. Графы Кэли Гга имеют иерархическое строение, если существует порядок элементов на порождающем множестве {s1,... ,sn}, такой что для каждого г, где 2 ^ г ^ п, элемент Si находится вне подгруппы, образованной порождающим множеством {S1,... ,Si—1}. Известно, что Pancake и Star графы с данным порядком порождающих элементов обладают иерархическим строением [5].

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

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

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

Пусть порождающее множество S симметрической группы Sym(n) состоит из транспозиций, тогда транспозиционным графом порождающего множества S называется граф Т(S) = (V,E) с вершинами V = {1,2,... ,п} и ребро {i,j} Е Е, если транспозиция (i j) Е S. Известно, что порождающее множество S, состоящее из транспозиций, является минимальным, если транспозиционный граф Т(S) имеет структуру дерева [24]. Название Star графов произошло от структуры транспозиционного графа порождающего множества ST: им является К1;п-1, который в теории графов называется графом "звезды".

Графы Кэли находят широкое применение как в теоретических разделах математики, так и в практических задачах, поэтому имеется широкий спектр задач, формулируемых для этих графов. В данной Главе будут рассмотрены следующие актуальные задачи, имеющие отношение к теме диссертации: 1) задача о диаметре; 2) задача о структуре циклов; 3) задача о гамильтоновых циклах; 4) задача поиска кодов Грея; 5) задача подсчета числа циклов.

ЗАДАЧА О ДИАМЕТРЕ. В теории графов под диаметром графа понимается длина максимального кратчайшего пути в графе. Для графа Кэли Г = Cay(G,S) его диаметр diam(Cay(G,S)) определяется, как наибольшая длина по всем элементам группы g Е G наименьшего представления в виде произведения порождающих g = s1 s2 ... sm, где Sk Е S, 1 ^ к ^ т. Задача поиска диаметра произвольного графа Кэли сводится к проблеме поиска минимального слова в группе, поэтому является ЖР-трудной [20].

Первые результаты исследования диаметра графов Кэли произвольных групп были получены еще П. Эрдёшем и А. Реньи в 1965 году [19]. В 1992 году Л. Бабаи и А. Сереш получили асимптотические оценки диаметра произвольного графа Кэли Cay(G,S) группы G с произвольным порождающим множеством S, используя структурные свойства группы G [9]. Было замечено, что diam(Cay(G,S)) для абелевых групп отличается от значений для неабелевых групп. Более того, была выдвинута следующая гипотеза [8].

Гипотеза 1. Пусть G неабелева группа с порождающим множеством S. Тогда существует с> 0, такое что

diam(Cay(G,S)) < (log |G|)C.

Гипотеза до сих пор остается открытой. Лучшим результатом в этом направлении на данный момент является работа Л. Пибера и Э. Сабо, опубликованная в 2014 году [43], где утверждается, что для конечной простой группы Ли G конечного ранга г существует полином с(г), такой что diam(Cay(G,S)) < (log |G|)c(r) для любого порождающего множества 5.

Графы Кэли симметрической группы Sym(n) имеют субэкспоненциальный диаметр. Пусть g Е Sym(n), тогда носителем элемента g называется множество supp(g) = {7 Е {1,2,... ,п} | g(^f) = 7}. Пусть Alt(n) С Sym(n) является группой четных перестановок.

Теорема 1. [11] Пусть G = Sym(n) или G = Alt(n), С = 0.63 и порождающее множество S содержит элемент д, такой что Isupp(g)I < Сп. Тогда существует с> 0, такое что

diam(Cay(G,S)) < 0(пс).

В 2014 году Х. Хельфготтом и А. Серешем был получен следующий результат для симметрической группы или группы четных перестановок вне зависимости от порождающего множества.

Теорема 2. [27] Если G = Sym(n) или G = Alt(n), то

diam(Cay(G,S)) = exp(0((\og п)4 log log п)).

Первые оценки диаметра Pancake графа diam(Pn) были получены независимо Э. Дьо-ри и Г. Тураном в 1978 году [25] и Б. Гейтсом и Х. Пападимитроу в 1979 году [22]:

17 5

—п ^ diam(Pn) ^ - (п +1). 16 3

Позднее, М. Хейдари и И. Садбороу в 1997 году [29] и И. Садбороу в 2009 году [3] получили улучшенные оценки диаметра:

15 , /^ч 18

— п ^ dtam(Pn) ^ — п.

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

Таблица 1. Точные значения диаметра Pancake графов Рп для п ^ 19.

п 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

diam(Pn) 4 5 7 8 9 10 11 13 14 15 16 17 18 19 20 22

Для Star графа, напротив, известен алгоритм построения кратчайших путей и точное значение диаметра diam(Sn) [4]:

diam(Sn) = [3(п — 1)/2\.

ЗАДАЧА О СТРУКТУРЕ ЦИКЛОВ. Графы Кэли широко используются для построения компьютерных сетей, поэтому важно знать не только их глобальные свойства, но также и локальную структуру. Одним из аспектов локальной структуры является структура циклов. Изучение структуры циклов особенно интересно на графах, для которых еще не известно точное значение диаметра. Первый вопрос, возникающий в данном контексте - это вопрос возможности вложения циклов в качестве индуцированных подграфов. Возможность вложения циклов в Pancake графы была показана в 1996 году А. Каневским и

Ч. Фенгом и результат усилен Дж. Шеу и др. в 2006 году, а в Star графы в 1991 году Дж. Джо и др.

Теорема 3. [32,47] В Pancake графах Рп, п ^ 3, существуют циклы длины I, где 6 ^ I ^ п\. Циклов длины 3, 4 и 5 в Pancake графах нет.

Теорема 4. [31] В Star графах Sn,n ^ 3, существуют циклы только четной длины I, где 6 ^ I ^ п\. Циклов длины 4 в Star графах нет.

Теоремы 3 и 4 являются теоремами о существовании, и полного описания всех циклов в теоремах представлено не было. Однако в некоторых задачах, в частности, при поиске хроматического числа графа, интересен не только сам факт наличия в нем циклов, но и их точное описание [2]. В Главе 1 приводится полное описание циклов малой длины в Pancake графах Рп,п ^ 3, и Star графах Sn,n ^ 3.

ЗАДАЧА О ГАМИЛЬТОНОВЫХ ЦИКЛАХ. Гамильтоновым циклом в графе называется простой цикл проходящий через все его вершины. Граф называется гамильто-новым, если он содержит гамильтонов цикл. Задача поиска гамильтонова цикла в произвольных графах, впервые поставленная сэром Гамильтоном в 1850-х годах, является широко известной задачей теории графов. Данная задача, именуемая в литературе как задача коммивояжера, также является классической ЖР-трудной задачей [26].

Задача поиска гамильтоновых циклов в графах Кэли также представляет отдельный интерес [37]. К первым общим результатам изучения гамильтоновости графов Кэли относится следующий результат, полученный Э. Раппапорт-Страссер в 1959 году. Элемент а конечной группы G называется инволюцией, если с? = е.

Теорема 5. [45] Пусть G конечная группа, порожденная тремя инволюциями такими, что = Ра. Тогда граф Кэли Cay(G,{a, P,j}) является гамильтоновым.

После ряда общих положительных результатов, была сформулирована следующая гипотеза [39].

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

Данная гипотеза до сих пор не опровергнута, и все известные примеры графов Кэли являются гамильтоновыми. Интересно, что данная гипотеза не верна для всех вершинно-транзитивных графов, поскольку, например, граф Петерсена, являющийся вершинно-тран-зитивным графов, но не графом Кэли, не является гамильтоновым.

В 1996 году Л. Бабаи выступил с критикой Гипотезы 2 [7], предположив обратное утверждение.

Гипотеза 3. Для любого £ > 0 существует бесконечно много связных вершинно-транзи-тивных графов Г = (V,E) (в частности графов Кэли), не содержащих циклов длины

I > (1 — e)IV|.

До сих пор эти две взаимоисключающие гипотезы остаются открытыми.

Абелевы группы оказались "хорошими" в смысле гамильтоновости. Д. Марушич в 1983 году показал, что практически для всех абелевых групп соответствующий граф Кэли является гамильтоновым.

Теорема 6. [40] Пусть G абелева группа c порождающим множеством S, такая что |G| > 3. Тогда граф Кэли Cay(G,S) является гамильтоновым.

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

Теорема 7. [41] Каждая конечная группа G, |G| > 3, имеет порождающее множество S, где 1 < log2 |G|, такое что соответствующий граф Кэли Cay(G,S) является гамильтоновым.

Доказательство Теоремы базируется на том факте, что любую неабелеву группу можно породить двумя элементами, одним из которых является инволюция.

В 1975 году было доказано, что графы Кэли на симметрической группе являются гамильтоновыми, если порождающее множество состоит из транспозиций [1]. Кроме того, если S порождающее множество симметрической группы, состоящее из транспозиций, тогда существует гамильтонов путь в соответствующем графе Кэли Cay(Sym(n),S), соединяющий вершины противоположной четности [49]. Поскольку порождающее множество ST состоит из транспозиций, то гамильтоновость Star графа вытекает из упомянутого выше результата.

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

Для построения гамильтонова цикла в графе Рп,п ^ 4, строится последовательность (п префикс-реверсалов следующим рекурсивным образом:

1 С2 = Г2;

2. (к = ((k-i rk)к-1 (к-1, к> 2,

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

В Главе 2 изучается вопрос наличия в Pancake графах гамильтоновых циклов на основе независимых циклов.

ЗАДАЧА ПОИСКА КОДОВ ГРЕЯ. Исследование кодов Грея началось с представления двоичного отраженного кода Грея на множестве двоичных векторов [23]. Как позже было замечено, данный код представляет собой гамильтонов цикл в n-кубе и, в общем случае, существует взаимо-однозначное отображение n-битных циклических кодов Грея и множества гамильтоновых циклов в п-кубе [48]. Позднее, было введено понятие комбинаторного кода Грея, как способа порождения комбинаторных объектов, так что каждый последующий отличается от предыдущего некоторым заданным образом [30]. Д. Кнут определяет комбинаторное порождение в следующем виде [34]:

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

Гамильтоновы циклы неразрывно связаны с кодами Грея. Если определить граф Кэли на группе комбинаторных объектов, то комбинаторному коду Грея на множестве этих объектов будет соответствовать гамильтонов цикл в таком графе Кэли.

Понятие префикс-реверсального кода Грея, как отдельного класса, было впервые введено в 2013 году А. Вильямсом в [50], где, в частности, была предложена новая конструкция гамильтонова цикла в Pancake графе, основанная на жадном подходе. Рассмотрим упорядоченное множество префикс-реверсалов GR = {гт1 ,rm2 ,...,rmk} С PR, где k ^ п — 1. Жадным гамильтоновым циклом называется гамильтонов цикл, образованный последовательным применением префикс-реверсалов rmi Е GR с наименьшим возможным индексом i на каждом шаге. Последовательность GR называется жадной последовательностью. Конструкция Вильямса имеет жадную последовательность GRw — {гп, гп-1,... ,г3,г2}, а конструкция Закса дает жадный гамильтонов цикл с жадной последовательностью GRz = {г2, г3,... ,гп-1, гп}.

В статье [51] ставится открытый вопрос о существовании других жадных гамильтоно-вых циклов в Pancake графе. В Главе 2 обсуждается данный вопрос, а также доказывается

необходимое условие их существования.

ЗАДАЧА ПОДСЧЕТА ЧИСЛА ЦИКЛОВ. Данная задача широко известна в теории графов, ей занимались такие крупные специалисты, как Н. Алон [6], а первая статья была опубликованна в данном направлении Дж. Бонди и М. Симоновитсом в 1974 году [10].

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

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

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

Положения, выносимые на защиту. На защиту выносятся следующие основные положения.

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

l = 6, 7, 8, и Star графах Sn, n ^ 3, где l = 6, 8.

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

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

Структура диссертации.

В первой главе изучается строение циклов малой длины в Pancake и Star графах. Предлагается подход к описанию циклов малой длины, основанный на иерархической структуре рассматриваемых графов, и данный подход применяется для описания циклов длины l, где I = 6, 7, 8, в Pancake графах, и длины I, где I = 6, 8, в Star графах. Полное описание циклов позволяет получить число этих циклов, проходящих через любую заданную вершину, и общее число циклов в рассматриваемых графах.

Формой цикла Се длины I в графе Кэли Г = Cay(G,S) с порождающим множеством S = |si,...,sfc}, будем называть последовательность порождающих элементов Се = Si0 ... Sit-1, где 1 < ij < к, и ij = ij+1 ((j + 1) modl) для любого j E {0,... / — 1}, таких что g Si0... Sie_ 1 = g, где g E G. Цикл Се длины l будем также называть l-циклом. Известно, что каждый l-цикл может быть представлен 21 формами (не обязательно различными) по отношению к начальной вершине и направлению обхода. Канонической формой l-цикла Се называется форма с лексикографически максимальной последовательностью индексов io. ..ie-i.

Основными результатами Главы 1 является полное описание циклов длины шесть, семь и восемь в Pancake графах и циклов длины шесть и восемь в Star графах. Описание циклов длины шесть в Pancake графах представлено в следующей Теореме.

Теорема 1.1. В графе Рп,п > 3, через каждую его вершину проходит ровно один цикл

длины шесть канонической формы

Сб = Г3 Г2 г3 Г2 г3 Г2.

Описание циклов длины семь в Pancake графах представлено в следующей Теореме.

Теорема 1.2. В графе Рп,п > 4, через каждую его вершину проходит ровно 7 (п — 3) различных циклов длины семь следующих канонических форм:

Cj = rk rk-1 rk rk-1 rk-2 rk Г2, 4 < k < n.

Всего граф Pn содержит (n — 3)n\ различных циклов длины семь.

Описание циклов длины восемь в Pancake графах представлено в следующей Теореме.

Теорема 1.3. В графе Рп,п > 4, через каждую его вершину проходит ровно N = 2(пз + 12п2 — 103п + 176) различных циклов длины восемь следующих канонических форм:

Cl = rk r-j п r-j rk rk-j+i n rk-j+i, 2 ^ г < j ^ k — 1, 4 ^ k ^ n,

Cl = rk rk-1 Г2 rk-1 rk Г2 Гз Г2, 4 ^ k ^ n,

c38 = rk rk-i rk-1 Vi rk rk-i rk-1 Гг, 2 ^ i ^ k — 2, 4 ^ k ^ n,

Cl = rk rk-i+1 rk Vi rk rk-i rk-1 r-1, 3 ^ % ^ k — 2, 5 ^ k ^ n,

Cl = rk rk-1 fi-1 rk rk-i+1 rk-i rk n, 3 ^ г ^ k — 2, 5 ^ k ^ n,

Cl = rk rk-1 rk rk-i rk-i-1 rk n ri+1, 2 ^ г ^ k — 3, 5 ^ k ^ n,

Cl = rk rk-j+1 rk ri rk rk-j+1 rk Vi, 2 ^ i < j ^ k — 1, 4 ^ k ^ n,

Cl = Г 4 Гз Г4 Гз Г4 Гз r4 Гз.

Всего граф Pn содержлт N^ различных циклов длины восемь.

Описание циклов длины шесть в Star графах представлено в следующей Теореме.

Теорема 1.4. В Star графе Sn,n ^ 3, каждая вершина принадлежит различным

циклам длины шесть следующих канонических форм:

С6 = tk ti tk ti tk ti, 2 ^ i<k ^ n.

Всего граф Sn содержит (n~различных циклов длины шесть.

Описание циклов длины восемь в Star графах представлено в следующей Теореме.

Теорема 1.5. В Star графе Sn,n ^ 4, каждая вершина принадлежит 3(п — 3)(п — 2)(п — 1) различным циклам длины восемь следующих канонических форм:

Cl = tk ti tj ti tk ti tj ti, 2 ^ i = j ^ к — 1, 4 ^ к ^ n;

Cf = tk tj ti tj tk ti tj ti, 2 ^ г = j ^ к — 1, 4 ^ к ^ n; Сf = tk tj ti tk tj tk ti tj, 2 ^ i = j ^ к — 1, 4 ^ к ^ n;

Сg = tk tj tk ti tk tj tk ti, 2 ^ i < j ^ к — 1, 4 ^ к ^ n. Всего граф Sn содержит 3(ra-3)(ra-2)(ra-1)n! различных циклов длины восемь.

Результаты первой главы опубликованы в работах [53-55,58-59,61].

Во второй главе рассматриваются префикс-реверсальные коды Грея, соответствующие гамильтоновым циклам в Pancake графе. В данной главе вводится новая конструкция гамильтоновых циклов, основанных на независимых циклах, и показывается, что в Pancake графах введенная конструкция описывает все известные конструкции префикс-реверсальных кодов Грея.

Максимальным множеством независимых циклов будем называть множество верши-нно-непересекающихся циклов в графе, покрывающих все вершины этого графа. Для краткости изложения будем опускать слова "максимальное множество".

Ребра, соединяющие вершины различных независимых циклов и не принадлежащие ни одному из них, называются внешними ребрами к данному множеству циклов. Гамиль-тонов цикл Нп в Рп,п ^ 3, называется основанным на независимых циклах длины l, если он состоит из набора (l — 1) -путей, полученных удалением ребра из каждого из этих циклов, соединенных вместе внешними к этим циклам ребрами. Ребра независимых циклов, не принадлежащие гамильтонову циклу Нп, называются неиспользованными ребрами. Внешние ребра вместе с неиспользованными ребрами образуют скрепляющий цикл Нп гамильтонова цикла Нп.

В Pancake графе Р4 получено полное описание гамильтоновых циклов, основанных на независимых циклах одной формы. Данное описание приводится в Разделе 2.2 в следующей Теореме.

Теорема 2.1. В Pancake графе Р4 существуют только четыре формы гамильтоновых циклов, основанных на независимых циклах, представленные в Таблице 2.

В Разделе 2.4 Главы 2 также рассматриваются гамильтоновы циклы Нп в графах Рп,п ^ 5, основанные на независимых циклах, представленные формой Се = (rn rm)k. В

Таблица 2. Гамильтоновы циклы основанные на независимых циклах в Р4

Щ Иi п4 Описание

Щ = ((г2 гэ)2г2 Г4)4 Hi = (Г4Г3)4 Гамильтонов цикл Закса;

Hi = ((гз Г2)2Г3 Г4)4 Щ = (Г4Г2)4 основанный на независимых С6;

Щ = ((г4 Гз)3Г4 Г2)3 Щ = (Г3Г2)3 Гамильтонов цикл Вильямса;

Hi = ((f4 Г2)3Г4 Гз)3 щ = (Г2Г3)3 основанный на независимых С8.

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

Нп (т£) = г k г к ... г к ,

где rii е РП\[гп,Гк}, где 1 ^ i ^ t, и

Тп Tj . . . Тп Tj,

вместе с формой

Tm Tj . . . Тт Tj,

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

Теорема 2.2. В Pancake графе Рп,п ^ 5, не существует гамильтоновых циклов Нп со скрепляющим циклом Нп(п,j) или Нп(m,j).

Теорема 2.3. В Pancake графе Рп,п ^ 5, не существует гамильтоновых цикла Нп со скрепляющими циклами Нп(т,£), где т е {2,... ,п — 3}.

В Разделе 2.5 Главы 2 рассматриваются жадные префикс-реверсальные коды Грея. С помощью подхода скрепляющих циклов было получено необходимое условие существования таких кодов, сформулированное в следующей Теореме.

Теорема 2.4. Пусть НЩ жадный гамильтонов цикл в Pancake графе Рп, п ^ 4, с соответствующей жадной последовательностью GR = {rmi ,гт2,... ,rmk}, где k ^ п — 1. Тогда длина НЩ удовлетворяет равенству

1 к-1

\НШ\ = n\ = 2Fr2 ПI' i=l

где &i длина цикла формы Cli = (rmi rmi+1 )к, 1 ^ г ^ к — 1.

Результаты второй главы опубликованы в работах [56,60,62].

В третьей главе исследуется число различных циклов четной длины 2d, проходящих через данную вершину в Star графах Sn,n ^ 4. Поскольку Star граф является вершинно-транзитивным, то рассматриваются циклы, проходящие через вершину id, соответствующую единичной перестановке. Показано, что циклы состоящие из двух непересекающихся кратчайших путей между вершиной id и вершиной -к на расстоянии d, дают асимптотическую оценку на число таких циклов при п ^ <х. Будем называть такие циклы (ж,id)-циклами и будем изучать их исходя из рассмотрения циклических представлений перестановок ж, соответствующих вершинам на расстоянии d от единичной id.

Пусть -к Е Sym(n) представлена в виде произведения непересекающихся циклов:

я- = к... < ж1 ...nh)... (^... <) = («Ж)... ),

где = п2 ... и li число элементов в цикле г, и l ^ 1, где 0 ^ i ^ к. Цикл длины т который содержит элемент "1" обозначается как т—СО, а цикл, который не содержит "1", обозначим как т — CN. Также будем использовать запись СО-цикл или CW-цикл, если длина цикла не уточняется. Цикл называется тривиальным, если он содержит только один элемент. Под циклической структурой перестановки понимается количество элементов в СО-цикле и количество нетривиальных CW-циклов.

Пример. Рассмотрим перестановку -к = [354126]. Циклическое представление перестановки -к = (134)(25)(6); циклическая структура к содержит нетривиальный 3 — СО (134), один нетривиальный 2 — CN (25) и один тривиальный CN (6).

Обозначим через N0(k) количество различных (n,id)-циклов, проходящих через все вершины -к с тривиальным СО-циклом и к нетривиальными СЖ-циклами и через N\ (к) количество различных (n,id)-циклов, проходящих через все вершины -к с нетривиальным СО-циклом и к нетривиальными CN-циклами. Обозначим убывающий факториал (п)к '■= п(п — 1)... (п — к + 1).

Список литературы диссертационного исследования кандидат наук Медведев Алексей Николаевич, 2016 год

Список литературы

[1] Компельмахер В.Л., Лисковец В.А. Последовательное порождение перестановок с помощью базиса транспозиций // Кибернетика. — 1975. — Т. 3. — С. 17-21.

[2] Константинова Е.В. О хроматическом числе некоторых графов Кэли // Труды VIII Международной конференции "Дискретные модели в теории управляющих систем".

— Москва: ФВМиК МГУ им. М. В. Ломоносова, 2009. — С. 149-155.

[3] An (18/11)n upper bound for sorting by prefix reversals / H. Sudborough, C. Chitturi, W. Fahle et al. // Theoretical Computer Science. — 2009. — Vol. 410, no. 36. — P. 3372-3390.

[4] Akers S.B., Krishnamurthy B. The star graph: an attractive alternative to n-cube // Proceedings of International Conference on Parallel Processing, ICPP-87. — St. Charles, Illinois: 1987. — P. 393-400.

[5] Akers S.B., Krishnamurthy B. A group-theoretic model for symmetric interconnection networks // IEEE Transactions on Computers. — 1989. — Vol. 38, no. 4. — P. 555-566.

[6] Alon N., Yuster R., Zwick U. Finding and counting given length cycles // Algorithmica.

— 1997. — Vol. 17, no. 3. — P. 209-223.

[7] Babai L. Automorphism Groups, Isomorphism, Reconstruction // Handbook of Combinatorics. — Cambridge, MA: MIT Press, 1996. — P. 1447-1540.

[8] Babai L., Seress A. On the diameter of cayley graphs of the symmetric group // Journal of Combinatorial Theory, Series A. — 1988. — Vol. 49, no. 1. — P. 175 - 179.

[9] Babai L., Seress A. On the diameter of permutation groups // European Journal of Combinatorics. — 1992. — Vol. 13. — P. 231-243.

[10] Bondy J.A, Simonovits M. Cycles of even length in graphs // Journal of Combinatorial Theory, Series B. — 1974. — Vol. 16, no. 2. — P. 97-105.

[11] Bounds on the diameter of Cayley graphs of the symmetric group / J. Bamberg, N. Gill, T.P. Hayes et al. // Journal of Algebraic Combinatorics. — 2014. — Vol. 40, no. 1. — P. 1-22.

[12] Bulteau L., Fertin G., Rusu I. Pancake Flipping is Hard // Mathematical Foundations of Computer Science 2012. — Berlin Heidelberg: Springer, 2012. — P. 247-258.

[13] Cibulka J. On average and highest number of flips in pancake sorting // Theoretical Computer Science. — 2011. — Vol. 412. — P. 822-834.

[14] Combinatorics of Genome Rearrangements / G. Fertin, A. Labarre, I. Rusu et al. — 1st edition. — The MIT Press, 2009.

[15] Computing the diameter of 17-pancake graph using a PC cluster / S. Asai, Y. Kounoike, Y. Shinano, K. Kaneko // LNCS. — 2006. — Vol. 4128. — P. 1114-1124.

[16] Dejter I.J., Serra O. Efficient dominating sets in Cayley graphs // Discrete Appl. Math.

— 2003. — Vol. 129. — P. 319-328.

[17] Distance distribution of nodes in star graphs / L. Wang, S. Subramanian, S. Latifi, P.K. Srimani // Applied Mathematics Letters. — 2006. — Vol. 19, no. 8. — P. 780-784.

[18] Dweighter H. E 2569 in: Elementary problems and solutions // Amer. Math. Monthly. — 1975. — Vol. 82, no. 1. — P. 1010.

[19] Erdos P., Renyi A. Probabilistic methods in group theory // J. Analyse Math. — 1965.

— Vol. 14. — P. 127-138.

[20] Even S., Goldreich O. The minimum-length generator sequence problem is NP-hard // Journal of Algorithms. — 1981. — Vol. 2, no. 3. — P. 311 - 313.

[21] Fill J.A., Pemantle R. Percolation, First-Passage Percolation and Covering Times for Richardson's Model on the n-Cube // The Annals of Applied Probability. — 1993. — Vol. 3, no. 2. — P. 593-629.

[22] Gates W.H., Papadimitriou C.H. Bounds for sorting by prefix-reversal // Discrete Mathematics. — 1979. — Vol. 27. — P. 47-57.

[23] Gilbert E.N. Gray Codes and Paths on the n-Cube // Bell System Technical Journal. — 1958. — Vol. 37, no. 3. — P. 815-826.

[24] Godsil C., Royle G. Algebraic Graph Theory. — Graduate Texts in Mathematics. Springer, 2001. — Vol. 207 of Graduate Texts in Mathematics.

[25] Gyori E., Turan G. Stack of Pancakes // Stud. Sci. Math. Hung. — 1978. — Vol. 13. — P. 133-137.

[26] Held M., Karp R.M. A Dynamic Programming Approach to Sequencing Problems // Journal of the Society for Industrial and Applied Mathematics. — 1962. — Vol. 10, no. 1.

— P. 196-210.

[27] Helfgott H., Seress A. On the diameter of permutation groups // Annals of Mathematics.

— 2014. — Vol. 179. — P. 611-658.

[28] Heydemann M.-C. Cayley graphs and interconnection networks // Graph Symmetry: Algebraic Methods and Applications / Ed. by Gena Hahn, Gert Sabidussi. — Dordrecht: Springer Netherlands, 1997. — P. 167-224.

[29] Hyedari M.H., Sudborough I.H. On the diameter of the pancake network // Journal of Algorithms. — 1997. — Vol. 25, no. 1. — P. 67-94.

[30] Joichi J.T., White D.E., Williamson S.G. Combinatorial Gray Codes // SIAM Journal on Computing. — 1980. — Vol. 9, no. 1. — P. 130-141.

[31] Jwo J.-S., Lakshmivarahan S., Dhall S.K. Embedding of cycles and grids in Star graphs // Journal of Circuits, Systems and Computers. — 1991. — Vol. 1, no. 1. — P. 43-74.

[32] Kanevsky A., Feng C. On the embedding of cycles in pancake graphs // Parallel computing.

— 1995. — Vol. 21. — P. 923-936.

[33] Kesten Harry. Percolation Theory and First-Passage Percolation // Ann. Probab. — 1987.

— 10. — Vol. 15, no. 4. — P. 1231-1271.

[34] Knuth D.E. The Art of Computer Programming, Volume 4, Fascicles 0-4. — 1st edition.

— Addison-Wesley Professional, 2009. — pp. 933.

[35] Konstantinova E. Some problems on Cayley graphs // Linear Algebra and its Applications.

— 2008. — Vol. 429, no. 11-12. — P. 2754-2769.

[36] Konstantinova E. Some Problems on Cayley Graphs. Famnit lecture notes. — University of Primorska Press, 2013. — P. 92.

[37] Kutnar K., Marusic D. Hamilton cycles and paths in vertex-transitive graphs—Current directions // Discrete Mathematics. — 2009. — Vol. 309, no. 17. — P. 5491 - 5500.

[38] Levenshtein V.I., Siemons J. Error graphs and the reconstruction of elements in groups // Journal of Combinatorial Theory, Series A. — 2009. — Vol. 116, no. 4. — P. 795-815.

[39] Lovasz L. Problem 11 in: Combinatorial structures and their applications // Proc. Calgary Internat. Conf., Calgary, Alberta. — Gordon and Breach, New York: 1969. — P. 243-246.

[40] Marusic D. Hamiltonian circuits in Cayley graphs // Discrete Mathematics. — 1983. — Vol. 46. — P. 49-54.

[41] Pak I., Radoicic R. Hamiltonian paths in Cayley graphs // Discrete Mathematics. — 2009.

— Vol. 309. — P. 5501-5508.

[42] Pevzner P.A. Computational Molecular Biology: An Algorithmic Approach (Computational Molecular Biology). — 1 edition. — A Bradford Book, 2000.

[43] Pyber L., Szabo E. Growth in finite simple groups of Lie type // J. Amer. Math. Soc. — 2016. — Vol. 29. — P. 95-146.

[44] Qiu K. Optimal broadcasting algorithms for multiple messages on the star and pancake graphs using minimum dominating sets // Congress. Numerantium. — 2006. — Vol. 181.

— P. 33-39.

[45] Rapaport-Strasser E. Cayley color groups and Hamilton lines // Scr. Math. — 1959. — Vol. 24. — P. 51-58.

[46] Sankoff D, El-Mabrouk N. Genome rearrangement // Current Topics in Computational Biology / Ed. by T. Jiang, T. Smith, Y. Xu, M. Zhang. — Cambridge, MA: MIT Press, 2002. — P. 135-155.

[47] Sheu J.J., Tan J.J.M., Chu K.T. Cycle embedding in pancake interconnection networks // Proc. 23rd Workshop on Combinatorial Mathematics and Computation Theory. — 2006.

— P. 85-92.

[48] Skiena S.S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, with programs by Steven Skiena and Anil Bhansali. — Reading: Addison-Wesley, 1990. — P. x + 334.

[49] Tchuente M. Generation of permutations by graphical exchanges // Ars Combin. — 1982.

— Vol. 14. — P. 115-122.

[50] Williams A. The Greedy Gray Code Algorithm // Algorithms and Data Structures: 13th International Symposium, WADS 2013, London, ON, Canada, August 12-14, 2013. Proceedings / Ed. by F. Dehne, R. Solis-Oba, J.-R. Sack. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2013. — P. 525-536.

[51] Williams A., Sawada J. Greedy Pancake Flipping // Electronic Notes in Discrete Mathematics. — 2013. — Vol. 44. — P. 357 - 362.

[52] Zaks S. A new algorithm for generation of permutations // BIT. — 1984. — Vol. 24. — P. 196-204.

Публикации автора по теме диссертации

[53] Константинова Е.В., Медведев А.Н. Циклы длины семь в Pancake графе // Дискретный Анализ и Исследование Операций. - 2010. - T. 17, № 5.- C. 46-55.

[54] Konstantinova E., Medvedev A. Small cycles in the Pancake graph // Ars Mathematica Contemporanea. - 2014. - Vol. 7. - P. 237-246.

[55] Konstantinova E.V., Medvedev A.N. Small cycles in the Star graph // Siberian Electronic Mathematical Reports. - 2014. - Vol. 11. - P. 906-914.

[56] Konstantinova E., Medvedev A. Independent even cycles in the Pancake graph and greedy Prefix-reversal Gray codes // Graphs and Combinatorics. - 2016 - doi: 10.1007/ s00373-016-1679-x, опубликована онлайн 2.02.2016.

[57] Medvedev A.N. The number of small cycles in the Star graph // Siberian Electronic Mathematical Reports. - 2016. - Vol. 13. - P. 286-299.

Тезисы и труды конференций

[58] Медведев А.Н. Характеризация циклов длины семь в Pancake графе // Материалы XLVIII Международной научной студенческой конференции «Студент и научно-технический прогресс»: Математика. - Новосибирск: Изд-во Новосиб. гос. ун-та, 2010.

- С. 168.

[59] Konstantinova E., Medvedev A. Algebraic representation of small cycles in the Pancake graph // Abstracts of the 7th Slovenian International Conference on Graph Theory, Bled, Slovenia, 19-25 2011. - Koper: UP FAMMIT & UP PINT, 2011. - P. 37.

[60] Медведев А.Н. О независимых циклах в Pancake графе // Материалы Юбилейной 50-й международной научной студенческой конференции «Студент и научно-технический прогресс»: Математика. - Новосибирск: Изд-во Новосиб. гос. ун-та, 2012. - С. 177.

[61] Константинова Е.В., Медведев А.Н., Савин М.Ю. Циклы малой длины в Star графе // «Дискретный анализ и исследование операций», Материалы конференции «DOOR-2013». - Новосибирск: Издательство Института Математики, 2013. - С. 108.

[62] Medvedev A. Prefix-reversal Gray codes // Symmetries of graphs and Networks IV and 2014 Phd Summer School in Discrete Mathematics, Rogla, Slovenia, June 29 - July 5, 2014. - Koper: UP FAMMIT & UP PINT, 2014. - P. 15-17.

[63] Medvedev A. On the number of cycles of small length in Star graph // Graphs and Groups, Cycles and Coverings, 2014: Abstracts of the Russian-Slovenian Workshop. - Novosibirsk: Sobolev Institute of Mathematics, 2014. - P. 22.

[64] Medvedev A. The distribution of cycles of length O(n) in the Star graph // Groups and Graphs, Algorithms and Automata, 2015: Abstracts of the International Conference and PhD Summer School. - Yekaterinburg: UrFU Publishing house, 2015. - P. 109.