3.2 Орграфы и матрицы

Матрицей смежностей А(D) орграфа D называется (р×р)-матрица ||a_ij||, у которой a_ij= 1, если V_iV_j- дуга орграфа D, и a_ij=0 в противном случае. Матрица смежностей которого имеет вид (рис. 26):

Рисунок 26

Легко проверить, что суммы элементов по строкам матрицы A(D) равны полустепеням исхода вершин орграфа D, а суммы элементов по столбцам - полустепеням захода.

Как и в случае графов, степени матрицы смежностей А орграфа дают полную информацию о числе маршрутов, идущих из одной вершины в другую. Теорема. (i, j)-й элемент а_ijⁿ матрицы А" равен числу маршрутов длины n, идущих из вершины v_i в вершину v_j.

Упомянем здесь вкратце еще о трех матрицах, связанных с орграфом D_s - о матрице достижимостей, матрице расстояний и матрице обходов. В матрице достижимостей R элемент r_ij равен 1,если вершина v_i достижима из v_j и равен 0 в противном случае. В матрице расстояний (i, j)-й элемент равен расстоянию из вершины v_i в вершину v_j; если же из v_i в v_j нет путей, то соответствующий элемент полагаем равным бесконечности. В матрице обходов (i, j)-й элемент равен длине наиболее длинного пути из v_i в v_j, а если таких путей нет, то опять-таки полагаем этот элемент равным бесконечности. Для орграфа D, показанного на рис. 27.

Рисунок 27

Следствие. Элементы матриц достижимостей и расстояний связаны со степенями матрицы А следующими соотношениями:

1) r_ii = 1 и d_ii = 0 для всех i;

2) r_ij = 1 тогда и только тогда, когда a_ijⁿ> 0 для некоторого n;

3) d(v_i,v_j) равно наименьшему из чисел n, для которых a_ijn> 0

Эффективных методов для нахождения элементов матрицы обходов не существует. Эта проблема тесно связана с некоторыми другими давно поставленными алгоритмическими проблемами теории графов, такими, как нахождение остовных циклов и контуров, а также решение задачи о коммивояжере.

Поэлементное произведение В×С матриц B=||b_ij|| и C=||c_ij|| имеет своим (i, j)-м элементом b_ijc_ij. Матрицу достижимостей орграфа можно использовать для нахождения его сильных компонент.