3.4.2.2. Пересечение графов

Граф G=(G₁G₂), для которого X=(X₁X₂) и r=(r₁r₂) есть пересечение графов G₁=<X₁, r₁> и G₂=<X₂, r₂>. На рис. 3.19 дан результат исполнения этой операции.

Для вычисления матрицы смежности формируемого графа сле­дует использо­вать матрицы смежности исходных графов.

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

: r_i,j=r⁽¹⁾(i, j) r⁽²⁾(i, j).

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

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
						x1	0	1	0	0
						x2	1	0	1	0
						x3	0	1	0	0
						x4	0	0	0	0

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

Граф G=(G₁G₂)=<X, r>, для которого X(X₁X₂), а r_i,jr существует тогда и только тогда, когда есть хотя бы одна вершина x_k, принадлежащая графам G₁ и G₂, что обеспечивает маршрут через вершину x_k, с началом в x_i⁽¹⁾X₁ и концом в x_j⁽²⁾X₂.

На рис. 3.20 дан результат исполнения этой операции.

Значение смежности вычисляют по формуле:

r(i, j)= _k=1ⁿ(r⁽¹⁾(i, k)r⁽²⁾(k, j).

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

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