Операции на графах

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

Заметим, что в

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

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

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

Операция произведения графов. Пусть G1(X,E1) и G2(Y,E2) - два графа. Произведением G1×G2 графов G1 и G2 называется граф с множеством вершин X´Y, а дуга из вершины (xi,yj) в вершину (xk,yl) существует тогда и только тогда, когда существуют дуги (xi,xk) Î E1 и (yj,yl) Î E2.

Выполнение операции произведения рассмотрим на примере графов, изображенных на рис. 5. Множество вершин Z результирующего графа определяется как декартово произведение множеств X´Y. Множество Z содержит следующие элементы: z1=(x1y1), z2=(x1y2), z3=(x1y3), z4=(x2y1), z5=(x2y2), z6=(x2y3).

Определим множество дуг результирующего графа. Для удобства рассмотрения составим таблицу, в первом столбце которой указываются дуги графа G1, во втором – дуги графа G2, а в третьем и четвертом – дуги результирующего графа.

Результирующий граф G1×G2 изображен на рис.5.

Операция произведения обладает следующими свойствами.

1. G1×G2 = G2×G1.

2. G1×(G2×G3) = (G1×G2)×G3.

Рассмотрим выполнение операции произведения графов в матричной форме.

Пусть G1(X,E1) и G2(Y,E2) – два графа, имеющие nx и ny вершин соответственно. Результирующий граф G1×G2 имеет nx×ny вершин, а его матрица смежности вершин - квадратная матрица размером (nx×ny)´ (nx ×ny). Обозначим через aab = a(ij)(kl) элемент матрицы смежности вершин, указывающий на наличие дуги (ребра), соединяющей вершину za=(xiyj) c zb=(xkyl). Этот элемент может быть вычислен при помощи матриц смежности вершин исходных графов следующим образом:

aab =a(ij)(kl) = a1,ik Ù a2,jl, (3)

де a1,ik, a1,ik – элементы матрицы смежности вершин графов G1 и G2 соответственно.

Пример 5. Выполнить операцию произведения на графах, приведенных на рис. 5.

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

 Скачать реферат