Операции на графах (стр. 2 из 5)
Рассмотрим выполнение операции пересечения для графов с несовпадающим множеством вершин.
Пусть G1(X1,E1) и G2(X2,E2) – графы без параллельных ребер, множества X1 и X2 вершин графов не совпадают, а A1 и A2 – матрицы смежности вершин графов. Для таких графов операция пересечения может быть выполнена так.
В соответствии с определением операции пересечения графов найдем множество вершин результирующего графа как X1ÇX2. Построим вспомогательные графы G’1 и G’2, множества вершин которых есть множество X1ÇX2, а множество ребер (дуг) определяется множествами E’1 и E’2 всех ребер (дуг), инцидентных этим вершинам. Очевидно, что матрицы A’1 и A’2 смежности вершин этих графов могут быть получены из матриц A1 и A2 путем удаления из них столбцов и строк, соответствующих вершинам, не вошедшим во множество X1ÇX2.
Применив к графам G’1 и G’2 теорему 2, найдем матрицу смежности вершин графа G’1ÇG’2 как A’1ÇA’2. Очевидно, что полученной матрице смежности вершин соответствует граф, множество вершин которого равно X1ÇX2, а множество ребер определяется, как E1ÇE2, что соответствует операции пересечения графов.
Пример 2. Выполнить в матричной форме операцию пересечения графов G1 и G2, представленных на рис. 2.
Составим матрицы смежности вершин исходных графов.
| x1 | x2 | x3 | x1 | x2 | x3 | x4 | ||||||
| x1 | 0 | 1 | 1 | x1 | 0 | 0 | 0 | 1 | ||||
| A1 | = | x2 | 1 | 0 | 1 | A2 | = | x2 | 1 | 0 | 1 | 1 |
| x3 | 0 | 1 | 0 | x3 | 1 | 0 | 0 | 0 | ||||
| x4 | 0 | 0 | 0 | 0 |
Находим множество вершин X результирующего графа.
X = X1ÇX2 = {x1, x2, x3}.
Составим матрицы смежности вершин вспомогательных графов G’1 и G’2.
| x1 | x2 | x3 | x1 | x2 | x3 | ||||||
| x1 | 0 | 1 | 1 | x1 | 0 | 0 | 0 | ||||
| A’1 | = | x2 | 1 | 0 | 1 | A’2 | = | x2 | 1 | 0 | 1 |
| x3 | 0 | 1 | 0 | x3 | 1 | 0 | 0 |
Найдем матрицу смежности вершин A = A1 Ç A2
| x1 | x2 | x3 | |||
| x1 | 0 | 0 | 0 | ||
| A’1ÇA’2 | = | x2 | 1 | 0 | 1 |
| x3 | 0 | 0 | 0 |
Полученная матрица смежности вершин A’1Ç A’2 соответствует графу G1ÇG2, изображенному на рис.2.
Композиция графов
Пусть G1(X,E1) и G2(X,E2) — два графа с одним и тем же множеством вершин X. Композицией G1(G2) графов G1и G2 называется граф с множеством вершин E, в котором существует дуга (xi,xj) тогда и только тогда, когда существует дуга (xi,xk), принадлежащая множеству E1, и дуга (xk,xj), принадлежащая множеству E2.
Рассмотрим выполнение операции композиции G1(G2) на графах, изображенных на рис.3. Для рассмотрения операции составим таблицу, в первом столбце которой указываются ребра (xi, xk), принадлежащие графу G1, во втором — ребра (xk, xj), принадлежащие графу G3, а в третьем — результирующее ребро (xi, xj) для графа G1(G2).
| G1 | G2 | G1(G2) |
| (x1,x2) | (x2,x1) (x2,x3) | (x1,x1) (x1,x3) |
| (x1,x3) | (x3,x3) | (x1,x3) |
| (x2,x1) | (x1,x1) (x1,x3) | (x2,x1) (x2,x3) |
Заметим, что дуга (x1,x3) результирующего графа в таблице встречается дважды. Однако, поскольку рассматриваются графы без параллельных ребер (дуг), то в множестве E результирующего графа дуга (x1,x3) учитывается только один раз, т.е. E = {(x1,x1), (x1,x3), (x2,x1), (x2,x3)}
На рис. 3 изображены графы G1 и G2 и их композиции G1(G2). На этом же рисунке изображен граф G2(G1). Рекомендуется самостоятельно построить граф G2(G1) и убедиться, что графы G1(G2) и G2(G1) не изоморфны.
Пусть А1 и A2 – матрицы смежности вершин графов G1(X,E1) и G(X,E2) соответственно. Рассмотрим матрицу A12элементы aij которой вычисляется так:
n
aij = Úa1ikÙa2kj (1)
k=1
где a1ikи a2kj – элементы матрицы смежности вершин первого и второго графов соответственно. Элемент aij равен 1, если в результирующем графе G1(G2) существует дуга, исходящая из вершины xi и заходящая xj, и нулю – в противном случае.
Пример 3. Выполнить операцию композиции для графов, представленных на рис. 3.
Составим матрицы смежности вершин графов:
| x1 | x2 | x3 | x1 | x2 | x3 | ||||||
| x1 | 0 | 1 | 1 | x1 | 1 | 0 | 1 | ||||
| A1 | = | x2 | 1 | 0 | 0 | A2 | = | x2 | 1 | 0 | 1 |
| x3 | 0 | 0 | 0 | x3 | 0 | 0 | 1 |
Вычислив элементы матрицы согласно (1), получаем:
| x1 | x2 | x3 | x1 | x2 | x3 | ||||||
| x1 | 1 | 0 | 2 | x1 | 0 | 1 | 1 | ||||
A12 | = | x2 | 1 | 0 | 1 | A21 | = | x2 | 0 | 1 | 1 |
| x3 | 0 | 0 | 0 | x3 | 0 | 0 | 0 |
Нетрудно убедиться, что полученным матрицам смежности вершин соответствуют графы G1(G2) и G2(G1), представленные на рис. 3.
Декартово произведение графов. Пусть G1(X,E1) и G2(Y,E2) — два графа. Декартовым произведением G1(X,E1)´G2(Y,E2) графов G1(X,E1) и G2(X,E2) называется граф с множеством вершин X´Y, в котором дуга (ребро), идущая из вершины (xiyj) в (xkyl), существует тогда и только тогда когда существует дуга (xixk), принадлежащая множеству дуг E1 и j = l или когда существует дуга (yj,yl), принадлежащая множеству E2 и i = k.
Выполнение операции декартова произведения рассмотрим на примере графов, изображенных на рис. 4. Множество вершин Z результирующего графа определяется как декартово произведение множеств X´Y. Множество Z содержит следующие элементы: z1=(x1y1), z2=(x1y2), z3=(x1y3), z4=(x2y1), z5=(x2y2), z6=(x2y3).
Определим множество дуг результирующего графа. Для этого выделим группы вершин множества Z, компоненты которых совпадают. В рассматриваемом примере пять таких групп: две группы с совпадающими компонентами из множества X, и три группы, имеющие совпадающие компоненты из Y. Рассмотрим группу вершин результирующего графа, которые имеют общую компоненту x1: z1=(x1y1), z2=(x1y1), z3=(x1y3). Согласно определению операции декартова произведения графов, множество дуг между этими вершинами определяется связями между вершинами множества Y. Таким образом, дуга (y1,y1) в графе G2 определяет наличие дуги (z1,z1) в результирующем графе. Для удобства рассмотрения всех дуг результирующего графа составим таблицу, в первом столбце которой перечисляются вершины с совпадающими компонентами, во втором – дуги между несовпадающими компонентами, а в третьем и четвертом – дуги в результирующем графе.