Свойства матрицы смежности ориентированного графа

Матрица смежности ориентированного графа.

Это квадратная матрица, в которой р строк и р столбцов, элементы которой определяются правилом

Пример орграфа и его матрицы смежности показан на рис. 10.

Рис. 10

· Число единиц в i- ой строке равно степени выхода i- ой вершины, i = = 1, 2, …, р.

· Число единиц в - м столбце равно степени входа - ой вершины, = 1, 2, …, р.

· Число единиц в матрице равно числу дуг в графе.

· Матрица смежности не симметрична относительно главной диагонали.