База знаний студента. Реферат, курсовая, контрольная, диплом на заказ

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

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

РЕФЕРАТ

На тему:

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

МИНСК, 2008

Операции на графах позволяют образовывать новые графы из нескольких более простых. В этом параграфе будут рассмотрены операции на графах без параллельных ребер (дуг).

 

Объединение графов.

 Пусть G₁(X₁,E₁) и G₂(X₂,E₂) – произвольные графы. Объединением  G₁ÈG₂ графов G₁ и G₂ называется граф с множеством вершин X₁ÈX₂, и с множеством ребер (дуг)  E₁ÈE_2.

Рассмотрим операцию на примере графов G₁(X₁,E₁) и G₂(X₂,E₂), приведенных на рис. 4.1. Множества вершин первого и второго графов соответственно равны X₁ = {x₁, x₂, x₃} и X₂ = {x₂, x₃, x₄}, а множество вершин результирующего графа определится как X = X₁ÈX₂ = {x₁, x₂, x₃, x₄}. Аналогично определяем множества дуг графа:

E₁ = {(x₁, x₂), (x₁, x₃), (x₂, x₁), (x₃, x₃)}.               E₂ = {(x₂, x₄), (x₃, x₂)_, (x₄, x₂)}.

E = {(x₁, x₂), (x₁, x₃), (x₂, x₁), (x₃, x₃), (x₂, x₄), (x₃, x₂)_, (x₄, x₂)}.

Результирующий граф G(X,E)  =  G₁(X₁,E₁)ÈG₂(X₂,E₂) также приведен на рис. 1.

Операция объединения обладает следующими свойствами, которые следуют из определения операции и свойств операций на множествах:

   G₁ÈG₂  = G₂ÈG₁ – свойство коммутативности;

  G₁È(G₂ÈG₃)  = (G₁ÈG₂)ÈG₃ – свойство ассоциативности.

Операция объединения графов может быть выполнена в матричной форме. Для графов с одним и тем же множеством вершин справедлива следующая теорема.

Теорема 1. Пусть G₁ и G₂ – два графа (ориентированные или не ориентированные одновременно) с одним и тем же множеством вершин X, и пусть A₁ и A₂ – матрицы смежности вершин этих графов. Тогда матрицей смежности вершин графа G₁ÈG₂  является матрица A = A₁ÈA₂, образованная поэлементным логическим сложением матриц A₁ и A₂.

Рассмотрим выполнение операции объединения графов, множества вершин которых не совпадают. Пусть G₁(X₁,E₁) и G₂(X₂,E₂)  – графы без параллельных ребер и  множества X₁ и X₂ вершин этих графов не совпадают. Пусть  A₁ и A₂ – матрицы смежности их вершин графов. Для таких графов операция объединения может быть выполнена следующим образом.

В соответствии с определением операции объединения графов найдем множество вершин результирующего графа как X₁ÈX₂. Построим вспомогательные графы G’₁ и G’₂, множества вершин которых есть множество X₁ÈX₂, а множество ребер (дуг) определяется множествами E₁ для графа G^’₁ и E₂ для графа G^’₂. Очевидно, что матрицы A’₁ и A’₂ смежности вершин этих графов могут быть получены из матриц A₁ и A₂ путем добавления в них дополнительных столбцов и строк с нулевыми элементами.

Применив к графам G’₁ и G’₂ теорему 4.1, найдем матрицу смежности вершин графа G’₁ÈG’₂ как A’₁ÈA’₂. Очевидно, что полученной матрице смежности вершин  соответствует граф, множество вершин которого равно X₁ÈX₂, а множество ребер определяется, как E₁ÈE₂, что соответствует операции объединения графов.

Пример 1. Выполнить в матричной форме операцию объединения графов G₁ и G₂, представленных на рис. 1.

Составим матрицы смежности вершин графов.

			x1	x2	x3				x2	x3	x4
		x1	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

