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

Матрицей смежностей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. Заменить каждый единичный элемент матрицы А соответствующим ему элементом матрицы М.

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

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