Дискретная математика:
логика, группы, графы, фракталы

Акимов О.Е.

3.2. Морфология графа

Симметрия графа и его дополнения

Зададимся вопросом: какое число графов (N) возможно на n вершинах и m ребрах? Так, для n = 4 можно вычертить N = 11 принципиально различающихся графов (рис. 3.15).

Рис. 3.15

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

A(Г ' ) = J – A(Г),

где J — матрица смежности полного графа, состоящая полностью из единиц, за исключением элементов диагонали.

Два графа с m = 2 находятся в отношении дополнения с двумя графами, имеющими m = 4 и т.д. В табл. 3.7, где приведены количества графов с n вершинами и m ребрами, нетрудно заметить, что в пределах одного столбца возрастающая последовательность его чисел, достигая максимума, в точности повторяет его убывающую последовательность.

Таблица 3.7

m\n	1	2	3	4	5	6	7	8
0	1	1	1	1	1	1	1	1
1	–	1	1	1	1	1	1	1
2	–	–	1	2	2	2	2	2
3	–	–	1	3	4	5	5	5
4	–	–	–	2	6	9	10	11
5	–	–	–	1	6	15	21	24
6	–	–	–	1	6	21	41	56
7	–	–	–	–	4	24	65	115
8	–	–	–	–	2	24	97	221
9	–	–	–	–	1	21	131	402
10	–	–	–	–	1	15	148	663
11	–	–	–	–	–	9	148	980
12	–	–	–	–	–	5	131	1312
13	–	–	–	–	–	2	97	1557
14	–	–	–	–	–	1	65	1646
15	–	–	–	–	–	1	41	1557
N	1	2	4	11	34	156	1044	12344

Аналогичная симметрия взаимного дополнения имеет место и для орграфов (табл. 3.8).

Таблица 3.8

m\n	1	2	3	4
0	1	1	1	1
1	–	1	1	1
2	–	1	4	5
3	–	–	4	13
4	–	–	4	27
5	–	–	1	38
6	–	–	1	48
7	–	–	–	38
8	–	–	–	27
9	–	–	–	13
10	–	–	–	5
11	–	–	–	1
12	–	–	–	1
N	1	3	16	218

На рис. 3.16 изображены всевозможные вариации орграфов на трех вершинах (n = 3, N = 16).

Рис. 3.16

Любой граф обладает некоторыми свойствами симметрии. Граф и его дополнение всегда имеют одну и ту же группу симметрии. В частности, полный граф и его дополнение — пустой граф на n вершинах обладают симметрической группой S_n. Известно, что, например, в группе S₄ содержится подгруппа S₃, т.е. группа симметрии треугольника. На рис. 3.15 для m = 6 изображено два графа (треугольной формы взят в рамку) как раз для того, чтобы продемонстрировать это свойство полного графа на четырех вершинах.

Граф с меньшим числом ребер, чем у полного графа, имеет в качестве своей группы симметрии какую-нибудь подгруппу группы S_n. Например, группа приведенного на рис. 3.15 графа с числом ребер, равным m = 5, состоит из четырех элементов; если вершины графа пронумеровать соответствующим образом, то его группа выразится подстановками: a = (02), b = (13), c = (02)(13) и e = (0). Между тем, как нам известно, группа симметрии полного графа (m = 6) S₄ состоит из 24-х элементов (подстановки см. в табл. 2.54).

Каждый граф имеет для себя тождественную подстановку. Поэтому его группа симметрии имеет, по крайней мере, один элемент симметрии. Для нахождения группы G, которая порождается симметричным графом Г, используются подстановочные 0,1-матрицы. Если граф Г определяется матрицей смежности A(Г), то его группа симметрии G определяется теми подстановочными 0,1-матрицами M(G), которые коммутируют с матрицей смежности A(Г):

A(Г) · M(G) = M(G) · A(Г).

Так, для только что приведенного в качестве примера графа с n = 4, m = 5 (рис. 3.15) и подстановкой c = (02)(13) имеем:

· = · = .

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

Рис. 3.17

Пусть дан довольно сложный исходный граф Г; по нему находим более простой дополнительный граф Г ' (рис. 3.17). Затем отыскиваем несколько очевидных транспозиций; перемножая их между собой, определяем полную группу симметрии исходного графа Г. В конце по коммутационному соотношению проверяем справедливость одной из найденных подстановок.

a = (12), b = (37), c = (12)(37), d = (17)(23)(48), e = (1),

g = (1723)(48),   f = (13)(27)(48),   h = (1327)(48).

A(Г) · M(G) = · = =

= · = M(G) · A(Г).