A parallel algorithm for study of the Cayley graphs of permutation groups

Full Text

Определение графа Кэли было дано известным английским математиком Артуром Кэли в 1878 г. для представления алгебраической группы, заданной фиксированным множеством порождающих элементов. В последние десятилетия теория графов Кэли развивается как отдельная большая ветвь теории графов. Графы Кэли находят применение как в математике, так и за ее пределами. Заметим, что известная задача по определению так называемого числа Бога кубика Рубика 3^3x3, т. е. минимального количества поворотов граней кубика, за которое его можно собрать из любого начального положения, сводится к исследованию соответствующего графа Кэли [1]. Неожиданное применение графы Кэли нашли в информационных технологиях после пионерской работы 1986 г. С. Эйкерса и Б. Кришнамурти [2], которые впервые предложили применять указанные графы для представления компьютерных сетей, в том числе для моделирования топологий многопроцессорных вычислительных систем (МВС) - суперкомпьютеров. С тех пор данное направление активно развивается. Это связано с тем, что графы Кэли имеют много привлекательных свойств, из которых выделим их регулярность, вершинно-транзитивность, малые диаметр и степень при достаточно большом количестве вершин в графе. Кстати, такие базовые топологии сети, как «кольцо» и «гиперкуб», являются графами Кэли. Среди множества работ отдельно стоит отметить статью С. Шайбелла и Р. Стаффорда 1992 г. [3], в которой показано, что наряду с диаметром графа Кэли очень важное значение для производительности МВС имеет также средний диаметр графа. Для вычисления диаметра графа требуется решить ряд задач дискретной оптимизации. В первую очередь необходимо найти кратчайшие пути, связывающие все пары вершин в графе. Затем из всех кратчайших путей выбрать наибольший путь, длина которого и будет являться диаметром графа. Соответственно, средний диаметр графа будет равен среднему арифметическому всех длин кратчайших путей. Как известно, если граф задан в виде матрицы длин ребер, то задача по вычислению диаметра графа решается алгоритмом полиномиальной сложности. Специфика же графов Кэли такова, что в исходной ситуации известны только порождающие элементы и определяющие соотношения группы. Чтобы вычислить диаметр графа Кэли, необходимо решить следующие задачи дискретной оптимизации. Сначала требуется найти для каждого элемента группы минимальное слово, т. е. представить элемент в виде комбинации из образующих наименьшей длины, после чего вычислить максимальную длину минимальных слов, которая и будет являться диаметром графа Кэли. Поиск минимального слова в большой конечной группе является хотя и разрешимой, но достаточно сложной проблемой. Это связано с тем, что в общем случае задача по определению минимального слова в группе, а следовательно, и диаметра графа Кэли, как показали С. Ивен и О. Голдрейх в 1981 г., является NP-трудной [4]. Поэтому для эффективного решения задач оптимизации на графах Кэли, имеющих большое количество вершин, необходимо применять МВС. В связи с этим представляется актуальной проблема разработки параллельных алгоритмов для исследования графов Кэли частных классов групп. Основные определения и понятия Определение 1. Положим G - конечная группа и X с G. Множество X = (xp x2, ...,xm} называют порождающим множеством группы, а его элементы -порождающими и записывают G = (Xs), если любой элемент из G можно представить в виде конечного произведения из порождающих: G = (X) ^ Vg е G ^ g = а - а2 •... • as, где а, е X. Порождающее множество X называют также алфавитом, а порождающие элементы xi - буквами. 35 Математика, механика, информатика Определение 2. Пусть g элемент из G и g = a1 • a2 •... • as, где a; е X. Правую часть данного выражения мы будем называть словом и записывать a1a2...as. Множество всех слов над алфавитом X будем обозначать X *. Если необходимо подчеркнуть, что слово v е X* соответствует элементу g е G , то следует писать: vg. Очевидно, что фиксированное слово v соответствует только лишь одному элементу группы. Определение 3. Если два различных слова v = a1a2...ar и w = p1p2...ps представляют один элемент g группы G, т. е. g = a1a2...ar и g = P1P2...Ps, то выражение a1a2...ar = p1p2...ps (или vg = wg) называют соотношением в G. Определение 4. Положим v произвольное слово из X *. Количество букв, входящее в v, будем называть длиной слова v и обозначать length(v). Единица группы e будет представлена пустым словом, которое мы также обозначим e. По определению length(e) = 0. На множестве порождающих введем отношение порядка « X »: {x1 X Х2 X ... X xm }. Определение 5. Пусть v и w произвольные слова из X*. Будем говорить, что слово v = a1a2...ar меньше слова w = P1P2...Ps и записывать v X w , если имеет место одно из следующих утверждений: 1) r < s; 2) если r = s , тогда a1 = P1, a2 = P2, ..., ak-1 = pk-1, ak X pk для некоторого 1 < k < s. Данный способ упорядочивания элементов называют также лексикографическим. Определение 6. Слово v будем называть минимальным в G относительно введенного порядка, если для любого другого слова w, удовлетворяющего условию vg = wg, будет выполняться v X w . Определение 7. Длиной length(g, X) элемента g в алфавите X будем называть длину минимального слова vg е X *, представляющего данный элемент, т. е. length(g, X) = min{length(vg )| vg е X}. Определение 8. Диаметром diam(G, X) группы G относительно порождающего множества X будем называть максимальную длину элементов данной группы. Другими словами: diam(G, X) = max{length(g, X) | g е G }, или diam(G, X) = max{min{length(vg) I vg е X* } | g е G }. Определение 9. Пусть G = (X). Шаром Kr(G, X) радиуса r группы G относительно X будем называть множество Kr(G, X) = { g е G | length(g,X) < r}. Таким образом, шар Kr(G, X) радиуса r представляет собой все элементы группы G, длины которых относительно порождающего множества X не превышают r. Определение 10. Функция роста growth (G, X, r) группы G = (X) от аргумента r е{0}UN задается соотношением growth (G, X ,0) = 1 и growth(G, x, r) = = |Kr (G, X)| - |Kr-1 (G, X) при r е N . Это означает, что каждое значение функции роста growth (G, X, r) равно числу элементов группы G = (X} фиксированной длины r. Определение 11. Средним диаметром diam (G, X) конечной группы G будем называть среднюю длину ее элементов в алфавите X. Другими словами: Y, lenght (g, X) diam (G, X ) = ^ diam(G, X) Y growth (G, X, r)• r = r=0_ " lGl Определение 12. Графом Г = (V, E) называют совокупность двух множеств - множества вершин V = {v1,v2, ...,vm} и множества ребер E = {e1,e2, ...,en}, где каждое ребро из E определяется неупорядоченной парой вершин {vi, vg}. Отметим, что приведенная выше формулировка определяет неориентированный граф. Если же каждое ребро графа задается упорядоченной парой (vi, vg) вершин, то такой граф называют ориентированным. Далее под графом будем понимать неориентированный граф. Пусть v1 и v2 - вершины графа, e1 -соединяющее их ребро. Тогда вершина v1 и ребро e1 инцидентны, ребро e1 и вершина v2 также инцидентны. Два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными. Степенью вершины называют число инцидентных ей ребер. Граф называют регулярным степени k, если каждая его вершина имеет степень k. Порядок графа определяется числом его вершин |V\. Определение 13. Автоморфизмом графа Г = (V, E) называется отображение ф множества вершин на себя, сохраняющее смежность, т. е. если {u, v} е E, то будет верно {ф(и), ф(у)} е E. Определение 14. Граф Г = (V, E) называют вершинно-транзитивным, если для любых двух вершин u,v еV существует автоморфизм ф, при котором ф(u) = v. Определение 15. Маршрутом в графе Г = (V, E) называют последовательность вершин и ребер из Г 36 Вестник СибГАУ. № 1(53). 2014 в которой любые два соседних элемента инцидентны, причем однородные элементы (вершины, ребра) через один смежны или совпадают. Число ребер маршрута p называют его длиной. Если все ребра различны, то маршрут называют цепью. Граф является связным, если между любыми его двумя вершинами существует маршрут. Определение 16. Расстоянием d (u, v) между вершинами u и v в графе Г будем называть длину кратчайшей цепи, связывающей эти две вершины. Определение 17. Диаметром diam(f) графа Г называется расстояние между двумя наиболее удаленными вершинами в графе, т. е. diam(Г) = max{d(u, v) | u,v еV}. (1) Определение 18. Средним диаметром diam(T) конечного непустого графа Г = (V, E) будем называть среднее расстояние между его вершинами. Другими словами: Y d(u,v) diam(H = -. (2) lVl Определение 19. Пусть X - порождающее множество группы G, т. е. G = ( X}. Графом Кэли Г = Cay (G, X) = (V, E) называют ориентированный граф, обладающий следующими свойствами: 1) множество вершин V(T) соответствуют элементам группы G; 2) множество ребер Е(Г) состоит из всех упорядоченных пар (g, xg), где g е G и x е X. В дальнейшем будем считать порождающее множество X симметричным и свободным от единичного элемента группы, т. е. x е X ^ x- е X и e g X. Поскольку X является свободным от единичного элемента, то граф Г не содержит петель. Симметричность порождающего множества означает, что граф будет неориентированным и без кратных ребер, т. е. если в графе имеется ребро из g в xg, то оно совпадает с ребром из xg в x (xg) = g . Таким образом, Г = Cay(G, X) = (V, E), где V = G и E = {{g, x g}| g е G, x е X}. Последовательный алгоритм A-I В настоящем разделе будет представлен базовый алгоритм A-I для вычисления характеристик графа Кэли конечной группы, заданной фиксированным порождающим множеством. Для обоснования корректности алгоритма А-I докажем сначала вспомогательные утверждения. Лемма 1. Пусть G = (X) и Г = Cay (G,X) - граф Кэли группы G относительно X. Тогда (i) Г является связным ^-регулярным графом; (ii) Г является вершинно-транзитивным графом; (iii) Vg, h е G d (g, h ) = length (hg-1, X); (iv) diam(Г) = diam (G, X ) ; (v) diam(T) = diam(G, X). Доказательство. (i) Так как X является порождающим множеством группы G, то граф Г является связным, а в связи с тем, что X - симметричное порождающее множество, то каждая вершина в Г имеет степень, равную |X|. Поэтому Г является связным ^-регулярным графом. (ii) Если u и v две произвольные смежные вершины в Г, то v = xu для некоторого x е X . Отсюда следует, что для смежных вершин всегда найдется такой элемент x е X, что vu- = x. Обратно, если u и v не являются смежными, то vu-1 g X . На множестве вершин из Г рассмотрим отображение фh такое, что ф^) = gh. Докажем, что фh сохраняет смежность, т. е. если u и v две смежные вершины, то фh(u) и ф^) также будут являться смежными. Действительно, фА (v)фA (u) 1 = vh (uh) 1 = vhh~1u~1 = vu- е X . Если же u и v не являются смежными, то будет выполняться фh (v)фА (u )1 g X, поэтому вершины ф^) и фh(v) также не будут являться смежными. Так как отображение фh сохраняет смежность, то оно будет являться автоморфизмом графа Г. Положим h = u~xv . Тогда фh (u) = ф ,v (u) = uu~lv = v. Следовательно, Г является вершиннотранзитивным графом. (iii) Пусть g и h - произвольные вершины в Г. Согласно (i) данный граф является связным, а значит, существует путь, связывающий эти вершины. Предположим, что кратчайший путь имеет следующий вид: g, a1g , a2a1g , ..., as ...a^g (at е X), т. е. d(g, h) = s . С другой стороны, as...a2a1 = hg-1, следовательно, length (hg_1, X) = s. Таким образом, между длинами элементов группы G и кратчайшими цепями в графе Г имеется взаимно однозначное соответствие, в частности, имеет место равенство Vg, h е G ^ d (g, h) = length (hg-1, X). (3) (iv) Запишем формулу (1) с учетом (3): diam (Г) = max{d (g, h) |g, h е G} = = max{length (hg_1, X )hg-1 е G} = diam (G, X ) (v) Согласно (ii) граф Кэли является вершиннотранзитивным, и для любых двух его вершин u и v будет выполняться Yd (u, v) = Yd (u, v) . (4) vеV ueV С учетом (4) перепишем формулу (2): _ Y d (^ v) |V| Yd (u,v) Yd (u,v) diam (Г ) = -. 1 ^ |v| 2 |V|2 \V\ Пусть u = e - единица G. Поскольку V = G, а также в силу (3), получим 37 Математика, механика, информатика diam (Г) = - Y d (e, v) Y length (g,X) gеG |G| = diam (G, X). 5. Если 6. Если Беря во внимание свойства (ii) и (iii) вышеприведенной леммы, мы можем определить функцию роста графа Кэли growth(Г, r) = growth (G, X, r), которая задает количество вершин в графе, удаленных от любой заданной вершины на расстояние r. Ниже представлен последовательный алгоритм для исследования графов Кэли конечных групп. Данный алгоритм можно распараллелить для эффективной реализации на МВС. Вход: G = (G, •) - конечная группа и X = {x1 X x2 X... X xm} - упорядоченное порождающее множество G. Выход: диаметр diam(r), средний диаметр diam (Г) графа Кэли Г = Cay(G, X), а также функция роста графа growth(r) = growth^, r), 0 < r < diam (Г). 1. s = 0, Ks = Ks (G, X) = {e} - шар группы G, T = K. 2. s = s+1, Ks = Ks_\, U = x1 • T u x2 • T...u xm • T -лексикографически упорядоченное множество. 3. T = 0 , i = 1. 4. Если ut g Ks, то Ks = Ks u ut, T = T u ut. I i < |v| , то i = i +1, переход в пункт 4; [i = |v| , то переход в пункт 6. [T ^0, то переход в пункт 2; [T = 0, то переход в пункт 7. 7. diam(r) = s -1, growth (r) = |Kr| - |Kr-1| для s-1 Y growth (r )• r 1 < r < s-1 и growth(0) = 1, diam (Г) = --:-j-. |Ks-11 Возврат полученных значений. Теорема. Алгоритм A-I корректен, т. е. для любой конечной группы он за конечное число шагов находит характеристики соответствующего графа Кэли. Доказательство. По построению A-I выражает каждый элемент группы G в виде уникального минимального слова. После каждого прохода от пункта 2 до пункта 6 множество Ks будет представлять собой шар радиуса s группы G в алфавите X. Поскольку количество элементов группы конечно, то через конечное число шагов все g е G будут записаны в формате минимальных слов, длины которых меньше s: Vg е G ^3!ug е Ks-1 ^ Vvg g ^ ^ ug X vg . Это означает, что diam (G, X) = s -1 и Ks-1 однозначно определяет функцию роста группы G в алфавите X. Как было сказано, growth (Г, r) = growth (G, X, r). По лемме 1 диаметр и средний диаметр графа Кэли Г группы G = (X} равны соответствующим характеристикам G. Теорема доказана. Параллельная версия алгоритма A-I для графов групп подстановок Для увеличения скорости вычислений алгоритм A-I можно распараллелить следующим образом. Множество Ks(Sn, Xn) разбивается на m=n(n-1)(n -2). (n -k+1) непересекающихся классов элементов (подстановок): m Ks = U K, K n kj = 0 при i * j. i=1 Каждый класс Ki будет однозначно определяться фиксированным набором значений (i1, i2, ., ik), т. е. (12... k... n Vg е Ki ^ g = 1 . . . . Ih ^2...lk...l„ Аналогичным образом массив U при каждом s также делится на m непересекающихся классов элементов: m U = UU- , Ui n Uj =0 при i * j, i=1 и дальнейшая обработка данных для каждой пары множеств Ui и Ki (пункты 4-5 алгоритма A-I) производится независимо. Нетрудно заметить, что рассмотренное разделение массивов не влияет на корректность работы алгоритма. Параметр k определяется экспериментально и зависит от строения группы, а также от характеристик МВС. Таким образом, представленный выше параллельный алгоритм, как показали вычисления на МВС [5], дает существенный прирост скорости вычислений. В будущем на основе данного алгоритма планируется провести серию экспериментов по исследованию графов Кэли различных классов групп с целью поиска перспективных топологий для МВС.

About the authors

Alexander Alexeevich Kuznetsov

Siberian State Aerospace University named after academician M. F. Reshetnev

Email: kuznetsov@sibsau.ru
Doctor of Phisical and Mathematical Sciences, associate professor, Leading Researcher

Alexandra Sergeevna Kuznetsova

Siberian State Aerospace University named after academician M. F. Reshetnev

Email: alexakulch@rambler.ru
Research Scientist

References

Supplementary files