Реферат: Операции на графах

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
Бесплатно скачать Реферат: Операции на графах