Операции на графах (стр. 4 из 5)

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

			*x₁y₁*	*x₁y₂*	*x₁y₃*	*x₂y₁*	*x₂y₂*	*x₂y₃*
		*x₁y₁*	1	1	0	1	0	0
		*x₁y₂*	0	0	1	0	1	0
A	=	*x₁y₃*	1	0	0	0	0	1
		*x₂y₁*	1	0	0	1	1	0
		*x₂y₂*	0	1	0	0	0	1
		*x₂y₃*	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₂, а в третьем и четвертом – дуги результирующего графа.

G₁

G₂

(x_1,y₁)®(x₂,y₁)

(z_a, z_b)

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

a_a_b =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₁y₁*	*x₁y₂*	*x₁y₃*	*x₂y₁*	*x₂y₂*	*x₂y₃*
		*x₁y₁*	a_1,11Ù a_2,11	a_1,11Ùa_2,12	a_1,11Ù a_2,13	a_1,12Ùa_2,11	a_1,12Ù a_2,12	a_1,12Ù a_2,13
		*x₁y₂*	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₁y₃*	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₂y₁*	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₂y₂*	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₂y₃*	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₂ на один из элементов a_1,ijматрицы A₁. С учетом этого матрицу A можно представить так:

			*x₁y₁*	*x₁y₂*	*x₁y₃*	*x₂y₁*	*x₂y₂*	*x₂y₃*
		*x₁y₁*	a_1,11ÙA₂			a_1,12ÙA₂
		*x₁y₂*
A	=	*x₁y₃*
		*x₂y₁*	a_1,21ÙA₂			a_1,22ÙA₂
		*x₂y₂*
		*x₂y₃*

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