Математические модели в управлении. Заболотский В.П - 102 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

102
Для выявления контуров длины 3 в матрице
[]
()
2
n
Q
приравнивают нулю
ненулевые элементы главной диагонали, если они есть, и умножают
полученную матрицу на матрицу Q
n
:
[]
()
[]
()
[]
32
,
n
nn
′
=
Q
QQ
где
[]
()
2
n
′
Q
– матрица, полученная из матрицы
[]
()
2
n
Q
после приравнива-
ния нулю ненулевых элементов главной диагонали.
Не равные нулю элементы главной диагонали матрицы
[]
()
3
n
Q
свиде-
тельствуют о наличии контуров длины 3 в графе. Если все элементы
главной диагонали матрицы равны нулю, то контуров длины 3 в графе нет.
В общем случае для выявления наличия контуров длины k необхо-
димо вычислять матрицу
[]
()
[]
()
[]
()
1
,21,
kk
n
nn
kn
′
−
==
Q
QQ
(2.3.4)
где
[]
()
[]
1
n
′
=
QQ
– матрица, полученная из матрицы R
[n]
смежности пу-
тем приравнивания нулю ненулевых элементов ее главной диагонали;
[]
()
()
1
,31
k
n
kn
′
−
∈

Q
– матрица, полученная из матрицы
[]
()
1
k
n
−
Q
путем
приравнивания нулю ненулевых элементов ее главной диагонали.
Не равные нулю элементы главной диагонали матрицы
[]
()
k
n
Q
свиде-
тельствуют о наличии контуров длины k в графе. При отсутствии таких
элементов контуров длины k в графе нет.
Матрица
[]
()
k
n
Q
определяет число всех путей длины k в графе. Так
как в графе с n вершинами самый длинный элементарный контур не
может иметь длину больше n, то и количество операций вида (2.3.4) не
превышает n.
Следует отметить, что, если в графе с n вершинами отсутствуют
петли и контуры, то максимальная длина элементарного пути в таком

Страницы