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

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

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

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

Пусть – граф и | V | = p.

Определение. Матрицей смежности неориентированного графа называется квадратная матрица с р строками и с р столбцами. Элементы матрицы определяются правилом:

Матрицу смежности обозначим буквой А.

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

j i

Рис. 9

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

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

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

· <=> , матрица смежности симметрична относительно главной диагонали, она совпадает со своей транспонированной.

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

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

Рис. 10

Дата добавления: 2014-12-07