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

Матрицей смежностей A (D) орграфа D называется (р´р)-матрица

у которой aij = 1, если viuj- дуга oprpaфа D, и аij=0 в противном случае.

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

Как и в случае графов, степени матрицы смежностей А орграфа дают полную информацию о числе маршрутов, идущих из одной вершины в другую.

Теорема (i, j)-й элемент аij матрицы Аⁿ равен числу маршрутов длины n, идущих из вершины vi в вершину vj.

Упомянем здесь вкратце еще о трех матрицах, связанных с орграфом D -

о матрице достижимостей, матрице расстояний и матрице обходов. В матрице достижимостей R элемент rij равен 1, если вершина vi достижима из vj, и равен 0 в противном случае. В матрице расстояний (i, j)-й элемент равен расстоянию из вершины vi в вершину vj, если же из vi в vj нет путей, то соответствующий элемент полагаем равным бесконечности. В матрице обходов (i, j)-й элемент равен длине наиболее длинного пути из vi в vj, а если таких путей нет, то опять-таки полагаем этот элемент равным бесконечности.

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

1) rij=1 и dij=0 для всех i;

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

3) d(vi, vj) равно наименьшему из чисел n, для которых аijⁿ> 0, и ¥, если таких чисел нет.

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

Следствие (б). Пусть vi- вершина орграфа D. Сильные компоненты орграфа D, содержащие vi, определяются единичными элементами i-й строки (или i-го столбца) матрицы R´RT.

Формула для числа остовных входящих деревьев данного орграфа была найдена Боттом и Мейберри, а доказана Таттом. Чтобы сформулировать этот результат, известный как матричная теорема о деревьях для орграфов, введем еще матрицы, связанные с D. Обозначим через Mod матрицу, полученную из -А заменой i-ro элемента главной диагонали на od (vi). Двойственным образом определим матрицу Мid.

Теорема. Для каждого помеченного орграфа D алгебраическое дополнение любого элемента i-й строки матрицы Мid равно числу остовных входящих деревьев, у которых вершина vi является стоком.

Теорема. Для каждого помеченного орграфа D алгебраическое дополнение любого элемента j-го столбца матрицы Mid равно числу остовных выходящих деревьев, у которых вершина vj является источником.

Следующий алгоритм (Харари) иногда упрощает вычисление собственных значений матрицы М, а также нахождение матрицы, обратной к М (если она существует).

1. Образовать орграф D, связанный с М.

2. Определить сильные компоненты орграфа D.

3. Образовать конденсацию D*.

4. Упорядочить сильные компоненты так, чтобы матрица смежностей орграфа D* стала верхней треугольной.

5. Используя сильные компоненты, переупорядочить вершины орграфа D так, чтобы привести его матрицу смежностей А к верхнему треугольному виду.

6. Заменить каждый единичный элемент матрицы А соответствующим ему элементом матрицы М.

Собственные значения матрицы М являются собственными значениями диагональных блоков новой матрицы, а матрицу, обратную к М, можно найти, обращая эти диагональные блоки.

Если М — разреженная матрица (или, скорее, матриц с таким расположением нулевых элементов, что в графе имеется несколько сильных компонент), то указанный алгоритм может быть весьма эффективным. Вариант этого алгоритма (иногда более эффективный, но также и более сложный) для двудольных графов был дан Далмеджем и Мендельсоном.