Множество вершин результирующего графа X₁ÈX₂ = {x₁, x₂, x₃, x₄}. Составим матрицы смежности вершин вспомогательных графов G’₁ и G’₂.

			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’₁ÈA’₂ имеет вид

			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’₁ È A’₂ соответствует графу G₁ÈG₂, изображенному на рис.1.

 

Пересечение графов

Пусть G₁(X₁,E₁) и G₂(X₂,E₂) – произвольные графы. Пересечением G₁ÇG₂ графов G₁ и G₂ называется граф с множеством вершин       X₁ÇX₂ с множеством ребер (дуг) E = E₁ÇE₂

Операция пересечения обладает следующими свойствами, которые следуют из определения операции и свойств операций на множествах:

  G₁ÇG₂  = G₂ÇG₁– свойство коммутативности;

  G₁Ç (G2ÇG3)  = (G1ÇG2) Ç G₃ – свойство ассоциативности.

Для того чтобы операция пересечения была всеобъемлющей, необходимо ввести понятие пустого графа. Граф G(X,E) называется пустым, если множество X вершин графа является пустым (X=Æ). Заметим, что в этом случае и множество E ребер (дуг) графа также пустое множество (E=Æ). Пустой граф обозначается символом Æ. Такой граф может быть получен в результате выполнения операции пересечения графов, у которых X₁ÇX₂=Æ. В этом случае говорят о непересекающихся графах.

Рассмотрим выполнение операции пересечения графов, изображенных на рис. 2. Для нахождения множества вершин результирующего графа запишем множества вершин исходных графов и выполним над этими множествами операцию пересечения:

X₁ = {x₁, x₂, x₃}; X₂ = {x₁, x₂, x₃, x₄};

X = X₁ÇX₂ = {x₁, x₂, x₃}.

Аналогично определяем множество E дуг результирующего графа:

E₁ = {(x₁, x₂), (x₁, x₃), (x₂, x₁), (x₂, x₃), (x₃, x₂)};

E₂ = {(x₁, x₃), (x₂, x₁), (x₂, x₃), (x₂, x₄), (x₃, x₁)};

E = E₁ÇE₂ = {(x₁, x₃), (x₂, x₁)}.

Графы G₁(X₁,E₁), G₂(X₂,E₂) и их пересечение приведены на рис 4.2.

Операция пересечения графов может быть выполнена в матричной форме.

Теорема 2. Пусть G₁ и G₂ – два графа (ориентированные или неориентированные одновременно) с одним и тем же множеством вершин X, и пусть A₁ и A₂ – матрицы смежности вершин этих графов. Тогда матрицей смежности вершин графа G1ÇG2  является матрица A = A₁ÇA₂ образованная поэлементным логически умножением матриц A₁ и A₂.

Рассмотрим выполнение операции пересечения для графов с несовпадающим множеством вершин.

Пусть G₁(X₁,E₁) и G₂(X₂,E₂)  – графы без параллельных ребер, множества X₁ и X₂ вершин графов не совпадают, а A₁ и A₂ – матрицы смежности вершин графов. Для таких графов операция пересечения может быть выполнена так.

В соответствии с определением операции пересечения графов найдем множество вершин результирующего графа как X₁ÇX₂. Построим вспомогательные графы G’₁ и G’₂, множества вершин которых есть множество X₁ÇX₂, а множество ребер (дуг) определяется множествами E’₁ и E’₂ всех ребер (дуг), инцидентных этим вершинам. Очевидно, что матрицы A’₁ и A’₂ смежности вершин этих графов могут быть получены из матриц A₁ и A₂ путем удаления из них столбцов и строк, соответствующих вершинам, не вошедшим во множество X1ÇX2.

Применив к графам G’₁ и G’₂ теорему 2, найдем матрицу смежности вершин графа G’₁ÇG’₂ как A’₁ÇA’₂. Очевидно, что полученной матрице смежности вершин  соответствует граф, множество вершин которого равно X₁ÇX₂, а множество ребер определяется, как E₁ÇE₂, что соответствует операции пересечения графов.

