Вернуться к списку примеров


Граф группы

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

Дадим интуитивное описание графа группы в соответствии с [1]. Пусть G - группа. Для простоты будем считать, что она имеет представление с двумя образующими элементами a и b. Установим взаимно однозначное соответствие между элементами g группы G и вершинами Pg графа группы G. Теперь соединим вершины графа ориентированными ребрами двух различных типов, соответствующих образующим элементам a и b (например, ребрами двух различных цветов Ca и Cb), по следующему правилу: если

g a = s,  g a-1 = t,  g b = u,  g b-1 = v,   

то проводим:

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

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

Graph:=function(G)
local elms, # список всех элементов группы
      gens, # список порождающих эл-тов группы
      graph,# описание графа группы
      i,    # индекс эл-тов группы
      k,    # номер цвета (порожд. эл-та группы)
      j;    # номер конца ребра цвета k с началом в вершине i
elms:=AsSSortedList(G);
gens:=GeneratorsOfGroup(G);
graph:=[];
for i in [1 .. Length(elms)] do
  for k in [1 .. Length(gens)] do
    j:=Position(elms, elms[i]*gens[k]);
    Append(graph, [[i,j,k]]);
  od;
od;
return graph;
end;

Вторая функция представляет полученный с помощью первой функции список в виде квадратной матрицы порядка |G|, в которой элемент aij равен k, если от вершины с номером i к вершине с номером j проведено ориентированное ребро цвета k, и нулю в противном случае. Заметим, что это менее экономичное хранение информации о графе группы, так как такая матрица содержит довольно много нулевых элементов.

Mat:=function(graph)
local l, n, mat, i,j, x;
l:=List(graph, x -> x[1]);
Append(l, List(graph, x -> x[2]));
n:=Maximum(l);
mat:=[];
for i in [1..n] do
  mat[i]:=[];
  for j in [1..n] do
    mat[i][j]:=0;
  od;
od;
for x in graph do
  mat[x[1]][x[2]]:=x[3];
od;
return(mat);
end;

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

gap> S:=SymmetricGroup(3);
Sym( [ 1 .. 3 ] )

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

gap> GeneratorsOfGroup(S);
[ (1,2,3), (1,2) ]
gap> AsSSortedList(S);
[ (), (2,3), (1,2), (1,2,3), (1,3,2), (1,3) ]

Теперь мы можем получить описание графа группы в виде списка:

gap> t:=Graph(S);
[ [ 1, 4, 1 ], [ 1, 3, 2 ], [ 2, 3, 1 ], [ 2, 4, 2 ], [ 3, 6, 1 ],
  [ 3, 1, 2 ], [ 4, 5, 1 ], [ 4, 2, 2 ], [ 5, 1, 1 ], [ 5, 6, 2 ],
  [ 6, 2, 1 ], [ 6, 5, 2 ] ]

а также в виде матрицы, которую удобно изобразить с помощью функции Display:

gap> m:=Mat(t);
[ [ 0, 0, 2, 1, 0, 0 ], [ 0, 0, 1, 2, 0, 0 ], [ 2, 0, 0, 0, 0, 1 ],
  [ 0, 2, 0, 0, 1, 0 ], [ 1, 0, 0, 0, 0, 2 ], [ 0, 1, 0, 0, 2, 0 ] ]
gap> Display(m);
[ [  0,  0,  2,  1,  0,  0 ],
  [  0,  0,  1,  2,  0,  0 ],
  [  2,  0,  0,  0,  0,  1 ],
  [  0,  2,  0,  0,  1,  0 ],
  [  1,  0,  0,  0,  0,  2 ],
  [  0,  1,  0,  0,  2,  0 ] ]

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

two graph drawings

[1] В.Магнус, А.Каррас, Д.Солитэр. Комбинаторная теория групп. М., Наука, 1974. 456 стр.



Вернуться к списку примеров