Операция произведения графов.
Пусть G1(X,E1) и G2(Y,E2) - два графа.
Определение 11.7. Произведением 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 | (x1,y1)®(x2,y1) | (za, zb) |
| (x1,x2) | (y1,y1) (y1,y2) (y2,y3) (y3,y2) | (x1,y1)®(x2,y1) (x1,y1)®(x2,y2) (x1,y2)®(x2,y3) (x1,y3)®(x2,y2) | (z1,z4) (z1,z5) (z2,z6) (z3,z5) |
| (x2,x1) | (y1,y1) (y1,y2) (y2,y3) (y3,y2) | (x2,y1)®(x1,y1) (x2,y1)®(x1,y2) (x2,y2)®(x1,y3) (x2,y3)®(x1,y2) | (z4,z1) (z4,z2) (z5,z3) (z6,z2) |
Результирующий граф G1×G2 изображен на рис.11.5.
Рисунок 11.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.
Составим матрицы смежности вершин исходных графов.
| x1 | x2 | y1 | y2 | y3 | |||||||
| x1 | y1 | ||||||||||
| A1 | = | x2 | A2 | = | y2 | ||||||
| y3 | |||||||||||
Построим матрицу A смежности вершин результирующего графа, каждый элемент которой вычисляется согласно соотношению (4.3).
| x1y1 | x1y2 | x1y3 | x2y1 | x2y2 | x2y3 | |||
| x1y1 | a1,11Ù a2,11 | a1,11Ùa2,12 | a1,11Ù a2,13 | a1,12Ùa2,11 | a1,12Ù a2,12 | a1,12Ù a2,13 | ||
| x1y2 | a1,11Ù a2,21 | a1,11Ù a2,22 | a1,11Ù a2,23 | a1,12Ù a2,21 | a1,12Ù a2,22 | a1,12Ù a2,23 | ||
| A | = | x1y3 | a1,11Ù a2,21 | a1,11Ù a2,22 | a1,11Ù a2,23 | a1,12Ù a2,31 | a1,12Ù a2,32 | a1,12Ù a2,33 |
| x2y1 | a1,21Ù a2,11 | a1,21Ù a2,12 | a1,21Ù a2,13 | a1,22Ù a2,11 | a1,22Ù a2,12 | a1,22Ù a2,13 | ||
| x2y2 | a1,21Ù a2,21 | a1,21Ù a2,22 | a1,21Ù a2,23 | a1,12Ù a2,21 | a1,12Ù a2,22 | A1,12Ù a2,23 | ||
| x2y3 | a1,21Ù a2,31 | a1,21Ù a2,32 | a1,21Ù a2,33 | a1,22Ù a2,31 | a1,12Ù a2,32 | A1,12Ù a2,33 |
Для удобства рассмотрения разделим матрицу A на четыре квадратные подматрицы. Заметим, что каждая подматрица может быть получена путем логического элементов матрицы умножения A2 на один из элементов a1,ij матрицы A1. С учетом этого матрицу A можно представить так:
| x1y1 | x1y2 | x1y3 | x2y1 | x2y2 | x2y3 | |||
| x1y1 | a1,11ÙA2 | a1,12ÙA2 | ||||||
| x1y2 | ||||||||
| A | = | x1y3 | ||||||
| x2y1 | a1,21ÙA2 | a1,22ÙA2 | ||||||
| x2y2 | ||||||||
| x2y3 |
Таким образом, матрица смежности вершин графа G1×G2 имеет вид:
| x1y1 | x1y2 | x1y3 | x2y1 | x2y2 | x2y3 | |||
| x1y1 | ||||||||
| x1y2 | ||||||||
| A | = | x1y3 | ||||||
| x2y1 | ||||||||
| x2y2 | ||||||||
| x2y3 |
Нетрудно убедиться, что полученной матрице смежности вершин соответствует граф G1×G2, представленный на рис. 11.5.