Операция произведения графов.

Пусть G₁(X,E₁) и G₂(Y,E₂) - два графа.

Определение 11.7. Произведением 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₂ изображен на рис.11.5.

Рисунок 11.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.

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

			x1	x2				y1	y2	y3
		x1					y1
A1	=	x2			A2	=	y2
							y3

Построим матрицу 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₂ имеет вид:

			x₁y₁	x₁y₂	x₁y₃	x₂y₁	x₂y₂	x₂y₃
		x₁y₁
		x₁y₂
A	=	x₁y₃
		x₂y₁
		x₂y₂
		x₂y₃

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

<19 20 212223 24 25 >

Дата добавления: 2021-07-22; просмотров: 531;

Операция произведения графов.

Публикации по технике и механике

Публикации по биологии

Публикации по информатике

Публикации по строительству

Публикации по физике

Публикации по химии

Публикации по электронике

Публикации по искусству

Публикации по истории

Публикации по медицине

Публикации по педагогике