Составители:
101
допускаются. В таком случае наличие петель и контуров свидетель-
ствует об ошибках в описании системы или построении графа ее струк-
туры. В то же время некоторые системы по своей сути должны иметь
петли или контуры, поэтому их отсутствие или невозможность пра-
вильной их интерпретации говорит о допущенных ошибках при моде-
лировании.
Наличие петель и контуров можно выявить с помощью матрицы
смежности. Если матрица R
[n]
смежности вершин графа содержит не-
нулевые элементы, расположенные на главной диагонали, т. е. суще-
ствуют
0
ii
r
≠
при
()
11
in
∈
, то вершины графа, соответствующие этим
элементам, имеют петли. Равенство нулю всех элементов матрицы смеж-
ности, расположенных на главной диагонали, свидетельствует об отсут-
ствии петель в графе.
Наличие контуров в графе определяется следующим образом.
Рассмотрим матрицу R
[n]
смежности вершин графа. Если в ней име-
ются не равные нулю элементы главной диагонали, то приравняем их
нулю. Полученную матрицу обозначим Q
[n]
и возведем в квадрат. При
отсутствии ненулевых элементов главной диагонали в матрице смежно-
сти в качестве матрицы Q
[n]
выбираем ее саму.
Элементы матрицы
[]
()
[]
2
2
n
n
=
QQ
определяются по формуле
()
() ()
2
1
,11,11.
n
ip pj
ij
p
qqqinjn
=
===
∑
(2.3.3)
Каждое слагаемое в выражении (2.3.3) не равно нулю в том и только
том случае, когда оба сомножителя q
ip
и q
pj
не равны нулю. А это возмож-
но только тогда, когда существует путь из вершины i в вершину j, состоя-
щий из двух дуг и проходящий через вершину p. Таким образом, значение
элемента
()
2
ij
q
матрицы
[]
()
2
n
Q
равно числу путей длины 2 (двухзвенных
путей), ведущих из вершины i в вершину j. Следовательно, матрица
[]
()
2
n
Q
определяет число всех путей длины 2 в рассматриваемом графе.
Не равные нулю элементы главной диагонали матрицы
[]
()
2
n
Q
, если они
имеются, свидетельствуют о наличии двухзвенных контуров в графе.
Страницы
- « первая
- ‹ предыдущая
- …
- 99
- 100
- 101
- 102
- 103
- …
- следующая ›
- последняя »
