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

Пусть 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_1×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_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.

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

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

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

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

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