Составители:
103
графе не превышает n – 1. Поэтому, начиная с некоторого
()
21
kn
∈
,
степени матрицы смежности будут представлять собой нулевые мат-
рицы, т. е.
[]
()
() ()
0, 1 , 2 1 .
l
n
lk k n
==∞∈
R
(2.3.5)
Следовательно, выполнение соотношения (2.3.5) свидетельствует об
отсутствии петель и контуров в графе. Если же при последовательном
возведении матрицы смежности в степень появляются ненулевые эле-
менты на ее главной диагонали, то это говорит о наличии контуров в
графе.
Рассмотрим применение указанных выше правил анализа структур
систем по графу на примерах.
Пример 2.3.1
Пусть диаграмма графа имеет вид, приведенный на рис. 2.3.2, а.
Определить наличие изолированных, висячих, тупиковых вершин, а так-
же петель и контуров в графе.
Решение. Матрица смежности вершин графа имеет вид
[]
3
123
0111
0012
0003
=
R
.
В матрице первый столбец и третья строка содержат только нули,
следовательно, первая вершина в графе – висячая, а третья – тупико-
3
2
1
Рис. 2.3.2. Диаграммы графов для примеров: а – 2.3.1; б – 2.3.2
б)
а)
4
3
2
1
Страницы
- « первая
- ‹ предыдущая
- …
- 101
- 102
- 103
- 104
- 105
- …
- следующая ›
- последняя »
