Составители:
117
2.3.4. Связность структуры
Связность структуры при описании ее в виде графа характеризуется
связностью графа. Ориентированный граф будет связным (слабо связ-
ным), если между двумя любыми его вершинами существует хотя бы
один путь, и сильно связным (бисвязным), если из любой вершины гра-
фа существует путь в любую вершину графа. Таким образом, связность
графа определяет возможность связи между его вершинами.
Связность графа достаточно хорошо может быть описана с помо-
щью полной матрицы связей.
Определение 2.3.7. Полной матрицей связи графа G с n верши-
нами будем называть квадратную матрицу вида
,
n
nij
n
=γΓ
(2.3.17)
где
() ()
1,
если в графе существует хотя бы один путь
из вершины в вершину ;
0–в противном случае, =1 1 , 1 1 .
i
j
ij
xx
inj n
γ=
=
Полная матрица связи может быть легко определена по полной мат-
рице путей на основе соотношения
() ()
1, если 0;
0, если 0, 1 1 , 1 1 .
ij
ij
ij
a
ainjn
>
γ=
== =
(2.3.18)
Для графа, рассмотренного в примере 2.3.4, полная матрица связи,
полученная из полной матрицы путей (2.3.16) с использованием выра-
жения (2.3.18), имеет вид
[]
5
5
5
12 345
111111
111112
111113
111114
111115
ij
=γ =
Γ
. (2.3.19)
Страницы
- « первая
- ‹ предыдущая
- …
- 115
- 116
- 117
- 118
- 119
- …
- следующая ›
- последняя »
