Операции на графах

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

Кафедра информатики

РЕФЕРАТ

На тему:

«Операции на графах»

МИНСК, 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 ) < /p> (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, заключительный).