Реферат: Операции на графах
0
0
1
1
0
x2 y2
0
1
0
0
0
1
x2 y3
0
0
1
1
0
0
Нетрудно убедиться, что полученной матрице смежности вершин соответствует граф 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 =(x1 y1 ), z2= (x1 y2 ), z3 =(x1 y3 ), z4 =(x2 y1 ), z5 =(x2 y2 ), z6 =(x2 y3 ) .
Определим множество дуг результирующего графа. Для удобства рассмотрения составим таблицу, в первом столбце которой указываются дуги графа G1 , во втором – дуги графа G2 , а в третьем и четвертом – дуги результирующего графа.
G1 | G2 | (x1, y1 ) ®(x2 ,y1 ) |
(z a , z b ) |
(x1 ,x2 ) | (y1 ,y1 ) (y1 ,y2 ) (y2 ,y3 ) (y3 К-во Просмотров: 998
Бесплатно скачать Реферат: Операции на графах
|