3.4.2. Бинарные операции

Бинарные операции поволяют формировать новые графы в результате объединения, пересечения, разности, композиции, произведения или суммы двух или нескольких графов.

При исполнении операций над двумя графами G₁=<X₁, r₁> и G₂=<X₂, r₂> следует обратить внимание на наличие общих элементов для X₁ и X₂ и/или r₁ и r₂. Это позволяет выделить три конструктивных объекта:

1. вершины и рёбра (дуги) не имеют общих элементов, т.е. (X₁X₂)= и (r₁r₂)=;

2. вершины имеют общие элементы, а рёбра (дуги) - нет, т.е. (X₁X₂) и (r₁r₂)=;

3. вершины и рёбра (дуги) имеют общие элементы, т.е. (X₁X₂) и (r₁r₂).

3.4.2.1. Объединение графов

Граф G=G₁G₂), для которого X=(X₁X₂) и r=(r₁r₂) есть объединение графов G₁=<X₁, r₁> и G₂=<X₂, r₂>.

Для вычисления матрицы смежности формируемого графа сле­дует использо­вать матрицы смежности исходных графов. Матрицы смежности всех графов должны иметь число строк и столбцов |X|=|(X₁X₂)|. Значение смежности вычисляют по формуле:

r(i, j)=r⁽¹⁾(i, j)  r⁽²⁾(i, j).

На рис. 3.18 показан результат этой операции для трех конструктивных объектов.

Ниже приведены матрицы для вычисления объединения графов G₁ и G₂ по рис. 3.18с).

r1	x1	x2	x3	x4		r2	x1	x2	x3	x4
x1	0	1	1	0		x1	0	1	0	1
x2	1	0	1	0		x2	1	0	1	0	=
x3	1	1	0	0		x3	0	1	0	1
x4	0	0	0	0		x4	1	0	1	0
						r	x1	x2	x3	x4
					=	x1	0	1	1	1
						x2	1	0	1	0
						x3	1	1	0	1
						x4	1	0	1	0