2.3 Матрицы смежности и инциденций графа

Если в графе G(X) через a_ij обозначить число дуг, идущих из x_i в x_j, то матрица || a_ij || с n строками и n столбцами называется матрицей смежно­сти вершин графа. Здесь a_ij – элемент, стоящий на пересечении i-й строки и j-го столбца, a_i – i-я вектор-строка, a_j – j-й вектор-столбец.

		x1	x2	x3	x4	x5
	x1	0	1	0	0	1
	x2	0	0	0	0	1
А =	x3	0	1	0	1	0
	x4	0	0	0	0	1
	x5	0	0	0	0	1

Наличие нулевого элемента на главной диагонали означает отсут­ствие петли в соответствующей вершине.

Матрица A^T соответствует графу G^-1(X).Матрица А является симметри­ческой тогда и только тогда, когда граф G(X) – симметрический. Матрица А антисимметрична тогда и только тогда, когда граф G(X) – антисимметрический. Матрица А полна тогда и только тогда, когда граф G(X) – полный (a_ij + a_ji  1).

Матрицей смежности ребер графа называется такая матрица

В = || b_ij || (i = 1, …, m; j = 1, …, m, где m – число ребер графа), что

1, если ребра g_i и g_j имеют общий конец,

b_ij =

0 в противном случае.

Пусть g₁ ,…, g_m – дуги, а x₁ ,…, x_n – вершины ориентированного графа G(X). Матрица S = || s_ij || (i = 1, …, n – номер вершины графа, j = 1, …, m – номер дуги графа), такая что

1, если g_j исходит из x_i,

s_ij = -1, если g_j заходит в x_i,

0, если g_j не инцидентна x_i

называется матрицей инциденций для дуг графа.

Матрица R = || r_ij || размером n  m, где

1, если x_i (i = 1, …, n) инцидентна g_j (j = 1, …, m),

r_ij =

0 в противном случае

называетсяматрицей инциденций для ребер графа (рис. 2.23).

	0	1	0	1	0	0		0	1	0	1	0	0
	1	0	1	0	0	0		1	0	1	0	0	0
S =	-1	-1	0	0	0	0	, R =	1	1	0	0	0	0	.
	0	0	-1	-1	1	1		0	0	1	1	1	1
	0	0	0	0	-1	0		0	0	0	0	1	0
	0	0	0	0	0	-1		0	0	0	0	0	1

2.4 Операции над графами Сумма графов

Пусть даны два графа G₁(X) и G₂(X) на одном и том же множестве вершин. Тогда суммой G(X), графовG₁(X) и G₂(X) является граф, состоя­щий из ребер, принадлежащих G₁(X), либо G₂(X). Таким образом, если

(x_i', x_j')  G₁(X)и (x_i'', x_j'') G₂(X), то (x_i', x_j') G(X) и (x_i'', x_j'') G(X)

 (x_i', x_j', x_i'', x_j'') X.

Символически сумму двух графов обозначают следующим образом:

G(X) = G₁(X)  G₂(X). Аналогично определяется сумма n графов G_i(X)

(i =1, …, n): _n

G(X) =  G_i(X)

^{i =1}

как граф, состоящий из ребер, принадлежащих хотя бы одному из графов G_i(X) (рис. 2.24, а, б).

Операция суммирования графов обладает переместительным свойст­вом, то есть G₁(X)  G₂(X) = G₂(X)  G₁(X).

Пример 1.

Рассмотрим случай, когда операция суммы графов применяется к графам, определенным на различных множествах вершин. Тогда суммой G(X) будет граф _n

G(X) = G₁(X₁)  G₂(X₂)  …  G_n(X_n) =  G_i(X_i),

ⁱ⁼¹

для которого справедливо: Х = Х₁  Х₂  …  Х_n и

_n

G(x_j) = G₁(x_j)  G₂(x_j)  …  G_n(x_j) =  G_i(x_j), x_j  X (рис. 2.25).

ⁱ⁼¹

Пример 2.