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

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

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

РЕФЕРАТ

На тему:

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

МИНСК, 2008

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

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

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

Рассмотрим операцию на примере графов 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.

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


			x₁	x₂	x₃				x₂	x₃	x₄
		x₁	0	1	1			x₂	0	0	1
A₁	=	x₂	1	0	0	A₂	=	x₃	1	0	0
		x₃	0	0	1			x₄	0	1	0

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


			x₁	x₂	x₃	x₄				x₁	x₂	x₃	x₄
		x₁	0	1	1	0			x₁	0	0	0	0
A₁	=	x₂	1	0	0	0	A₂	=	x₂	0	0	0	1
		x₃	0	0	1	0			x₃	0	1	0	0
		x₄	0	0	0	0			x₄	0	0	1	0

Матрица A = A₁A₂ имеет вид


			X₁	x₂	x₃	x₄
		x₁	0	1	1	0
		x₂	1	0	0	1
*A =* A_1A₂	=	x₃	0	1	1	0
		x₄	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₁ (G2G3) = (G1G2) 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_{1 и A_{2 - матрицы смежности вершин этих графов. Тогда матрицей смежности вершин графа G1G2 является матрица
A = A_{1A_{2 образованная поэлементным логически умножением матриц A_{1 и
A_2.}}}}}

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

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

В соответствии с определением операции пересечения графов найдем множество вершин результирующего графа как X₁X₂. Построим вспомогательные графы G₁ и G₂, множества вершин которых есть множество X₁X₂, а множество ребер (дуг) определяется множествами E₁ и E₂ всех ребер (дуг), инцидентных этим вершинам. Очевидно, что матрицы A_{1 и
A_{2 смежности вершин этих графов могут быть получены из матриц A_{1 и A_{2 путем удаления из них
столбцов и строк, соответствующих вершинам, не вошедшим во множество X1X2.}}}}

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

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

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


			x₁	x₂	x₃				x₁	x₂	x₃	x₄
		x₁	0	1	1			x₁	0	0	0	1
A₁	=	x₂	1	0	1	A₂	=	x₂	1	0	1	1
		x₃	0	1	0			x₃	1	0	0	0
								x₄	0	0	0	0

Находим множество вершин X результирующего графа.

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

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


			x₁	x₂	x₃				x₁	x₂	x₃
		x₁	0	1	1			x₁	0	0	0
A₁	=	x₂	1	0	1	A₂	=	x₂	1	0	1
		x₃	0	1	0			x₃	1	0	0

Найдем матрицу смежности вершин A = A_{1 A₂}


			x₁	x₂	x₃
		x₁	0	0	0
A_1A₂	=	x₂	1	0	1
		x₃	0	0	0

Полученная матрица смежности вершин A_{1 A_{2 соответствует графу 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₂).


G₁	G₂	G_1(G₂₎
(x₁,x₂)	(x₂,x₁) (x₂,x₃)	(x₁,x₁) (x₁,x₃)
(x₁,x₃)	(x₃,x₃)	(x₁,x₃)
(x₂,x₁)	(x₁,x₁) (x₁,x₃)	(x₂,x₁) (x₂,x₃)

Заметим, что дуга (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₁) не изоморфны.

Пусть А_{1 и A_{2 - матрицы смежности вершин графов G₁(X,E₁) и
G(X,E₂) соответственно. Рассмотрим матрицу A_{12 элементы a_ij которой вычисляется так:}}}

a_ij = a₁_ika₂_kj (1)

^k⁼¹

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

Пример 3. Выполнить операцию композиции для графов, пред-ставленных на рис. 3.

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


			x₁	x₂	x₃				x₁	x₂	x₃
		x₁	0	1	1			x₁	1	0	1
A₁	=	x₂	1	0	0	A₂	=	x₂	1	0	1
		x₃	0	0	0			x₃	0	0	1

Вычислив элементы матрицы согласно (1), получаем:


			x₁	x₂	x₃				x₁	x₂	x₃
		x₁	1	0	2			x₁	0	1	1
A₁₂	=	x₂	1	0	1	A₂₁	=	x₂	0	1	1
		x₃	0	0	0			x₃	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₂) называется граф с множеством вершин XY, в котором дуга (ребро), идущая из вершины (x_iy_j) в (x_ky_l), существует тогда и только тогда когда существует дуга (x_ix_k), принадлежащая множеству дуг E₁ и j = l или когда существует дуга (y_j,y_l), принадлежащая множеству E₂ и i = k.

Выполнение операции декартова произведения рассмотрим на примере графов, изображенных на рис. 4. Множество вершин Z результирующего графа определяется как декартово произведение множеств XY. Множество 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₁) в результирующем графе. Для удобства рассмотрения всех дуг результирующего графа составим таблицу, в первом столбце которой перечисляются вершины с совпадающими компонентами, во втором - дуги между несовпадающими компонентами, а в третьем и четвертом - дуги в результирующем графе.