Пример 2. Выполнить в матричной форме операцию пересечения графов G₁ и G₂, представленных на рис. 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 = X₁ÇX₂ = {x₁, x₂, x₃}.

Составим матрицы смежности вершин вспомогательных графов G’₁ и G’₂.

			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 = A₁ Ç A₂

 

			x1	x2	x3
		x1	0	0	0
A’1ÇA’2	=	x2	1	0	1
		x3	0	0	0

 Полученная матрица  смежности вершин A’₁ Ç A’₂ соответствует графу G₁ÇG₂,  изображенному на рис.2.

Композиция графов

Пусть G₁(X,E₁) и G₂(X,E₂) — два графа с одним и тем же множеством вершин X. Композицией G₁(G₂) графов G₁ и G₂ называется граф с множеством вершин E, в котором существует дуга (x_i,x_j) тогда и только тогда, когда существует дуга (x_i,x_k), принадлежащая множеству E₁, и дуга (x_k,x_j), принадлежащая множеству E₂.

Рассмотрим выполнение операции композиции G₁(G₂) на графах, изображенных на рис.3. Для рассмотрения операции составим таблицу, в первом столбце которой указываются ребра (x_i, x_k), принадлежащие графу G₁, во втором — ребра (x_k, x_j), принадлежащие графу G₃, а в третьем — результирующее ребро (x_i, x_j) для графа G₁(G₂).

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)

 

Заметим, что дуга (x₁,x₃) результирующего графа в таблице встречается дважды. Однако, поскольку рассматриваются графы без параллельных ребер (дуг), то в множестве E результирующего графа дуга (x₁,x₃) учитывается только один раз, т.е. E = {(x₁,x₁), (x₁,x₃), (x₂,x₁), (x₂,x₃)}  

На рис. 3 изображены графы G₁ и G₂ и их композиции G₁(G₂). На этом же рисунке изображен граф G₂(G₁). Рекомендуется самостоятельно построить граф G₂(G₁) и убедиться,  что графы G₁(G₂) и G₂(G₁)   не изоморфны.

Пусть А₁ и A₂ – матрицы смежности вершин графов G₁(X,E₁) и G(X,E₂) соответственно.  Рассмотрим матрицу A₁₂ элементы a_ij которой вычисляется так:

                                                                  _n

a_ij = Úa_1ikÙa_2kj                                                        (1)

                                                                                                              ^k=1

 где a_1ik и a_2kj – элементы матрицы смежности вершин первого и второго графов соответственно. Элемент a_ij равен 1, если в результирующем графе G₁(G₂) существует дуга, исходящая из вершины x_i и заходящая  x_j, и нулю – в противном случае.

Пример 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

Нетрудно убедиться, что полученным матрицам смежности вершин соответствуют графы G₁(G₂) и G₂(G₁), представленные на рис. 3.

Декартово произведение графов. Пусть G₁(X,E₁) и G₂(Y,E₂) — два графа. Декартовым произведением G₁(X,E₁)´G₂(Y,E₂) графов G₁(X,E₁) и G₂(X,E₂) называется граф с множеством вершин X´Y, в котором дуга (ребро), идущая из вершины (x_iy_j) в (x_ky_l), существует тогда и только тогда когда существует дуга (x_ix_k), принадлежащая множеству дуг E₁ и j = l или когда существует дуга (y_j,y_l), принадлежащая множеству E₂ и i = k.

Выполнение операции декартова произведения рассмотрим на примере графов, изображенных на рис. 4. Множество вершин Z результирующего графа определяется как декартово произведение множеств X´Y. Множество Z содержит следующие элементы: z₁=(x₁y₁), z₂₌(x₁y₂), z₃=(x₁y₃), z₄=(x₂y₁), z₅=(x₂y₂), z₆=(x₂y₃).

