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

Если в графе G(X) через а_ij обозначить число дуг, идущих из x_i в x_j, то матрица A = || а_ij || (i = 1, ..., n; j=1, ..., n; где n – число вершин графа) называется матри­цей смежности вершин графа.

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

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

 

Рис. 3.21. Пример графа для определения матрицы

смежности A

Матрицей смежности ребер графа называется такая матрица В = || b_ij || (I = 1, ..., m; j = 1, ..., m; где m - число ребер графа), что:

bij =

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

 

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

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

sij =

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

-1, если g_j заходит в х_i,

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

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

Для неорграфа матрица R = || r_ij || размером n х m, где:

rij =

1, если х_i (i = 1, ..., n) инцидентна g_j (j = 1, ..., m),

 

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

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

 

Рис. 3.22. Пример графа для определения матриц S и R