Декартово произведение графов.

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

Определение 11.6. Декартовым произведением 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₃).

Рисунок 11.4.

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

Граф G₁´ G₂ изображен на рис. 11.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.

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

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

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

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

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

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