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

UptoLike

ВУЗ: 

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

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

Рубрика: 

110
Следует помнить, что для графа без петель и контуров элементы
a
kk
= 0, k = 1(1)n.
Порядок вычисления элементов a
kl
полной матрицы путей A
[n]
сле-
дующий.
Пусть граф задан матрицей R
[n]
смежности вершин графа.
1-й этап. По матрице R
[n]
путем замены всех элементов, не равных
нулю, на символы u
ij
, i = 1(1)n, j = 1(1)n получают матрицу непосред-
ственных путей U
[n]
.
2-й этап. Применяя алгебру квазиминоров, вычисляют элемент a
kl
матрицы полных путей по формуле (2.3.7) либо (2.3.8) путем последова-
тельного разложения исходного квазиминора на квазиминоры меньше-
го порядка по формуле (2.3.6) до тех пор, пока не получат обыкновенно-
го алгебраического выражения, значение которого вычисляется стан-
дартным способом. При этом индексацию столбцов и строк квазимино-
ров в процессе вычисления не изменяют.
Вычисление квазиминора (2.3.7) или (2.3.8) начинают с разложения
его с помощью выражения (2.3.6) по элементам строки, которая соот-
ветствует исходной вершине искомых элементарных путей. Для эле-
мента a
kl
полной матрицы путей исходной вершиной будет вершина с
индексом k. Следовательно, для k ≠ l имеем
()
1
,
n
l
kl ij lk kq
kq
kl
q
a
uuU
−
=
==
∑
(2.3.9)
где
()
,11
kq
uq n
=
– длина дуги u
kq
;
()
()
,
1, при = ,
при , 1 1 .
l
kq
ij lk kq
ql
ql
uqlqn
−−
=
≠=
U
Если k = l, то
()
1
.
n
l
ll ij lq
ll
q
a
uu
=
==
∑
U
(2.3.10)
Последующие разложения квазиминоров меньших порядков прово-
дятся по элементам строк, соответствующих вершинам, в которые за-
ходят дуги, по которым производилось предыдущее разложение, т. е. по
элементам q-х строк.

Страницы