О свойствах графов Кэли некоторых конечных групп Овчаренко Алёна Юрьевна

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

Актуальность темы исследования и степень ее разработанности. Графы Кэли (Caley graphs) и их различные приложения являются объектом интенсивных исследований в информатике, теории вычислительных систем и связи. Они используются при анализе и проектировании топологий (структур) вычислительных систем (ВС), а также протоколов работы распределенных алгоритмов. Одной из значимых областей применения графов Кэли в теории ВС является построение оптимальных структур сетей межмашинных связей. Под оптимальной структурой ВС понимается граф соединения элементарных машин системы, обеспечивающий экстремальные значения одного или нескольких показателей эффективности: диаметр графа, средний диаметр, вектор-функция структурной коммутируемости, вектор-функция структурной живучести. С 1970-х годов значительное развитие в теории оптимальных структур ВС получили циркулянтные графы (1)_п-графы), которые являются частным случаем графов Кэли [Воробьев В.А., 1974; Корнеев В.В., 1985; Евреинов Э.В., Хорошевский В.Г., 1978; Монахов О.Г., Монахова Э.А., 2000]. 1)_п-графы нашли практическую реализацию в проектах различных ВС: ILLIAC-IV, Intel Paragon, Cray T3D, семейство ВС с программируемой структурой МИКРОС, МВС. Несмотря на значимые теоретические и практические результаты в области построения эффективных структур ВС на базе графов Кэли, остается широкой круг задач, требующих своего решения. Одно из актуальных направлений — исследований перспективных свойств отдельных видов графов Кэли. В частности, теоретический и практический интерес представляет поиск и исследование целочисленных графов Кэли.

Графом Кэли Г = Cay(G,5') = (V, Е) на группе G относительно порождающего множества S называется граф с множеством вершин V = G и множеством рёбер Е = {(g,h) \ g,h Є G,g~^lh Є S}. Графы Кэли являются связными и регулярными степени \S\. Диаметр графа Кэли Г равен максимальному расстоянию между единичным элементом и любым д Є G, а также максимальной из длин наиболее коротких выражений элементов группы в виде произведения порождающих. Спектр графа Г определяется как множество характеристических корней матрицы смежности.

В силу определения, введённого Ф. Харари и А. Д. Швейком в работе «Which graphs have integral spectra?» [F. Harary, A.J. Schwenk, 1974], граф Г называется целочисленным, если его спектр состоит из целых чисел. В этой же работе они поставили задачу поиска целочисленных графов.

Количество целочисленных графов не только бесконечно, но такие графы встречаются среди графов произвольного порядка [К. Balinska, D. Cvetkovic, Z. Radosavljevic, S. Simic, and D. Stevanovi, 2002]. Тем не менее, они являются очень редкими и найти их достаточно трудно [О. Ahmadi, N. Alon, I. F. Blake, I. E. Shparlinski, 2009]. Более точно, в 2009 году О. Ахмади, Н. Алон, И. Ф. Блейк, И. Е. Шпарлински доказали, что вероятность того, что помеченный граф с вершинами будет целочисленным, не превосходит 2-П/400 д_ЛЯ достаточно больших . Эти результаты показывают, что поиск целочисленных графов стоит вести внутри конкретных семейств. К этой задаче, в свою очередь, можно подходить с двух сторон. Можно рассматривать семейства графов как таковых, например, графов с заданной максимальной степенью вершин или -регулярных графов. Такая работа велась, например, для кубических графов Ф. С. Бюссмакером и Д.М. Чветковичем [D. Cvetkovic, 1975], а также А. Д. Швенком [Schwenk A. J., 1976], которые доказали, что существует ровно 13 связных кубических целочисленных графов. С другой стороны, можно рассматривать графы, ассоциированные с семействами конечных групп, порождённых определёнными наборами порождающих. Это и есть графы Кэли, которые были определены выше. Именно этот подход представлен в настоящей работе.

Заметим, что не все графы являются графами Кэли каких-либо групп. Например, А. Абдоллахи и Е. Ватандуст [Abdollahi A., Vatandoost Е., 2009] показали, что среди упомянутых выше 13 связных кубических целочисленных графов только 7 являются графами Кэли.

На настоящий момент существует много интересных результатов о графах Кэли. Некоторые целочисленные графы Кэли на абелевых, диэдральных и циклических группах исследовались в [W. Klotz, Т. Sander, 2010; L. Lu, Q. Huang, X. Huang, 2018; S. M. Mirafzal, A. Zafari, 2017; W. So, 2005].

Приведём пример бесконечного семейства целочисленных графов Кэли. Обозначим через Sym_n группу всех биективных отображений множества {1, 2,... ,} на себя. Звёздный граф _n = (Sym_n,), ^ 2, который является графом Кэли на симметрической группе Sym_n относительно порождающего множества, состоящего из транспозиций вида = {(l) | 2 ^ ^ }, является связным двудольным ( - 1)-регулярным графом. Спектр звёздного графа целочисленный, более точно, для ) 2 и для любого целого 1 ^ ^ - 1 значения ±( - ) являются собственными значениями графа _n; если ^ 4, то 0 тоже является собственным значением графа _n. Поскольку звёздный граф является двудольным, для кратностей его собственных значений верно mul( - ) = mul(- + ) для любого целого 1 ^ ^ . В частности, ±( - 1) являются простыми (кратности один) собственными

