15.1.2. Виды графов

Определим смежностный (двойственный) граф G_S = (U, V), (обозначают также U(G)) для графа G = (X, U). Вершинами G_S являются ребра G, а ребрами G_S — пары (u_i, u_j). Для построения G_S по G на каждом ребре u_i  U графа G выбирают среднюю точку и считают ее вершиной u_i  U графа G_S (см. рис. 1.5). Таким образом, двойственный граф G_S будет иметь 12 вершин: U = {u₁, u₂, …, u₁₂}

Затем пару (u_i, u_j) соединяют ребром v_k = (u_i, u_j), если ребра u_i, u_j имеют общую вершину в G. То есть для графа G_S вершина u_1, например, будет иметь общие ребра с вершинами u₂, u₄, u₅, u₆, так как эти ребра в исходном графе G имели общие вершины (x₁ и x₂). В результате получим следующий двойственный граф G_S (рис. 15.6)

Рис. 15.5. Построение двойственного графа G_S

Рис. 15.6. Двойственный граф G_S

Следует отметить, что существуют различного рода матрицы и списки, производные от R и I, которые используются при записи алгоритмов.

Граф G называется конечным, если множества его вершин и ребер ─ конечные множества. Далее будем рассматривать конечные графы, так как модели объектов, представляемые графами, состоят из конечного числа элементов.

Граф G, у которого X  , а U = , называется нуль-графом, а его вершины ─ изолированными. Обозначается он G₀. Граф G = (X, U), |X| = n называется полным, если между любой парой вершин x_i, x_j  X имеется ребро u_k  U. Обозначается он K_n. Число ребер, инцидентных вершине x_i  X графа G, называется локальной степенью или просто степенью этой вершины и обозначается (x_i) или _i. Тогда число ребер графа G = (X, U), |X| = n, |U| = m,

. (15.1)

Заметим, что если в графе имеются петли, то каждая из них должна считаться дважды. Так как для полного графа на n вершин (x₁) = (x₂) = … = (x_n), то

m = n(n - 1) / 2. (15.2)

Графы с одинаковыми числами степеней называются регулярными. Регулярные графы степени 3 называются кубическими (трехвалентными). Примером кубического графа является граф Петерсона (рис. 15.7).

Рис 15.7. Граф Петерсона

Среди регулярных графов интерес представляют так называемые платоновы графы – графы, образованные вершинами и ребрами пяти правильных многогранников – платоновых тел:

• тетраэдра (рис. 15.8, а),

• куба (рис. 15.8, б),

• октаэдра (рис. 15.9, а),

• додекаэдра (рис. 15.9, б),

• икосаэдра (рис 15.9, в).

а б

Рис. 15.8. Тетраэдр (а), куб (б)

а б

Рис. 15.9. Октаэдр(а), додекаэдр (б),

в

Рис. 15.9. (окончание) икосаэдр (в)

Число ребер регулярного графа с локальной степенью (x_i) вершины x_i определяется как

m = n(x_i)/2. (15.3)

Заметим, что в графе каждое ребро соединяет две вершины и, следовательно, число вершин нечетной степени четно.

Полный граф K_1,n называется звездным. Он показан на рис 15.10.

Рис. 15.10. Пример звездного графа

Над графами можно выполнять следующие операции: объединение (), сложение (+) и произведение (*).

1. Объединением графов G(a) = (X(a), U(a)) и G(b) = (X(b), U(b)) называется граф G = (X, U), у которого X = (X(a)  X(b)), U = (U(a)  U(b)) (рис. 15.11).

Рис. 15.11. Операция объединения графов

2. Суммой графов G(a) = (X(a), U(a)) и G(b) = (X(b), U(b)) называется граф G = (X, U) который определяется объединением G(a) и G(b), и каждая вершина x_i  X(a), не вошедшая в пересечение X(a)  X(b), соединяется со всеми вершинами X(b) \ X(a)  X(b) и наоборот (рис. 15.12).

Рис. 15.12. Сумма графов

3. Произведением графов G(a) = (X(a), U(a)) и G(b) = (X(b), U(b)) называется граф G = (X, U) у которого X = X(a) × X(b), а ребра соответствуют связности подграфов (рис. 1.13).

Рис. 15.13. Произведение графов

Подграфом графа G называется граф, у которого все вершины и ребра принадлежат G, т.е. G’ = (X’, U’), подграф G = (X, U), если X’  X, U’  U и ребра U’ соединяют только вершины X’. Удаление из графа G = (X, U) вершины x_i со всеми инцидентными ей ребрами приводит к подграфу G’’ = (X’’, U’’), X’’ = X \ x_i. На рис. 15.14, а, b, c показаны граф G = (X, U) и два его подграфа, G1 = (X1, U1) и G2 = (X2, U2), где |X| = 7, |U| = 10, X = {x₁, x₂, …, x₇}, U = {u₁, u₂, …, u₁₀}; |X1| = 3, |U1| = 3, X1 = {x₁, x₂, x₄}, U1 = {u₁, u₇, u₆}; |X2| = 5, |U2| = 6, X2 = {x₂, x₃, x₅, x₆, x₇}, U2 = {u₂, u₃, u₄, u₈, u₉, u₁₀}. Заметим, что подграф G1 можно получить, удалив из G вершины x₃, x₅, x₆, x₇ с инцидентными им ребрами, а подграф G2, удалив из G вершины x₁, x₄ с инцидентными им ребрами.

a

G1 G2

б в

г д

Рис.15.14. Граф G(а) и его подграфы G1(б) и G2(в); суграф графа G(г); дополнение графа G(д)

Суграфом G’ = (X’, U’) графа G = (X, U) называется граф, для которого X’ = X, U’  U.

Граф называется дополнением графа G до полного, если он состоит из всех ребер полного графа K, не принадлежащих G, = K \ G. На рис. 15.14, г) показан суграф графа (см. рис. 15.14, в). На рис. 15.14, д) приведено дополнение графа G (см. рис. 15.14, в) до полного графа K₇.