Определим множество дуг результирующего графа. Для этого выделим группы вершин множества Z,  компоненты которых совпадают. В рассматриваемом примере пять таких групп: две группы с совпадающими компонентами из множества X, и  три группы, имеющие совпадающие компоненты из Y. Рассмотрим группу вершин результирующего графа, которые имеют общую компоненту x₁: z₁=(x₁y₁), z₂₌(x₁y₁), z₃=(x₁y₃). Согласно определению операции декартова произведения графов, множество дуг между этими вершинами определяется связями между вершинами множества Y. Таким образом, дуга (y₁,y₁) в графе G2 определяет наличие дуги (z₁,z₁) в результирующем графе. Для удобства рассмотрения всех дуг результирующего графа составим таблицу, в первом столбце которой перечисляются вершины с совпадающими компонентами, во втором – дуги между несовпадающими компонентами, а в третьем и четвертом – дуги в результирующем графе.

№ п.п.	Группы вершин с совпадаю­щими компонентами	Дуги для несовпада­­ю­щих компонент	Дуга (xiyj)®(xkyl)	Дуга (za,zb)
1	z1=(x1y1), z2=(x1y2), z3=(x1y3)	(y1,y1) (y1,y2) (y2,y3) (y3,y1)	(x1y1)®(x1y1) (x1y1)®(x1y2) (x1y2)®(x1y3) (x1y3)®(x1y1)	(z1,z1) (z1,z2) (z2,z3) (z3,z1)
2	z4=(x2y1), z5=(x2y2), z6=(x2y3)	(y1,y1) (y1,y2) (y2,y3) (y3,y1)	(x2y1)®(x2y1) (x2y1)®(x2y2) (x2y2)®(x2y3) (x2y3)®(x2y1)	(z4,z4) (z4,z5) (z5,z6) (z6,z4)
3	z1=(x1y1), z4=(x2y1)	(x1,x2) (x2,x1)	(x1y1)®(x2y1) (x2y1)®(x1y1)	(z1,z4) (z4,z1)
4	z2=(x1y2),  z5=(x2y2)	(x1,x2) (x2,x1)	(x1y2)®(x2y2) (x1y2)®(x1y2)	(z2,z5) (z5,z2)
5	Z3=(x1y3), z6=(x2y3)	(x1,x2) (x2,x1)	(x1y3)®(x2y3) (x2y3)®(x1y3)	(z3,z6) (z6,z3)

 

Граф G₁´ G₂ изображен на рис. 4.

Операция декартова произведения обладает следующими свойствами.

1. G₁´G₂ = G₂´G₁

2. G₁´(G₂´G₃) =  (G₁´G₂)´G₃.

Операция декартова произведения графов может быть выполнена в матричной форме.

Пусть G₁(X,E₁) и G₂(Y,E₂) – два графа, имеющие  n_x и n_y  вершин соответственно. Результирующий граф G₁´G₂ имеет n_x×n_y вершин, а его матрица смежности вершин - квадратная матрица размером (n_x×n_y)´ (n_x ×n_y). Обозначим через a_ab = a_(ij)(kl) элемент матрицы смежности вершин, указывающий на наличие дуги (ребра), соединяющей вершину z_a=(x_iy_j) c z_b=(x_ky_l). Согласно определению операции этот элемент может быть вычислен при помощи матриц смежности вершин исходных графов следующим образом:

a_ab = a_(ij)(kl) = K_ik×a_2,jl Ú K_jl×a_1,ik,                                              (2)

где a_1,ik, a_2,jl – элементы матрицы смежности вершин графов G₁ и G₂ соответственно;

K_ik – символ Кронекера, равный 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). В этом соотношении первое слагаемое K_ik×a_2,jl указывает на наличие дуг для вершин, у которых совпадают компоненты из множества X. Для пояснения сказанного, рассмотрим вспомогательную матрицу Axy, в которой элементы, для которых K_ik = 1, помечены символом X. Эти элементы принимают значения, равные значениям соответствующих элементов матрицы A₂ смежности вершин графа G₂, так, как это показано для матрицы A*.

 

			x1y1	x1y2	x1y3	x2y1	x2y2	x2y3
		x1y1	XÚY	X	X	Y	0	0
		x1y2	X	XÚY	X	0	Y	0
