Классификационные построения в экологии и систематике - Андреев В.Л.
Скачать (прямая ссылка):
А' + А'т:
¦А Ат А' + Ат'
О о о
о о о
0 . 1 -Г о = 0 . 1
о
О 0 1 . 0 1 .
о
Слабосвязные компоненты орграфа, содержащие i-ю вершину, определяются единичными элементами i-й строки матрицы А' +
— А'т. В данном примере замечаем, что единичные элементы имеют 5-я и 7-я строки: соответствующие вершины орграфа принадлежат слабосвязной компоненте аг = {5, 7}.
Для определения связей, удаление которых приводит к разрушению системы, упорядочиваем строки и столбцы матрицы смежностей А в соответствии с выделенными подсистемами:
1 2 3 6 8 5 7 4
1 . 1 . )
2 i . 1 1 Г1
3 1 1 . 1 . 1 1
6 . 1 . 1 1
8 1 . . 1 [ »2
5 . 1 } а1
7
4 ,
Единичные элементы (нули для наглядности опущены) за пределами очерченных квадратиков соответствуют искомым связям: а-ц,
®35> ®34! &67 > &$~-
Рис. 5.2. Орграф сокращенной системы
После декомпозиции систему можно представить как сокращенную (рис. 5.2), в которой элементами являются выделенные подсистемы. Орграф сокращенной системы является удобной моделью для решения многих последующих информационных и диагностических задач.
3 В. Л. Андреев
65
5.2. Нанкратчайшпе н наидлиннейшие пути
Матричное представление графов хотя и менее наглядно, чем рафическое, обладает определенными преимуществами: дает воз-ожность использовать ЭВМ п, следовательно, позволяет автомати-ировать трудоемкие процессы их анализа. В предыдущем пара-рафе была введена операция сложения матриц, сейчас же введем ще одну операцию: произведением матриц А и В называется [атрица С:
(5-4)
3
1 которой элемент, стоящий в i-fi строке и в к-м столбце, равен сум-ie произведений элементов г-й строки матрицы А и к-то столбца ттрицы В.
Пусть даны матрицы
а а а12 «13 &11 &12 &13
А = в21 а22 а23 , 5 = &21 &22 &23
а-л а32 а33 , Ъп ^32 Ьзз
Элементы первой строки матрицы С = А-В подсчитываются как
= ^11^11 “Г й12^21 "Г" ®13^31>
Cl2 = ЧцЬ 12 ~7- + а13^32)
^13 ^ ®и^1з 4" %з^зз-
Аналогично подсчитываются элементы последующих строк.
Перейдем теперь к анализу матриц смежностей, которые несут полную информацию о графах. В частности, степени матрицы смежностей А орграфа дают полную информацию о числе маршрутов, идущих от одной вершины в другую: элемент яу матрицы Ап равен числу маршрутов длины п, идущих из вершины Rt в вершину Rj.
Кроме матрицы смежностей, с орграфом связаны матрица достижимостей, матрица расстояний D и матрица обходов V. В матрице достижимостей R элемент г13 = 1, если i-я вершина
достижима из /-й, и равен нулю в противном случае. В матрице D
элемент dц равен расстоянию (длине кратчайшего пути) из г-й вершины в /-ю, если же такого пути не существует, то dtj = ос. В матрице V элемент vi} равен длине наиболее длинного пути из i-й вершины в j-ю, если же такого пути нет, то — 00.
Элементы матриц достижимостей и расстояний связаны с элементами матрицы смежностей следующими соотношениями:
1) ги == 1 тогда и только тогда, когда а?,- 0 для некоторого п\
2) dij равно наименьшему из чисел п, для которых а*} О, и бесконечности, если таких чисел нет.
Эффективных методов для нахождения элементов матрицы обходов не существует.
Используем утверждения 1) и 2) для нахождения элементов наикратчайшего пути из г-й вершины в j-ю. Для иллюстрации вычислительных процедур обратимся снова к орграфу на рис. 5.1 и определим наикратчайший путь из вершины 1 в вершину 7:
А А2
1 2 3 4 5 6 7 8
1 .1...... .011....
2 1.11.... 1 . .11.1.
3 11.11.1. 11.1. . 1 .
4 ........
5 ......1 . У
6 ......11 ......1 .
i ......1 .
8
1 .
2 2
А3 1 1 1 . 2 1
(5.5)
Здесь, как и ранее, нули заменены точками. В А элемент al7 = О, следовательно, вершины 1 тп 7 соединены путем, большим 1; в Л* этот же элемент равен нулю, следовательно, искомый путь больше 2; в А3 элемент al7 = 1, откуда заключаем, что наикратчайший путь из верпшны 1 в вершину 7 равен 3 (показателю степени Л3). А3 можно рассматривать также как перечисление маршрутов длиной 3 между всеми вершинами. Однако, чтобы полу- • чить матрицу достижимостей, возведение в степень следует вести до тех пор, пока показатель степени не станет равным порядку матрицы (п — 8).
Разберем еще один способ определения наикратчапшнх, а также наидлин-нейшпх путей в графе. Пусть требуется найти оба эти пути от вершины 1 к вершине 7. Все возможные пути от точки 1 можно представить (рис. 5.3) в виде де- рцс g 3 Дерево ддя оцре_ рева, графа, не имеющего замкнутых деления маршрутов от вер-путей (циклов). Способ построения де- шины 1 к вершине 7
