лекции по дм. лекции. Основные понятия теории множеств. Способы задания множеств 4 Диаграммы Венна. 4
 Скачать 1.51 Mb.
|
Декартово произведение графов.Пусть G1(X,E1) и G2(Y,E2) — два графа. Определение 11.6. Декартовым произведением G1(X,E1)G2(Y,E2) графов G1(X,E1) и G2(X,E2) называется граф с множеством вершин XY, в котором дуга (ребро), идущая из вершины (xiyj) в (xkyl), существует тогда и только тогда когда существует дуга (xixk), принадлежащая множеству дуг E1 и j = l или когда существует дуга (yj,yl), принадлежащая множеству E2 и i = k. Выполнение операции декартова произведения рассмотрим на примере графов, изображенных на рис. 4. Множество вершин Z результирующего графа определяется как декартово произведение множеств XY. Множество Z содержит следующие элементы: z1=(x1y1), z2=(x1y2), z3=(x1y3), z4=(x2y1), z5=(x2y2), z6=(x2y3).  Рисунок 11.4. Определим множество дуг результирующего графа. Для этого выделим группы вершин множества Z, компоненты которых совпадают. В рассматриваемом примере пять таких групп: две группы с совпадающими компонентами из множества X, и три группы, имеющие совпадающие компоненты из Y. Рассмотрим группу вершин результирующего графа, которые имеют общую компоненту x1: z1=(x1y1), z2=(x1y1), z3=(x1y3). Согласно определению операции декартова произведения графов, множество дуг между этими вершинами определяется связями между вершинами множества Y. Таким образом, дуга (y1,y1) в графе G2 определяет наличие дуги (z1,z1) в результирующем графе. Для удобства рассмотрения всех дуг результирующего графа составим таблицу, в первом столбце которой перечисляются вершины с совпадающими компонентами, во втором – дуги между несовпадающими компонентами, а в третьем и четвертом – дуги в результирующем графе.
Граф G1 G2изображен на рис. 11.4. Операция декартова произведения обладает следующими свойствами. 1. G1G2 = G2G1 2. G1(G2G3) = (G1G2)G3. Операция декартова произведения графов может быть выполнена в матричной форме. Пусть G1(X,E1) и G2(Y,E2) – два графа, имеющие nx и ny вершин соответственно. Результирующий граф G1G2 имеет nxny вершин, а его матрица смежности вершин - квадратная матрица размером (nxny) (nx ny). Обозначим через a = a(ij)(kl) элемент матрицы смежности вершин, указывающий на наличие дуги (ребра), соединяющей вершину z=(xiyj) c z=(xkyl). Согласно определению операции этот элемент может быть вычислен при помощи матриц смежности вершин исходных графов следующим образом: a = a(ij)(kl) = Kika2,jl Kjla1,ik, (2) где a1,ik, a2,jl – элементы матрицы смежности вершин графов G1 и G2 соответственно; Kik – символ Кронекера, равный 1, если i=k, и нулю, если ik . Пример. Выполнить операцию декартова произведения на графах, приведенных на рис. 4. Составим матрицы смежности вершин исходных графов.
Для построения матрицы смежности результирующего графа воспользуемся соотношением (2). В этом соотношении первое слагаемое Kika2,jlуказывает на наличие дуг для вершин, у которых совпадают компоненты из множества X. Для пояснения сказанного, рассмотрим вспомогательную матрицу Axy, в которой элементы, для которых Kik = 1, помечены символом X. Эти элементы принимают значения, равные значениям соответствующих элементов матрицы A2смежности вершин графа G2, так, как это показано для матрицы A*.
Второе слагаемое Kjla1,ikсоотношения(2) указывает на наличие дуг для групп вершин, у которых совпадают компоненты из множества Y. В матрице Axy элементы, для которых Kjl = 1 помечены символом Y. Эти элементы принимают значения, равные значениям соответствующих элементов матрицы A1смежности вершин графа G1, так, как это показано для матрицы A*. Заметим, что в матрицах Axy и A* на главной диагонали располагаются элементы, равные логической сумме значений элементов матриц смежности вершин обоих графов. Это определяется тем, что на главной диагонали расположены элементы, для которых Kik = Kjl = 1. Таким образом, матрица смежности вершин результирующего графа принимает вид:
Нетрудно убедиться, что полученной матрице смежности вершин соответствует граф G1G2, представленный на рис. 4 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||