Орграфы и матрицы
Матрицей смежностей A (D) орграфа D называется (р´р)-матрица
у которой aij = 1, если viuj- дуга oprpaфа D, и аij=0 в противном случае.
Легко проверить, что суммы элементов по строкам матрицы A (D) равны полустепеням исхода вершин орграфа D, а суммы элементов по столбцам — полустепеням захода.
Как и в случае графов, степени матрицы смежностей А орграфа дают полную информацию о числе маршрутов, идущих из одной вершины в другую.
Теорема(i, j)-й элемент аij матрицы Аn равен числу маршрутов длины 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 тогда и только тогда, когда aijn>0 для некоторого n;
3) d(vi, vj) равно наименьшему из чисел n, для которых аijn> 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. Заменить каждый единичный элемент матрицы А соответствующим ему элементом матрицы М.
Собственные значения матрицы М являются собственными значениями диагональных блоков новой матрицы, а матрицу, обратную к М, можно найти, обращая эти диагональные блоки.
Если М — разреженная матрица (или, скорее, матриц с таким расположением нулевых элементов, что в графе имеется несколько сильных компонент), то указанный алгоритм может быть весьма эффективным. Вариант этого алгоритма (иногда более эффективный, но также и более сложный) для двудольных графов был дан Далмеджем и Мендельсоном.