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

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

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

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

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

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

Если в орграфе G р вершин и q дуг, то элементы его матрицы инцидентности определяются правилом

i = 1, …, p; j = 1, …, q.

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

Рис. 12

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

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

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

· В каждом столбце матрицы есть ровно одна единица и ровно одна единица с минусом, так как всякая дуга из одной вершины выходит и в одну вершину входит.

Дата добавления: 2014-12-07; Просмотров: 1002; Нарушение авторских прав?; Мы поможем в написании вашей работы!