Axy	=	X1y3	X	X	XÚY	0	0	Y
		X2y1	Y	0	0	XÚY	X	X
		X2y2	0	Y	0	X	XÚY	X
		X2y3	0	0	Y	X	X	XÚY

 

			x1y1	x1y2	x1y3	x2y1	x2y2	x2y3
		x1y1	a1,11Ú  a2,11	a2,12	a2,13	a1,12
		x1y2	a2,21	a1,11Úa2,22	a2,11		a1,12
A*	=	x1y3	a2,31	A2,32	a1,11Úa2,33	0	0	a1,12
		x2y1	a1,21	0	0	a1,22Úa2,11	a2,12	a2,13
		x2y2	0	a1,21	0	a2,21	a1,22Úa2,22	a2,23
		x2y3	0	0	a1,21	a2,31	a2,32	a1,22Ú a2,33

 

Второе слагаемое K_jl×a_1,ik соотношения (2) указывает на  наличие дуг для групп вершин, у которых совпадают компоненты из множества Y. В матрице Axy элементы, для которых K_jl = 1 помечены символом Y. Эти элементы принимают значения, равные значениям соответствующих элементов матрицы A₁ смежности вершин графа G₁, так, как это показано для матрицы A*.

Заметим, что в матрицах Axy и A* на главной диагонали располагаются элементы, равные логической сумме значений элементов матриц смежности вершин обоих графов. Это определяется тем, что на главной диагонали расположены элементы, для которых    K_ik = K_jl = 1.

Таким образом, матрица смежности вершин результирующего графа принимает вид:

 

			x1y1	x1y2	x1y3	x2y1	x2y2	x2y3
		x1y1	1	1	0	1	0	0
		x1y2	0	0	1	0	1	0
A	=	x1y3	1	0	0	0	0	1
		x2y1	1	0	0	1	1	0
		x2y2	0	1	0	0	0	1
		x2y3	0	0	1	1	0	0

Нетрудно убедиться, что полученной матрице смежности вершин соответствует граф G₁´G₂, представленный на рис. 4

 Операция произведения графов.  Пусть G₁(X,E₁) и G₂(Y,E₂) - два графа. Произведением G₁×G₂ графов G₁ и G₂ называется граф с множеством вершин X´Y, а дуга из вершины  (x_i,y_j) в вершину (x_k,y_l) существует тогда и только тогда, когда существуют дуги (x_i,x_k) Î E₁ и (y_j,y_l) Î E₂.

Выполнение операции произведения рассмотрим на примере графов, изображенных на рис. 5. Множество вершин Z результирующего графа определяется как декартово произведение множеств X´Y. Множество Z содержит следующие элементы: z₁=(x₁y₁), z₂₌(x₁y₂), z₃=(x₁y₃), z₄=(x₂y₁), z₅=(x₂y₂), z₆=(x₂y₃).

Определим множество дуг результирующего графа. Для удобства рассмотрения составим таблицу, в первом столбце которой указываются дуги графа G₁, во втором – дуги графа G₂, а в третьем и четвертом – дуги результирующего графа.

G1	G2	(x1,y1)®(x2,y1)	(za, zb)
(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)

Результирующий граф G_1×G₂ изображен на рис.5.

Операция произведения обладает следующими свойствами.

1. G₁×G₂ = G₂×G₁.

2. G₁×(G₂×G₃)  = (G₁×G₂)×G₃.

Рассмотрим выполнение операции произведения графов в матричной форме.

Пусть G₁(X,E₁) и G₂(Y,E₂) – два графа, имеющие  n_x и n_y  вершин соответственно. Результирующий граф G₁×G₂ имеет n_x×n_y вершин, а его матрица смежности вершин - квадратная матрица размером (n_x×n_y)´ (n_x ×n_y). Обозначим через a_ab = a_(ij)(kl) элемент матрицы смежности вершин, указывающий на наличие дуги (ребра), соединяющей вершину z_a=(x_iy_j) c z_b=(x_ky_l). Этот элемент может быть вычислен при помощи матриц смежности вершин исходных графов следующим образом:

