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

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

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

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

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

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

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

Утверждение. Если А – матрица смежности графа , то элемент матрицы А^п равен числу маршрутов длины п, соединяющих вершины v_i и v_j графа G.

Доказательство. Методом математической индукции по числу п.

База индукции. При п = 1 утверждение верно, так как всякое ребро графа G – это маршрут длины 1.

Индуктивное предположение. Пусть утверждение справедливо для всех n £ k.

Индуктивный переход. Рассмотрим матрицу А^{k +1}. В ней .

В силу индуктивного предположения произведение есть число маршрутов длины k + 1, соединяющих вершину v_i с вершиной v_j с предпоследней вершиной всех таких маршрутов - v_m. Значит, сумма действительно равна числу маршрутов длин k + 1, соединяющих вершину v_i с вершиной v_j.

Следствие. Пусть – связный граф с р вершинами. Тогда любые две вершины графа можно соединить простой цепью. Но в простой цепи не может быть более (р - 1) ребер. Следовательно, все элементы матрицы отличны от нуля. Ясно, что верно и обратное утверждение.

В некоторых случаях при вычислениях степеней матрицы А и матрицы С важно знать не число соответствующих маршрутов, а только есть ли в графе эти маршруты или нет. Тогда при вычислении элементов матриц А ², А ³, …, А^{р -1} вместо обычного сложения используют операцию Å, введенную нами при рассмотрении матриц конечных бинарных отношений. В результате матрицы А, А ², А ³, …, A^{p- 1}, C состоят только из нулей и единиц.

Полученная таким образом матрица С называется матрицейдостижимости графа G. Граф G связен тогда и только тогда, когда каждый элемент матрицы достижимости равен 1 (р ³ 3).

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