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

x₃

1

0

0

Найдем матрицу смежности вершин A = A₁ Ç A₂

			x1	x2	x3
		x1	0	0	0
A’1 Ç A’2	=	x2	1	0	1
		x3	0	0	0

Полученная матрица смежности вершин A’₁ Ç A’₂ соответствует графу G₁ Ç G₂ , изображенному на рис.2.

Композиция графов

Пусть G₁ (X,E₁ ) и G₂ (X,E₂ ) — два графа с одним и тем же множеством вершин X . Композицией G₁ (G₂ ) графов G₁ и G₂ называется граф с множеством вершин E , в котором существует дуга (x_i ,x_j ) тогда и только тогда, когда существует дуга (x_i ,x_k ) , принадлежащая множеству E₁ , и дуга (x_k ,x_j ) , принадлежащая множеству E₂ .

Рассмотрим выполнение операции композиции G₁ (G₂ ) на графах, изображенных на рис.3. Для рассмотрения операции составим таблицу, в первом столбце которой указываются ребра (x_i , x_k ) , принадлежащие графу G₁ , во втором — ребра (x_k , x_j ) , принадлежащие графу G₃ , а в третьем — результирующее ребро (x_i , x_j ) для графа G₁ (G₂ ) .

G1	G2	G1 (G2 )
(x1 ,x2 )	(x2 ,x1 ) (x2 ,x3 )	(x1 ,x1 ) (x1 ,x3 )
(x1 ,x3 )	(x3 ,x3 )	(x1 ,x3 )
(x2 ,x1 )	(x1 ,x1 ) (x1 ,x3 )	(x2 ,x1 ) (x2 ,x3 )

Заметим, что дуга (x₁ ,x₃ ) результирующего графа в таблице встречается дважды. Однако, поскольку рассматриваются графы без параллельных ребер (дуг), то в множестве E результирующего графа дуга (x₁ ,x₃ ) учитывается только один раз, т.е. E = {(x₁ ,x₁ ), (x₁ ,x₃ ), (x₂ ,x₁ ), (x₂ ,x₃ )}