Скачать .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, заключительный).