значениями графа S_n. Целочисленность спектра звёздного графа S_n следует из изучения спектров элементов Юнга-Юциса-Мёрфи в групповой алгебре симметрической группы [G. Chapuy, V. Feray, 2012; R. Krakovski, В. Mohar, 2012; P. Renteln, 2011]. В [J. Friedman, 2000] исследовались вторые по минимальности неотрицательные собственные значения z^ графа Кэли на симметрической группе, порождённой транспозициями. Было доказано, что среди всех множеств из п — 1 транспозиции, порождающих симметрическую группу, множество, чей соответствующий граф Кэли имеет наибольшее ^2 = 1 — это множество Т. Это означает, что не существует других целочисленных графов Кэли на симметрической группе, порождённых множеством, состоящим из п — 1 транспозиции. Также стоит отметить, что до настоящего времени не было известно о существовании графов Кэли на симметрической группе с другими (отличными от упомянутого множества транспозиций) порождающими множествами.

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

На данный момент имеется много различных результатов, связанных с некоторыми частными случаями целочисленных графов. Например, важные результаты, касающиеся целочисленных графов, получены Чветковичем (1974, 1975, 1998), Швенком (1978), Симичем (1986, 1995, 1998, 2001, 2002), Балиншкой (1999, 2001, 2002, 2004) и другими. Ройтман (1984) построил бесконечное семейство целочисленных полных трёхдольных графов. Лепович (Lepovic, 2003, 2004) представил результаты о целочисленных графах, принадлежащих классам аК_а^ъ, аК_а U (ЗКъ или аК_а U (ЗКъ^ъ (подробнее об этих семействах см. в разделе 1.2). Ещё одним важным семейством графов, для которых рассматривалась указанная проблема, являются деревья. Это отражено в исследованиях Харари (1974), Швенка (1974, 1979), Ватанабе (1979), Ли (1987, 1999, 2000, 2002, 2004), Лю (1988), Чао (1988, 1991), Юаня (1998), Хика (1997, 1998, 2003), Ванга (1999, 2000, 2002, 2004) и других. В работе Овчаренко (2017) найдены примеры целочисленных графов Кэли знакопеременной группы А_п для некоторых п.

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

В соответствии с целью определены нижеследующие задачи исследования.

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

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

3. Реализовать алгоритмы в программном пакете генерации и исследования характеристик целочисленных графов Кэли.

4. При помощи разработанного инструментария выполнить поиск целочисленных графов Кэли.

5. Построить графы Кэли и целочисленные части их спектров для симметрических групп S_n при п = 3,4,5,6, знакопеременных групп А_п при п = 4,5,6,7,8, линейных групп ^(п) при п = 5,7,8,9,11,13, для групп диэдра D^n при п = 6,7,... ,132, а также других групп малых порядков в соответствии с п. 4.

6. Определить характеристики указанных графов, а именно, диаметры и средние диаметры в зависимости от порядка графа и степени вершин.

Научная новизна. Все результаты работы являются новыми.

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

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

9. Найдены новые семейства целочисленных графов Кэли, а именно:

знакопеременных групп А_п при п = 4,5,6,7,8, порождённых множеством 3-циклов вида (12г);

симметрических групп S_n при п = 3,4,5,6, порождённых набором всех транспозиций вида (ij) и набором всех инволюций;

линейных групп L/2(n) при п = 5,7,8,9,11,13, порождённых набором всех инволюций;

диэдральных групп D^n при п = 6,7,. .. ,132, также порождённых множеством всех инволюций.

4. Для других классических наборов порождающих знакопеременной
группы А_п при п = 4,5,6,7 определены целочисленные части спек
тра.

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

Теоретическая и практическая значимость работы.

10. Разработан алгоритм поиска целочисленных графов Кэли по заданному набору порождающих элементов конечной группы.

11. Создан алгоритм расчета характеристик целочисленных графов Кэли на основе рациональной арифметики произвольной точности.

12. Алгоритмы реализованы в программном пакете генерации и исследования характеристик целочисленных графов Кэли.

13. При помощи разработанного инструментария для графов Кэли знакопеременных групп А_п при п = 4,5,6,7,8, порождённых множеством 3-циклов вида (12г); других классических наборов порождающих знакопеременной группы А_п при п = 4,5,6,7; симметрических групп S_n при п = 3,4,5,6, порождённых набором всех транспозиций вида (ij) и набором всех инволюций; линейных групп ^(п) при п = 5,7,8,9,11,13, порождённых набором всех инволюций; диэд-ральных групп D^n при п = 6,7,... ,132, также порождённых множеством всех инволюций найдены:

целочисленные части спектра;

диаметры и средние диаметры;

5. Найдены новые семейства целочисленных графов Кэли, а именно,
на симметрической группе S_n, порождённой набором всех транспо
зиций или набором всех инволюций; на знакопеременной группе А_п,
порождённой множеством 3-циклов вида (12г); на любой конечной
группе, порождённой инвариантным множеством инволюций.

Практическая значимость определяется тем, что алгоритмы реализованы в виде пакета программ, написанного на языке программирования Python, на операционных системах Windows и Linux. Получено свидетельство о государственной регистрации программы для ЭВМ. Результаты работы внедрены в учебный процесс СибГУТИ: в курс лекций по дисциплине «Дискретная математика», раздел «теория графов», что подтверждается соответствующим актом.

Основные этапы исследования выполнены в ходе осуществления работ по проектам:

- НИОКТР АААА-А17-117041910201-1 «Алгоритмические задачи в информационных технологиях» (03/04/2017 - 29/12/2017, руководитель проекта д.ф.-м.н. профессор Лыткина Д.В.);

- НИОКТР АААА-А18-118041990034-0 «О графах Кэли как возможных графах межмашинных связей» (02/04/2018 - 29/12/2018 руководитель проекта д.ф.-м.н. профессор Лыткина Д.В.).

Результаты диссертационной работы используются в архитектурных решениях Сибирского Филиала Акционерного общества Коммерческого Банка «Модульбанк», а именно, в ускорении процесса обработки пользовательской информации, что подтверждается актом внедрения.

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

Положения и результаты, выносимые на защиту.

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

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

16. Создан программный пакет генерации и исследования характеристик целочисленных графов Кэли с числом вершин до 20160, что превосходит возможности пакета GAP в 5-8 раз.

17. При помощи разработанного инструментария определены новые семейства целочисленных графов Кэли, а также полные целочисленные части их спектров для:

симметрических групп S_n, порожденных набором всех транспозиций вида (ij) и набором всех инволюций для п = 3,4,5,6 (табл. );

знакопеременных групп А_п для п = 4,5,6,7,8, с различными наборами порождающих (табл. );

линейных групп L/2(n) для п = 5,7,8,9,11,13, порожденных набором всех инволюций (табл. );

групп диэдра D^n для п = 6,7,... ,132, порожденных набором всех инволюций (табл. );

— других конечных групп малых порядков, порождённых наборами всех инволюций (табл. ). 5. Для перечисленных выше групп и соответствующих графов Кэли

найдены диаметры и средние диаметры (табл. , , , ). Личный вклад. Все выносимые на защиту результаты принадлежат соискателю лично. В наиболее значимых работах, опубликованных в соавторстве с Д.В. Лыткиной, разработка методов решения поставленных задач осуществлялись при непосредственном участии соискателя, в частности, алгоритм, позволяющий определить целочисленность графа Кэли конечной группы по заданному набору порождающих, и его программная реализация полностью разработаны соискателем [1,3].

Степень достоверности и апробация результатов. Основные результаты работы докладывались и обсуждались на международных и всероссийских научных конференциях, в их числе:

Российская научно-техническая конференция «Обработка информации и математическое моделирование» («СибГУТИ», г. Новосибирск, 21-22 апреля, 2016г.).

Международная научная конференция «Мальцевские чтения» (Институт математики им. С.Л. Соболева СО РАН, г. Новосибирск, 21-25 ноября, 2016г.).

Российская научно-техническая конференция «Обработка информации и математическое моделирование» («СибГУТИ», г. Новосибирск, 26-27 апреля, 2017г.).

Международная научная конференция «Актуальные проблемы прикладной математики и физики» (г. Нальчик - Терскол, 17-21 мая, 2017).

Международная научная конференция «Groups and graphs, metrics and manifolds» (Уральский Федеральный Университет, г. Екатеринбург, 22-30 июля, 2017г.).

Российская научно-техническая конференция «Обработка информации и математическое моделирование» («СибГУТИ», г. Новосибирск, 26-27 апреля, 2018г.).

Публикации. По теме диссертации опубликовано 10 работ, из которых 3 работы входят в список ВАК и 5 работ из списка РИНЦ и получено 1 свидетельство о государственной регистрации программы для ЭВМ.

Доля личного вклада в работах, выполненных в соавторстве составляет не менее 50%.

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

источников, изложенных на 86 страницах, а также приложений на 11 страницах. Работа содержит 16 таблиц и 1 рисунок. Список литературы содержит 113 наименований.