Скачать .docx | Скачать .pdf |
Реферат: Операции на графах
БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
Кафедра информатики
РЕФЕРАТ
На тему:
«Операции на графах»
МИНСК, 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 |
0 |
1 |
1 |
|
|
x2 |
0 |
0 |
1 |
A1 |
= |
x2 |
1 |
0 |
0 |
A2 |
= |
x3 |
1 |
0 |
0 |
|
|
x3 |
0 |
0 |
1 |
|
|
x4 |
0 |
1 |
0 |
Множество вершин результирующего графа X1 È X2 = {x1 , x2 , x3 , x4 } . Составим матрицы смежности вершин вспомогательных графов G’1 и G’2 .
|
|
|
x1 |
x2 |
x3 |
x4 |
|
|
|
x1 |
x2 |
x3 |
x4 |
x1 |
0 |
1 |
1 |
0 |
x1 |
0 |
0 |
0 |
0 |
||||
A’1 |
= |
x2 |
1 |
0 |
0 |
0 |
A’2 |
= |
x2 |
0 |
0 |
0 |
1 |
x3 |
0 |
0 |
1 |
0 |
x3 |
0 |
1 |
0 |
0 |
||||
x4 |
0 |
0 |
0 |
0 |
x4 |
0 |
0 |
1 |
0 |
Матрица A = A’1 È A’2 имеет вид
|
|
|
X1 |
x2 |
x3 |
x4 |
|
|
x1 |
0 |
1 |
1 |
0 |
|
|
x2 |
1 |
0 |
0 |
1 |
A = A’1 È A’2 |
= |
x3 |
0 |
1 |
1 |
0 |
|
|
x4 |
0 |
0 |
1 |
0 |
Полученная матрица смежности вершин 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 |
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 = Ú 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 |
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 , в котором дуга (ребро), идущая из вершины (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 |
0 |
1 |
y1 |
1 |
1 |
0 |
|||||
A1 |
= |
x2 |
1 |
0 |
A2 |
= |
y2 |
0 |
0 |
1 |
|
y3 |
1 |
0 |
0 |
Для построения матрицы смежности результирующего графа воспользуемся соотношением (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 |
0 |
0 |
|
|
x1 y2 |
X |
X ÚY |
X |
0 |
Y |
0 |
|
Axy |
= |
X1 y3 |
X |
X |
X ÚY |
0 |
0 |
Y |
|
X2 y1 |
Y |
0 |
0 |
XÚY |
X |
X |
|
|
X2 y2 |
0 |
Y |
0 |
X |
X ÚY |
X |
|
|
X2 y3 |
0 |
0 |
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 |
0 |
0 |
a1,12 |
|
x2 y1 |
a1,21 |
0 |
0 |
a1,22 Úa2,11 |
a2,12 |
a2,13 |
|
|
x2 y2 |
0 |
a1,21 |
0 |
a2,21 |
a1,22 Úa2,22 |
a2,23 |
|
|
x2 y3 |
0 |
0 |
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 |
0 |
1 |
0 |
0 |
|
|
x1 y2 |
0 |
0 |
1 |
0 |
1 |
0 |
|
A |
= |
x1 y3 |
1 |
0 |
0 |
0 |
0 |
1 |
|
x2 y1 |
1 |
0 |
0 |
1 |
1 |
0 |
|
|
x2 y2 |
0 |
1 |
0 |
0 |
0 |
1 |
|
|
x2 y3 |
0 |
0 |
1 |
1 |
0 |
0 |
Нетрудно убедиться, что полученной матрице смежности вершин соответствует граф 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 |
0 |
1 |
|
y1 |
1 |
1 |
0 |
|||
A1 |
= |
x2 |
1 |
0 |
A2 |
= |
y2 |
0 |
0 |
1 |
|
|
|
|
y3 |
0 |
1 |
0 |
Построим матрицу 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 |
0 |
0 |
0 |
1 |
1 |
0 |
|
|
x1 y2 |
0 |
0 |
0 |
0 |
0 |
1 |
|
A |
= |
x1 y3 |
0 |
0 |
0 |
0 |
1 |
0 |
|
x2 y1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
|
x2 y2 |
0 |
0 |
1 |
0 |
0 |
0 |
|
|
x2 y3 |
0 |
1 |
0 |
0 |
0 |
0 |
Нетрудно убедиться, что полученной матрице смежности вершин соответствует граф G1 × G2 , представленный на рис. 5.
ЛИТЕРАТУРА
1. Белоусов А.И., Ткачев С.Б. Дискретная математика: Учебник для ВУЗов / Под ред. В.С. Зарубина, А.П. Крищенко.– М.: изд-во МГТУ им. Н.Э. Баумана, 2001.– 744 с. (Сер. Математика в техническом университете; Вып XIX).
2. Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика.– М.: Наука, Физматлит, 2000.– 544 с.– ISBN 5-02-015238-2.
3. Зарубин В.С. Математическое моделирование в технике: Учеб. для ВУЗов / Под ред. В.С. Зарубина, А.П. Крищенко.– М.: Изд-во МГТУ им. Н.Э. Баумана, 2001.– 496 с. (Сер. Математика в техническом университете; вып. XXI, заключительный).