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

Акимов О.Е.

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

Виды графов

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

A(Г) = B*(Г) · B(Г) – d(v)E,

где E — единичная матрица, d(v) — степень вершины v регулярного графа Г, B*(Г) — транспонированная матрица инцидентности B(Г).

Схожую формулу имеет реберный граф. Граф Г_p называется реберным, если в качестве вершин выбраны ребра исходного графа Г с m ребрами и n вершинами, имеющего матрицу инцидентности B(Г). Матрица смежности реберного графа находится по формуле:

A(Г_p) = B(Г) · B*(Г) – 2E.

Исходный граф Г для построения реберного Г_p необязательно должен быть регулярным. Но если Г регулярный, то и реберный Г_p тоже будет регулярным. В общем случае, если ребро e_i в графе Г ограничено вершинами v_j и v_k, степень которых равна d(v_j) и d(v_k), то степень вершины ei в реберном графе Г_p определится формулой:

d(e_i) = d(v_j) + d(v_k) – 2.

Число ребер в реберном графе Г_p в общем, а не только регулярном случае, определяется следующим выражением:

m' = = .

Пусть дан регулярный граф Г (рис. 3.18). Его матрица инцидентности — B(Г), которую мы примем в своем расчете за исходную. По формулам находим A(Г) и A(Г_p), а также d(e_i) = 4, m' = 18.

B(Г) = ,    A(Г) = ,    A(Г_p) = .

Рис. 3.18

Граф называется плоским (планарным), если его можно уложить на плоскости так, чтобы его ребра нигде не пересекались, кроме как в вершинах. Имеется два основных непланарных графа — Г₅ и Г_3,3, изображение которых дано на рис. 3.19. Оба графа Г₅ и Г_3,3 являются регулярными, но последний относится еще и к так называемому двудольному, который определяется здесь как многозначное отображение трех верхних вершин на три нижние вершины, или наоборот. В общем случае в двудольном графе Г_д число вершин в обоих рядах может быть любым.

Рис. 3.19

Гиперграф — это такое обобщение простого графа, когда ребрами могут быть не только двухэлементные, но и любые подмножества вершин. Пусть заданы два множества: V = {v₁, v₂ ... v₉} — множество вершин, E = {e₁, e₂ ... e₆} — множество ребер. Тогда за гиперграф H(V, E) можно принять, например, следующее семейство подмножеств (рис. 3.20 слева):

Рис. 3.20

H(V, E) = {e₁, e₂, e₃, e₄, e₅, e₆} =
= {{v₁, v₂, v₃}, {v₂, v₄, v₅, v₆}, {v₆, v₇, v₈}, {v₃, v₈}, {v₉}, {v₆}}.

Любому гиперграфу H(V, E) можно поставить в соответствие двудольный граф Г_д(H) (рис. 3.20 справа).

В особый тип графов выделяются деревья. Дерево — это связанный граф, не имеющий циклов, так как любые две его вершины соединены простым путем. Число ребер в нем всегда на единицу меньше числа его вершин (m = n – 1). На рис. 3.21 изображены все 6 деревьев, которые могут быть построены на шести вершинах.

Рис. 3.21

Количество деревьев резко увеличится, если вершины как-нибудь пометить. Число помеченных деревьев и число других видов графов приведено в табл. 3.9.

Таблица 3.9

Виды графов   n	1	2	3	4	5	6
Деревья	1	1	1	2	3	6
Помеченные деревья	1	1	3	16	125	1296
Простые графы	1	2	4	11	34	156
Связанные простые графы	1	1	2	6	21	112
Эйлеровы простые графы	1	0	1	1	4	8
Гамильтоновы простые графы	1	0	1	3	8	48
Простые планарные графы	1	1	2	6	20	105
Простые орграфы	1	3	16	218	9608	1540944
Связанные простые орграфы	1	2	13	199	9364	1439822

Чтобы произвести идентификацию деревьев различной конфигурации производят упорядочение вершин по корневому признаку. Суть этой процедуры состоит в следующем. Из дерева Т удаляются все концевые вершины вместе с инцидентными им ребрами, т.е. вершины степени, равной единице. Так получается новое дерево Т₁. Затем из Т₁ вновь удаляются все концевые вершины; получается дерево Т₂. Эта процедура повторяется до тех пор, пока исходное дерево Т не сократится до единственной вершины, которая и называется корнем дерева Т. Если в результате удаления концевых вершин осталось две вершины, соединенные ребром, то за корень дерева принимается любая из этих вершин. Каждой вершине приписывается вес, т.е. число, соответствующее общему количеству вершин поддеревьев. Вершины, смежные с корнем дерева Т, рассматриваются как корни поддеревьев.

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

На рис. 3.22 приведено дерево вместе с указанием его веса вершин, которые удобно записать в следующем порядке:

Т(10, 4, 1, 2, 1, 5, 1 , 3, 1, 1).

Рис. 3.22