Составители:
118
Анализ полной матрицы связей показывает, что в графе существуют
пути из любой вершины в любую вершину, следовательно, данный граф
является сильно связным.
Элементы полной матрицы связи могут быть определены также с
помощью квазиминоров
() ()
,11,11,
ij lk
kl u
kl
knln
−
=
γ==
если при их вычислении сложение понимать в булевом смысле (как ло-
гическое), т. е. предполагать, что
0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1+ 1 = 1,
а длины дуг принимать равными единице.
Для вычисления полной матрицы связей ориентированного графа без
петель и контуров можно использовать еще один достаточно простой спо-
соб, в основе которого положено определение матрицы
s
n
R
по формуле
[]
1
,
n
sk
n
n
k=
=
∑
RR
(2.3.20)
где R
[n]
– матрица смежности вершин графа.
После вычисления матрицы
s
n
R
полную матрицу связей получают
на основе соотношения
() ()
1, если 0;
0, если 0, 1 1 , 1 1 .
s
ij
ij
s
ij
r
rinjn
>
γ=
== =
(2.3.21)
Анализ связности графа позволяет выявить наличие обрывов или от-
сутствие необходимых связей в системе, а также наиболее уязвимые
связи и элементы, удаление которых может привести к распаду систе-
мы на отдельные, не связанные между собой, подсистемы.
2.3.5. Значимость элементов в структуре системы
Методы теории графов позволяют определять и такую структурную
характеристику системы, как значимость элемента в ее структуре. Ес-
тественно предположить, что, чем больше связей имеет элемент с дру-