a_ab =a_(ij)(kl) = a_1,ik Ù a_2,jl,                                        (3)

де a_1,ik, a_1,ik – элементы матрицы смежности вершин графов G₁ и G₂ соответственно.

Пример 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).

			x1y1	x1y2	x1y3	x2y1	x2y2	x2y3
		x1y1	a1,11Ù a2,11	a1,11Ùa2,12	a1,11Ù a2,13	a1,12Ùa2,11	a1,12Ù a2,12	a1,12Ù a2,13
		x1y2	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	=	x1y3	a1,11Ù a2,21	a1,11Ù a2,22	a1,11Ù a2,23	a1,12Ù a2,31	a1,12Ù a2,32	a1,12Ù a2,33
		x2y1	a1,21Ù a2,11	a1,21Ù a2,12	a1,21Ù a2,13	a1,22Ù a2,11	a1,22Ù a2,12	a1,22Ù a2,13
		x2y2	a1,21Ù a2,21	a1,21Ù a2,22	a1,21Ù a2,23	a1,12Ù a2,21	a1,12Ù a2,22	A1,12Ù a2,23
		x2y3	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 на четыре квадратные подматрицы. Заметим, что каждая подматрица может быть получена путем логического элементов матрицы умножения A₂ на один из элементов  a_1,ij матрицы A₁. С учетом этого матрицу A можно представить так:

			x1y1	x1y2	x1y3	x2y1	x2y2	x2y3
		x1y1	a1,11ÙA2			a1,12ÙA2
		x1y2
A	=	x1y3
		x2y1	a1,21ÙA2			a1,22ÙA2
		x2y2
		x2y3

 Таким образом, матрица смежности вершин  графа G₁×G₂ имеет вид:

			x1y1	x1y2	x1y3	x2y1	x2y2	x2y3
		x1y1	0	0	0	1	1	0
		x1y2	0	0	0	0	0	1
A	=	x1y3	0	0	0	0	1	0
		x2y1	1	1	0	0	0	0
		x2y2	0	0	1	0	0	0
		x2y3	0	1	0	0	0	0

Нетрудно убедиться, что полученной матрице смежности вершин соответствует граф G₁×G₂, представленный на рис. 5.

ЛИТЕРАТУРА

 

1.  Белоусов А.И., Ткачев С.Б. Дискретная математика: Учебник для ВУЗов / Под ред. В.С. Зарубина, А.П. Крищенко.– М.: изд-во МГТУ им. Н.Э. Баумана, 2001.– 744 с. (Сер. Математика в техническом университете; Вып XIX).

2.  Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика.– М.: Наука, Физматлит, 2000.– 544 с.– ISBN 5-02-015238-2.

3.  Зарубин В.С. Математическое моделирование в технике: Учеб. для ВУЗов / Под ред. В.С. Зарубина, А.П. Крищенко.– М.: Изд-во МГТУ им. Н.Э. Баумана, 2001.– 496 с. (Сер. Математика в техническом университете; вып. XXI, заключительный).

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ Кафедра информатики РЕФЕРАТ На тему: «Операции на графах»МИНСК, 2008 Операции на графах позволяют образовывать новые

 

• 14:21 05 Июля 2016
  Российско-китайский медуниверситет откроет магистерскую программу по TCM
• 01:21 05 Июля 2016
  На форуме МГУ Россия и Китай обсудят научно-образовательное сотрудничество
• 11:00 04 Июля 2016
  Реморенко: "ЕГЭ-туризм" в России сходит на нет
• 10:52 04 Июля 2016
  Летняя российско-австрийская школа откроется в Москве
• 15:31 01 Июля 2016
  В СПбГУ могут воссоздать географический факультет

Заказать уникальную работу