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

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

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

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

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

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

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

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

Пусть – неориентированный граф с р вершинами и q ребрами. Произвольно переномеруем его вершины и ребра.

Определение. Матрицей инцидентности графа называется матрица с р строками (каждая строка соответствует одной из вершин графа) и q столбцами (каждый столбец соответствует одному из ребер графа), элементы которой определяются правилом

Пример графа и его матрицы инцидентности приведен на рис. 11

j i

Рис. 11

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

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

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

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