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

Если в графе 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
	x2
А =	x3
	x4
	x5

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

Матрица 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).

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