Если в графе G(X) через аij обозначить число дуг, идущих из xi в xj, то матрица A = || аij || (i = 1, ..., n; j=1, ..., n; где n – число вершин графа) называется матрицей смежности вершин графа.
Наличие нулевого элемента на главной диагонали означает отсутствие петли в соответствующей вершине.
Матрица Ат соответствует графу G-1(X). Матрица А является симметрической тогда и только тогда, когда граф G(X) – симметрический. Матрица А антисимметрична тогда и только тогда, когда граф G(X) – антисимметрический. Матрица А полна тогда и только тогда, когда граф G(X) – полный (аij + аji ³ 1).
Рис. 3.21. Пример графа для определения матрицы
смежности A
Матрицей смежности ребер графа называется такая матрица В = || bij || (I = 1, ..., m; j = 1, ..., m; где m - число ребер графа), что:
1, если ребра gi и gj имеют общий конец,
0 в противном случае.
Пусть g1, ..., gm – дуги, х1, ..., хn – вершины ориентированного графа G(X). Матрица S = || sij || (I = 1, ..., n – номер вершины графа, j = 1, ..., m – номер дуги графа), такая что:
1, если gj исходит из хi,
-1, если gj заходит в хi,
0, если gj не инцидентна хi
называется матрицей инциденций для дуг графа.
Для неорграфа матрица R = || rij || размером n х m, где:
1, если хi (i = 1, ..., n) инцидентна gj (j = 1, ..., m),
0 в противном случае
называется матрицей инциденций для ребер графа.
Рис. 3.22. Пример графа для определения матриц S и R