№ п.п.

Группы вершин с совпадаю-щими компонентами

Дуги для несовпада--ю-щих компонент

Дуга

(x_iy_j)(x_ky_l)

Дуга

(z,z)

z₁=(x₁y₁), z₂₌(x₁y₂), z₃=(x₁y₃)

(y₁,y₁)

(y₁,y₂)

(y₂,y₃)

(y₃,y₁)

(x₁y₁)(x₁y₁)

(x₁y₁)(x₁y₂)

(x₁y₂)(x₁y₃)

(x₁y₃)(x₁y₁)

(z₁,z₁)

(z₁,z₂)

(z₂,z₃)

(z₃,z₁)

z₄=(x₂y₁), z₅=(x₂y₂), z₆=(x₂y₃)

(y₁,y₁)

(y₁,y₂)

(y₂,y₃)

(y₃,y₁)

(x₂y₁)(x₂y₁) (x₂y₁)(x₂y₂) (x₂y₂)(x₂y₃) (x₂y₃)(x₂y₁)

(z₄,z₄)

(z₄,z₅)

(z₅,z₆)

(z₆,z₄)

z₁=(x₁y₁), z₄=(x₂y₁)

(x₁,x₂)

(x₂,x₁)

(x₁y₁)(x₂y₁ ) (x₂y₁)(x₁y₁)

(z₁,z₄) (z₄,z₁)
4	z₂₌(x₁y₂), z₅=(x₂y₂)	(x₁,x₂) (x₂,x₁)	(x₁y₂)(x₂y₂) (x₁y₂)(x₁y₂)	(z₂,z₅) (z₅,z₂)
5	Z₃=(x₁y₃), z₆=(x₂y₃)	(x₁,x₂) (x₂,x₁)	(x₁y₃)(x₂y₃) (x₂y₃)(x₁y₃)	(z₃,z₆) (z₆,z₃)

Граф 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_xn_y вершин, а его матрица смежности вершин - квадратная матрица размером (n_xn_y) (n_x n_y). Обозначим через a = a_(ij)(kl) элемент матрицы смежности вершин, указывающий на наличие дуги (ребра), соединяющей вершину z=(x_iy_j) c z=(x_ky_l). Согласно определению операции этот элемент может быть вычислен при помощи матриц смежности вершин исходных графов следующим образом:

a = a_(ij)(kl) = K_ika_2,jl K_jla_1,ik, (2)

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

K_ik - символ Кронекера, равный 1, если i=k, и нулю, если ik .

Пример 4. Выполнить операцию декартова произведения на графах, приведенных на рис. 4.

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


			x₁	x₂				y₁	y₂	y₃
		x₁	0	1			y₁	1	1	0
A₁	=	x₂	1	0	A₂	=	y₂	0	0	1
							y₃	1	0	0

Для построения матрицы смежности результирующего графа воспользуемся соотношением (2). В этом соотношении первое слагаемое K_ika_2,jl указывает на наличие дуг для вершин, у которых совпадают компоненты из множества X. Для пояснения сказанного, рассмотрим вспомогательную матрицу Axy, в которой элементы, для которых K_ik = 1, помечены символом X. Эти элементы принимают значения, равные значениям соответствующих элементов матрицы A_{2 смежности вершин графа
G₂, так, как это показано для матрицы A*.}


			x_1y₁	x_1y₂	x_1y₃	x_2y₁	x_2y₂	x_2y₃
		x_1y₁	XY	X	X	Y	0	0
		x_1y₂	X	XY	X	0	Y	0
*Axy*	=	X_1y₃	X	X	XY	0	0	Y
		X_2y₁	Y	0	0	XY	X	X
		X_2y₂	0	Y	0	X	XY	X
		X_2y₃	0	0	Y	X	X	XY


			x_1y₁	x_1y₂	x_1y₃	x_2y₁	x_2y₂	x_2y₃
		x_1y₁	a_1,11 a_2,11	a_2,12	a_2,13	a_1,12
		x_1y₂	a_2,21	a_1,11a_2,22	a_2,11		a_1,12
