Реферат: Операции на графах
БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
Кафедра информатики
РЕФЕРАТ
На тему:
«Операции на графах»
МИНСК, 2008
Операции на графах позволяют образовывать новые графы из нескольких более простых. В этом параграфе будут рассмотрены операции на графах без параллельных ребер (дуг).
Объединение графов .
Пусть G1 (X1 ,E1 ) и G2 (X2 ,E2 ) – произвольные графы. Объединением G1 È G2 графов G1 и G2 называется граф с множеством вершин X1 È X2, и с множеством ребер (дуг) E1 È E2 .
Рассмотрим операцию на примере графов G1 (X1 ,E1 ) и G2 (X2 ,E2 ), приведенных на рис. 4.1. Множества вершин первого и второго графов соответственно равны X1 = {x1, x2, x3 } и X2 = {x2, x3, x4 }, а множество вершин результирующего графа определится как X = X1 È X2 = {x1, x2, x3, x4 }. Аналогично определяем множества дуг графа:
E1 = {(x1, x2 ), (x1, x3 ), (x2, x1 ), (x3, x3 )}. E2 = {(x2, x4 ), (x3, x2 ), (x4, x2 )}.
E = {(x1, x2 ), (x1, x3 ), (x2, x1 ), (x3, x3 ), (x2, x4 ), (x3, x2 ), (x4, x2 )}.
Результирующий граф G(X,E) = G1 (X1 ,E1 ) ÈG2 (X2 ,E2 ) также приведен на рис. 1.
Операция объединения обладает следующими свойствами, которые следуют из определения операции и свойств операций на множествах:
G1 È G2 = G2 È G1 – свойство коммутативности;
G1 È (G2 È G3 ) = (G1 È G2 ) È G3 – свойство ассоциативности.
Операция объединения графов может быть выполнена в матричной форме. Для графов с одним и тем же множеством вершин справедлива следующая теорема.
Теорема 1. Пусть G1 и G2 – два графа (ориентированные или не ориентированные одновременно) с одним и тем же множеством вершин X, и пусть A1 и A2 – матрицы смежности вершин этих графов. Тогда матрицей смежности вершин графа G1 È G2 является матрица A = A1 È A2, образованная поэлементным логическим сложением матриц A1 и A2 .
Рассмотрим выполнение операции объединения графов, множества вершин которых не совпадают. Пусть G1 (X1 ,E1 ) и G2 (X2 ,E2 ) – графы без параллельных ребер и множества X1 и X2 вершин этих графов не совпадают. Пусть A1 и A2 – матрицы смежности их вершин графов. Для таких графов операция объединения может быть выполнена следующим образом.
В соответствии с определением операции объединения графов найдем множество вершин результирующего графа как X1 È X2. Построим вспомогательные графы G’1 иG’2, множества вершин которых есть множество X1 È X2, а множество ребер (дуг) определяется множествами E1 для графа G ’ 1 и E2 для графа G ’ 2. Очевидно, что матрицы A’1 и A’2 смежности вершин этих графов могут быть получены из матриц A1 и A2 путем добавления в них дополнительных столбцов и строк с нулевыми элементами.
Применив к графам G’1 и G’2 теорему 4.1, найдем матрицу смежности вершин графа G’1 È G’2 как A’1 È A’2. Очевидно, что полученной матрице смежности вершин соответствует граф, множество вершин которого равно X1 È X2, а множество ребер определяется, как E1 È E2, что соответствует операции объединения графов.
Пример 1. Выполнить в матричной форме операцию объединения графов G1 и G2, представленных на рис. 1.
Составим матрицы смежности вершин графов.
x1 | x2 | x3 | x2 | x3 | x4 | ||
x 1 | 1 | 1 | x2 | 1 | |||
A1 | = | x2 | 1 | A2 | = | x3 | 1 |
x3 | 1 | x4 | 1 |
Множество вершин результирующего графаX1 È X2 = {x1, x2, x3, x4 }. Составим матрицы смежности вершин вспомогательных графов G’1 иG’2 .
x1 | x2 | x3 | x4 | x1 | x2 | x3 | x4 |
x1 | 1 | 1 | x1 | ||||
A’1 | = | x2 | 1 | A’2 | = | x2 | 1 |
x3 | 1 | x3 | 1 | ||||
x4 | x4 | 1 |
Матрица A = A’1 È A’2 имеет вид
X1 | x2 | x3 | x4 | |
x1 | 1 | 1 | ||
x2 | 1 | 1 | ||
A = A’1 È A’2 | = | x3 | 1 | 1 |
x4 | 1 |
Полученная матрица смежности вершин A’1 È A’2 соответствует графу G1 È G2, изображенному на рис.1.
Пересечение графов
Пусть G1 (X1 ,E1 ) и G2 (X2 ,E2 ) – произвольные графы. Пересечением G1 Ç G2 графов G1 и G2 называется граф с множеством вершин X1 Ç X2 с множеством ребер (дуг) E = E1 Ç E2
Операция пересечения обладает следующими свойствами, которые следуют из определения операции и свойств операций на множествах:
G1 Ç G2 = G2 Ç G1 – свойство коммутативности;
G1 Ç (G2 Ç G3) = (G1 Ç G2) Ç G3 – свойство ассоциативности.
Для того чтобы операция пересечения была всеобъемлющей, необходимо ввести понятие пустого графа. Граф G(X,E) называется пустым, если множество X вершин графа является пустым (X= Æ ). Заметим, что в этом случае и множество E ребер (дуг) графа также пустое множество (E= Æ ). Пустой граф обозначается символом Æ. Такой граф может быть получен в результате выполнения операции пересечения графов, у которых X 1 Ç X 2 = Æ . В этом случае говорят о непересекающихся графах.
Рассмотрим выполнение операции пересечения графов, изображенных на рис. 2. Для нахождения множества вершин результирующего графа запишем множества вершин исходных графов и выполним над этими множествами операцию пересечения:
X1 = {x1, x2, x3 }; X2 = {x1, x2, x3, x4 };
X = X1 Ç X2 = {x1, x2, x3 }.
Аналогично определяем множество E дуг результирующего графа:
E1 = {(x1, x2 ), (x1, x3 ), (x2, x1 ), (x2, x3 ), (x3, x2 )};
E2 = {(x1, x3 ), (x2, x1 ), (x2, x3 ), (x2, x4 ), (x3, x1 )};
E = E1 Ç E2 = {(x1, x3 ), (x2, x1 )}.
Графы G1 (X1 ,E1 ), G2 (X2 ,E2 ) и их пересечение приведены на рис 4.2.
Операция пересечения графов может быть выполнена в матричной форме.
Теорема 2. Пусть G1 и G2 – два графа (ориентированные или неориентированные одновременно) с одним и тем же множеством вершин X, и пусть A1 и A2 – матрицы смежности вершин этих графов. Тогда матрицей смежности вершин графа G1 Ç G2 является матрица A = A1 Ç A2 образованная поэлементным логически умножением матриц A1 и A2 .
Рассмотрим выполнение операции пересечения для графов с несовпадающим множеством вершин.
Пусть 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 | 1 | 1 | x1 | 1 | ||||||
A1 | = | x2 | 1 | 1 | A2 | = | x2 | 1 | 1 | 1 |
x3 | 1 | x3 | 1 | |||||||
x4 |
Находим множество вершин X результирующего графа.
X = X1 Ç X2 = {x1, x2, x3 } .
Составим матрицы смежности вершин вспомогательных графов G’1 и G’2 .
x1 | x2 | x3 | x1 | x2 | x3 | ||||
x1 | 1 | 1 | x1 | ||||||
A’1 | = | x2 | 1 | 1 | A’2 | = | x2 | 1 | 1 |
x3 | 1 | x3 | 1 |
Найдем матрицу смежности вершин A = A1 Ç A2
x1 | x2 | x3 | ||
x1 | ||||
A’1 Ç A’2 | = | x2 | 1 | 1 |
x3 |
Полученная матрица смежности вершин 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 = Ú a 1 ik Ù a 2 kj (1)
k=1
где a1ik и a2kj – элементы матрицы смежности вершин первого и второго графов соответственно. Элемент aij равен 1, если в результирующем графе G1 (G2 ) существует дуга, исходящая из вершины xi и заходящая xj , и нулю – в противном случае.
Пример 3. Выполнить операцию композиции для графов, представленных на рис. 3.
Составим матрицы смежности вершин графов:
x 1 | x2 | x3 | x1 | x2 | x3 | |||
x1 | 1 | 1 | x1 | 1 | 1 | |||
A1 | = | x2 | 1 | A2 | = | x2 | 1 | 1 |
x3 | x3 | 1 |
Вычислив элементы матрицы согласно (1), получаем:
x1 | x2 | x3 | x1 | x2 | x3 | ||||
x1 | 1 | 2 | x1 | 1 | 1 | ||||
A12 | = | x2 | 1 | 1 | A21 | = | x2 | 1 | 1 |
x3 | x3 |
Нетрудно убедиться, что полученным матрицам смежности вершин соответствуют графы 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, в котором дуга (ребро), идущая из вершины (xi yj ) в (xk yl ), существует тогда и только тогда когда существует дуга (xi xk ), принадлежащая множеству дуг E1 и j = l или когда существует дуга (yj ,yl ), принадлежащая множеству E2 и i = k.
Выполнение операции декартова произведения рассмотрим на примере графов, изображенных на рис. 4. Множество вершин Z результирующего графа определяется как декартово произведение множеств X ´ Y. Множество Z содержит следующие элементы: z1 =(x1 y1 ), z2= (x1 y2 ), z3 =(x1 y3 ), z4 =(x2 y1 ), z5 =(x2 y2 ), z6 =(x2 y3 ) .
Определим множество дуг результирующего графа. Для этого выделим группы вершин множества Z, компоненты которых совпадают. В рассматриваемом примере пять таких групп: две группы с совпадающими компонентами из множества X, и три группы, имеющие совпадающие компоненты из Y. Рассмотрим группу вершин результирующего графа, которые имеют общую компоненту x1: z1 =(x1 y1 ), z2= (x1 y1 ), z3 =(x1 y3 ). Согласно определению операции декартова произведения графов, множество дуг между этими вершинами определяется связями между вершинами множества Y. Таким образом, дуга (y1 ,y1 ) в графе G2 определяет наличие дуги (z1 ,z1 ) в результирующем графе. Для удобства рассмотрения всех дуг результирующего графа составим таблицу, в первом столбце которой перечисляются вершины с совпадающими компонентами, во втором – дуги между несовпадающими компонентами, а в третьем и четвертом – дуги в результирующем графе.
№ п.п. | Группы вершин с совпадающими компонентами | Дуги для несовпадающих компонент | Дуга ( xi yj ) ® (xk yl ) | Дуга ( z a ,z b ) |
1 | z1 =(x1 y1 ), z2= (x1 y2 ), z3 =(x1 y3 ) | (y1 ,y1 ) (y1 ,y2 ) (y2 ,y3 ) (y3 ,y1 ) | (x1 y1 ) ® (x1 y1 ) (x1 y1 ) ® (x1 y2 ) (x1 y2 ) ® (x1 y3 ) ( x1 y3 ) ® (x1 y1 ) | (z1 ,z1 ) (z1 ,z2 ) (z2 ,z3 ) (z3 ,z1 ) |
2 | z4 =(x2 y1 ), z5 =(x2 y2 ), z6 =(x2 y3 ) | (y1 ,y1 ) (y1 ,y2 ) (y2 ,y3 ) (y3 ,y1 ) | (x2 y1 ) ® (x2 y1 ) (x2 y1 ) ® (x2 y2 ) (x2 y2 ) ® (x2 y3 ) (x2 y3 ) ® (x2 y1 ) | (z4 ,z4 ) (z4 ,z5 ) (z5 ,z6 ) (z6 ,z4 ) |
3 | z1 =(x1 y1 ), z4 =(x2 y1 ) | (x1 ,x2 ) (x2 ,x1 ) | ( x1 y1 ) ® (x2 y1 ) ( x2 y1 ) ® (x1 y1 ) | (z1 ,z4 ) (z4 ,z1 ) |
4 | z2= (x1 y2 ), z5 =(x2 y2 ) | (x1 ,x2 ) (x2 ,x1 ) | ( x1 y2 ) ® (x2 y2 ) ( x1 y2 ) ® (x1 y2 ) | (z2 ,z5 ) (z5 ,z2 ) |
5 | Z3 =(x1 y3 ), z6 =(x2 y3 ) | (x1 ,x2 ) (x2 ,x1 ) | ( x1 y3 ) ® (x2 y3 ) ( x2 y3 ) ® (x1 y3 ) | (z3 ,z6 ) (z6 ,z3 ) |
Граф G1 ´ G2 изображен на рис. 4.
Операция декартова произведения обладает следующими свойствами.
1. G1 ´ G2 = G2 ´ G1
2. G1 ´ (G2 ´ G3 ) = (G1 ´ G2 ) ´ G3 .
Операция декартова произведения графов может быть выполнена в матричной форме.
Пусть G1 (X,E1 ) и G2 (Y,E2 ) – два графа, имеющие nx и ny вершин соответственно. Результирующий граф G1 ´ G2 имеет nx × ny вершин, а его матрица смежности вершин — квадратная матрица размером (nx × ny ) ´ (nx × ny ). Обозначим через a a b = a(ij)(kl) элемент матрицы смежности вершин, указывающий на наличие дуги (ребра), соединяющей вершину z a =(xi yj ) c z b =(xk yl ). Согласно определению операции этот элемент может быть вычислен при помощи матриц смежности вершин исходных графов следующим образом:
a a b = a(ij)(kl) = Kik × a2,jl Ú Kjl × a1,ik, (2)
где a1,ik, a2,jl – элементы матрицы смежности вершин графов G1 и G2 соответственно;
Kik – символ Кронекера, равный 1, если i=k, и нулю, если i ¹ k .
Пример 4. Выполнить операцию декартова произведения на графах, приведенных на рис. 4.
Составим матрицы смежности вершин исходных графов.
x1 | x2 | y1 | y2 | y3 | |||
x1 | 1 | y1 | 1 | 1 | |||
A1 | = | x2 | 1 | A2 | = | y2 | 1 |
y3 | 1 |
Для построения матрицы смежности результирующего графа воспользуемся соотношением (2). В этом соотношении первое слагаемое Kik × a2,jl указывает на наличие дуг для вершин, у которых совпадают компоненты из множества X. Для пояснения сказанного, рассмотрим вспомогательную матрицу Axy, в которой элементы, для которых Kik = 1, помечены символом X. Эти элементы принимают значения, равные значениям соответствующих элементов матрицы A2 смежности вершин графа G2, так, как это показано для матрицыA*.
x1 y1 | x1 y2 | x1 y3 | x2 y1 | x2 y2 | x2 y3 | |
x1 y1 | X Ú Y | X | X | Y | ||
x1 y2 | X | X ÚY | X | Y | ||
Axy | = | X1 y3 | X | X | X ÚY | Y |
X2 y1 | Y | XÚY | X | X | ||
X2 y2 | Y | X | X ÚY | X | ||
X2 y3 | Y | X | X | X ÚY |
x1 y1 | x1 y2 | x1 y3 | x2 y1 | x2 y2 | x2 y3 | |
x1 y1 | a1,11 Ú a2,11 | a2,12 | a2,13 | a1,12 | ||
x1 y2 | a2,21 | a1,11 Úa2,22 | a2,11 | a1,12 | ||
A* | = | x1 y3 | a2,31 | A2,32 | a1,11 Úa2,33 | a1,12 |
x2 y1 | a1,21 | a1,22 Úa2,11 | a2,12 | a2,13 | ||
x2 y2 | a1,21 | a2,21 | a1,22 Úa2,22 | a2,23 | ||
x2 y3 | a1,21 | a2,31 | a2,32 | a1,22 Ú a2,33 |
Второе слагаемое Kjl × a1,ik соотношения (2) указывает на наличие дуг для групп вершин, у которых совпадают компоненты из множества Y. В матрице Axy элементы, для которых Kjl = 1 помечены символом Y. Эти элементы принимают значения, равные значениям соответствующих элементов матрицы A1 смежности вершин графа G1, так, как это показано для матрицыA*.
Заметим, что в матрицах Axy и A* на главной диагонали располагаются элементы, равные логической сумме значений элементов матриц смежности вершин обоих графов. Это определяется тем, что на главной диагонали расположены элементы, для которых Kik = Kjl = 1.
Таким образом, матрица смежности вершин результирующего графа принимает вид:
x1 y1 | x1 y2 | x1 y3 | x2 y1 | x2 y2 | x2 y3 |
x1 y1 | 1 | 1 | 1 | ||
x1 y2 | 1 | 1 | |||
A | = | x1 y3 | 1 | 1 | |
x2 y1 | 1 | 1 | 1 | ||
x2 y2 | 1 | 1 | |||
x2 y3 | 1 | 1 |
Нетрудно убедиться, что полученной матрице смежности вершин соответствует граф G1 ´ G2, представленный на рис. 4
Операция произведения графов. Пусть G1 (X,E1 ) и G2 (Y,E2 ) — два графа. Произведением G1 × G2 графов G1 и G2 называется граф с множеством вершин X ´ Y, а дуга из вершины (xi ,yj ) в вершину (xk ,yl ) существует тогда и только тогда, когда существуют дуги (xi ,xk ) Î E1 и (yj ,yl ) Î E2 .
Выполнение операции произведения рассмотрим на примере графов, изображенных на рис. 5. Множество вершин Z результирующего графа определяется как декартово произведение множеств X ´ Y. Множество Z содержит следующие элементы: z1 =(x1 y1 ), z2= (x1 y2 ), z3 =(x1 y3 ), z4 =(x2 y1 ), z5 =(x2 y2 ), z6 =(x2 y3 ) .
Определим множество дуг результирующего графа. Для удобства рассмотрения составим таблицу, в первом столбце которой указываются дуги графа G1 , во втором – дуги графа G2, а в третьем и четвертом – дуги результирующего графа.
G1 | G2 | (x1, y1 ) ®(x2 ,y1 ) | (z a, z b ) |
(x1 ,x2 ) | (y1 ,y1 ) (y1 ,y2 ) (y2 ,y3 ) (y3 ,y2 ) | (x1, y1 ) ® (x2 ,y1 ) (x1, y1 ) ® (x2 ,y2 ) (x1, y2 ) ® (x2 ,y3 ) (x1, y3 ) ®(x2 ,y2 ) | (z1, z4 ) (z1, z5 ) (z2, z6 ) (z3, z5 ) |
(x2 ,x1 ) | (y1 ,y1 ) (y1 ,y2 ) (y2 ,y3 ) (y3 ,y2 ) | (x2, y1 ) ® (x1 ,y1 ) (x2, y1 ) ® (x1 ,y2 ) (x2, y2 ) ® (x1 ,y3 ) (x2, y3 ) ®(x1 ,y2 ) | (z4, z1 ) (z4, z2 ) (z5, z3 ) (z6, z2 ) |
Результирующий граф G1 × G2 изображен на рис.5.
Операция произведения обладает следующими свойствами.
1. G1 × G2 = G2 × G1 .
2. G1 × (G2 × G3 ) = (G1 × G2 ) × G3 .
Рассмотрим выполнение операции произведения графов в матричной форме.
Пусть G1 (X,E1 ) и G2 (Y,E2 ) – два графа, имеющие nx и ny вершин соответственно. Результирующий граф G1 × G2 имеет nx × ny вершин, а его матрица смежности вершин — квадратная матрица размером (nx × ny ) ´ (nx × ny ). Обозначим через a a b = a(ij)(kl) элемент матрицы смежности вершин, указывающий на наличие дуги (ребра), соединяющей вершину z a =(xi yj ) c z b =(xk yl ). Этот элемент может быть вычислен при помощи матриц смежности вершин исходных графов следующим образом:
a a b =a(ij)(kl) = a1,ik Ù a2,jl, (3)
де a1,ik, a1,ik – элементы матрицы смежности вершин графов G1 и G2 соответственно.
Пример 5. Выполнить операцию произведения на графах, приведенных на рис. 5.
Составим матрицы смежности вершин исходных графов.
x1 | x2 | y1 | y2 | y3 | |||
x1 | 1 | y1 | 1 | 1 | |||
A1 | = | x2 | 1 | A2 | = | y2 | 1 |
y3 | 1 |
Построим матрицу A смежности вершин результирующего графа, каждый элемент которой вычисляется согласно соотношению (4.3).
x1 y1 | x1 y2 | x1 y3 | x2 y1 | x2 y2 | x2 y3 | |||
x1 y1 | a1,11 Ù a2,11 | a1,11 Ùa2,12 | a1,11 Ù a2,13 | a1,12 Ùa2,11 | a1,12 Ù a2,12 | a1,12 Ù a2,13 | ||
x1 y2 | a1,11 Ù a2,21 | a1,11 Ù a2,22 | a1,11 Ù a2,23 | a1,12 Ù a2,21 | a1,12 Ù a2,22 | a1,12 Ù a2,23 | ||
A | = | x1 y3 | a1,11 Ù a2,21 | a1,11 Ù a2,22 | a1,11 Ù a2,23 | a1,12 Ù a2,31 | a1,12 Ù a2,32 | a1,12 Ù a2,33 |
x2 y1 | a1,21 Ù a2,11 | a1,21 Ù a2,12 | a1,21 Ù a2,13 | a1,22 Ù a2,11 | a1,22 Ù a2,12 | a1,22 Ù a2,13 | ||
x2 y2 | a1,21 Ù a2,21 | a1,21 Ù a2,22 | a1,21 Ù a2,23 | a1,12 Ù a2,21 | a1,12 Ù a2,22 | A1,12 Ù a2,23 | ||
x2 y3 | a1,21 Ù a2,31 | a1,21 Ù a2,32 | a1,21 Ù a2,33 | a1,22 Ù a2,31 | a1,12 Ù a2,32 | A1,12 Ù a2,33 |
Для удобства рассмотрения разделим матрицу A на четыре квадратные подматрицы. Заметим, что каждая подматрица может быть получена путем логического элементов матрицы умножения A2 на один из элементов a1,ij матрицы A 1 . С учетом этого матрицу A можно представить так:
x1 y1 | x1 y2 | x1 y3 | x2 y1 | x2 y2 | x2 y3 |
x1 y1 | a1,11 Ù A2 | a1,12 Ù A2 | |||
x1 y2 | |||||
A | = | x1 y3 | |||
x2 y1 | a1,21 Ù A2 | a1,22 Ù A2 | |||
x2 y2 | |||||
x2 y3 |
Таким образом, матрица смежности вершин графа G1 × G 2 имеет вид:
x1 y1 | x1 y2 | x1 y3 | x2 y1 | x2 y2 | x2 y3 |
x1 y1 | 1 | 1 | |||
x1 y2 | 1 | ||||
A | = | x1 y3 | 1 | ||
x2 y1 | 1 | 1 | |||
x2 y2 | 1 | ||||
x2 y3 | 1 |
Нетрудно убедиться, что полученной матрице смежности вершин соответствует граф G1 × G2, представленный на рис. 5.
ЛИТЕРАТУРА
1. Белоусов А.И., Ткачев С.Б. Дискретная математика: Учебник для ВУЗов / Под ред. В.С. Зарубина, А.П. Крищенко.– М.: изд-во МГТУ им. Н.Э. Баумана, 2001.– 744 с. (Сер. Математика в техническом университете; Вып XIX).
2. Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика.– М.: Наука, Физматлит, 2000.– 544 с.– ISBN 5-02-015238-2.
3. Зарубин В.С. Математическое моделирование в технике: Учеб. для ВУЗов / Под ред. В.С. Зарубина, А.П. Крищенко.– М.: Изд-во МГТУ им. Н.Э. Баумана, 2001.– 496 с. (Сер. Математика в техническом университете; вып. XXI, заключительный).