A*	=	x_1y₃	a_2,31	A_2,32	a_1,11a_2,33	0	0	a_1,12
		x_2y₁	a_1,21	0	0	a_1,22a_2,11	a_2,12	a_2,13
		x_2y₂	0	a_1,21	0	a_2,21	a_1,22a_2,22	a_2,23
		x_2y₃	0	0	a_1,21	a_2,31	a_2,32	a_1,22 a_2,33

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

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

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


			x_1y₁	x_1y₂	x_1y₃	x_2y₁	x_2y₂	x_2y₃
		x_1y₁	1	1	0	1	0	0
		x_1y₂	0	0	1	0	1	0
A	=	x_1y₃	1	0	0	0	0	1
		x_2y₁	1	0	0	1	1	0
		x_2y₂	0	1	0	0	0	1
		x_2y₃	0	0	1	1	0	0

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

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

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

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


G₁	G₂	(x_{1,y_{1)(x_2,y₁₎}}	(z_{, z₎}
(x₁,x₂)	(y₁,y₁) (y₁,y₂) (y₂,y₃) (y₃,y₂)	(x_1,y₁)(x₂,y₁) (x_1,y₁)(x₂,y₂) (x_1,y₂)(x₂,y₃) (x_1,y₃)(x₂,y₂)	(z_1,z₄) (z_1,z₅) (z_2,z₆) (z_3,z₅)
(x₂,x₁)	(y₁,y₁) (y₁,y₂) (y₂,y₃) (y₃,y₂)	(x_2,y₁)(x₁,y₁) (x_2,y₁)(x₁,y₂) (x_2,y₂)(x₁,y₃) (x_2,y₃)(x₁,y₂)	(z_4,z₁) (z_4,z₂) (z_5,z₃) (z_6,z₂)

Результирующий граф G₁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_xn_y вершин, а его матрица смежности вершин - квадратная матрица размером (n_xn_y) (n_x n_y). Обозначим через a = a_(ij)(kl) элемент матрицы смежности вершин, указывающий на наличие дуги (ребра), соединяющей вершину z=(x_iy_j) c z=(x_ky_l). Этот элемент может быть вычислен при помощи матриц смежности вершин исходных графов следующим образом:

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

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

Пример 5. Выполнить операцию произведения на графах, приведенных на рис. 5.

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


			x₁	x₂				y₁	y₂	y₃
		x₁	0	1			y₁	1	1	0
A₁	=	x₂	1	0	A₂	=	y₂	0	0	1
							y₃	0	1	0

Построим матрицу A смежности вершин результирующего графа, каждый элемент которой вычисляется согласно соотношению (4.3).


			x_1y₁	x_1y₂	x_1y₃	x_2y₁	x_2y₂	x_2y₃
		x_1y₁	a_1,11 a_2,11	a_1,11a_2,12	a_1,11 a_2,13	a_1,12a_2,11	a_1,12 a_2,12	a_1,12 a_2,13
		x_1y₂	a_1,11 a_2,21	a_1,11 a_2,22	a_1,11 a_2,23	a_1,12 a_2,21	a_1,12 a_2,22	a_1,12 a_2,23
A	=	x_1y₃	a_1,11 a_2,21	a_1,11 a_2,22	a_1,11 a_2,23	a_1,12 a_2,31	a_1,12 a_2,32	a_1,12 a_2,33
		x_2y₁	a_1,21 a_2,11	a_1,21 a_2,12	a_1,21 a_2,13	a_1,22 a_2,11	a_1,22 a_2,12	a_1,22 a_2,13
		x_2y₂	a_1,21 a_2,21	a_1,21 a_2,22	a_1,21 a_2,23	a_1,12 a_2,21	a_1,12 a_2,22	A_1,12 a_2,23
		x_2y₃	a_1,21 a_2,31	a_1,21 a_2,32	a_1,21 a_2,33	a_1,22 a_2,31	a_1,12 a_2,32	A_1,12 a_2,33

Для удобства рассмотрения разделим матрицу A на четыре квадратные подматрицы. Заметим, что каждая подматрица может быть получена путем логического элементов матрицы умножения A_{2 на один из элементов a_1,ij матрицы A_{1. С учетом этого матрицу A можно
представить так:}}


			x_1y₁	x_1y₂	x_1y₃	x_2y₁	x_2y₂	x_2y₃
		x_1y₁	a_1,11A₂	a_1,12A₂
		x_1y₂
A	=	x_1y₃
		x_2y₁	a_1,21A₂	a_1,22A₂
		x_2y₂
		x_2y₃

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


			x_1y₁	x_1y₂	x_1y₃	x_2y₁	x_2y₂	x_2y₃
		x_1y₁	0	0	0	1	1	0
		x_1y₂	0	0	0	0	0	1
A	=	x_1y₃	0	0	0	0	1	0
		x_2y₁	1	1	0	0	0	0
		x_2y₂	0	0	1	0	0	0
		x_2y₃	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, заключительный).

Не сдавайте скачаную работу преподавателю!

Данный реферат Вы можете использовать для подготовки курсовых проектов.

Доработать Узнать цену написания по вашей теме

Поделись с друзьями, за репост + 100 мильонов к студенческой карме :

Заказать работу:

!	Курсовая работа
!	Дипломная работа
!	Реферат
!	Решение задач
!	Отчет по практике
!	Контрольная работа

Пишем реферат самостоятельно:

!	Как писать рефераты Практические рекомендации по написанию студенческих рефератов.
!	План реферата Краткий список разделов, отражающий структура и порядок работы над будующим рефератом.
!	Введение реферата Вводная часть работы, в которой отражается цель и обозначается список задач.
!	Заключение реферата В заключении подводятся итоги, описывается была ли достигнута поставленная цель, каковы результаты.
!	Оформление рефератов Методические рекомендации по грамотному оформлению работы по ГОСТ.

Читайте также:

→	Виды рефератов Какими бывают рефераты по своему назначению и структуре.

Другие популярные рефераты:

Реферат	Механические волны
Реферат	Обратная матрица
Реферат	Инверсия и ее применение
Реферат	Социокультурная динамика межпоколенных взаимодействий
Реферат	Расследование преступлений в сфере компьютерной информации
Реферат	Туристско-краеведческая характеристика Калининградской области
Реферат	Организация административно-хозяйственной службы гостиницы
Реферат	Диагностика психологической готовности ребенка к школе 2
Реферат	Модель современного менеджера
Реферат	Условия формирования военно-административной системы Южного Зауралья в XVII - первой половине XIX века

Сейчас смотрят :

Реферат	10. 02. 01 – белорусский язык
Реферат	Германия во времена Габсбургов и Люксембургов
Реферат	Высокое Возрождение Италии XVI века
Реферат	История штата Аляска
Реферат	Платон - подборка разных материалов
Реферат	Империя Хань I в. до н.э. – II в. н.э. Восстание «желтых повязок»
Реферат	Государство и право Древнего Египта
Реферат	Поэт и общество в лирике Лермонтова
Реферат	Значение разделов Польского государства 1772, 1793, 1794 годов
Реферат	Идеи общественного договора и народного суверенитета в Декларации независимости США 1776г.
Реферат	«Мне дали имя при крещенье — Анна»
Реферат	Судовий захист прав та свобод людини і громадянина у сфері виконавчої влади
Реферат	Формирование государственности во Франции
Реферат	Поезд современности
Реферат	Конституция США и её особенности

Реферат по предмету "Математика"

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

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

Дуга

Дуга

(y1,y1)

(y1,y2)

(y2,y3)

(x1y1)(x1y1)

(x1y1)(x1y2)

(x1y2)(x1y3)

(z1,z1)

(z1,z2)

(z2,z3)

(y1,y1)

(y1,y2)

(y2,y3)

(z4,z4)

(z4,z5)

(z5,z6)

(x1,x2)

(z1,z4)

(x1,x2)

(z2,z5)

(x1,x2)

(z3,z6)

Граф G1 G2 изображен на рис. 4.

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

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

Другие популярные рефераты:

Сейчас смотрят :

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

(y₁,y₁)

(y₁,y₂)

(y₂,y₃)

(x₁y₁)(x₁y₁)

(x₁y₁)(x₁y₂)

(x₁y₂)(x₁y₃)

(z₁,z₁)

(z₁,z₂)

(z₂,z₃)

(y₁,y₁)

(y₁,y₂)

(y₂,y₃)

(z₄,z₄)

(z₄,z₅)

(z₅,z₆)

(x₁,x₂)

(z₁,z₄)

(x₁,x₂)

(z₂,z₅)

(x₁,x₂)

(z₃,z₆)

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

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