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

UptoLike

ВУЗ: 

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

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

Рубрика: 

109
квазиминоры. Процесс вычисления во многом сходен с процессом вы-
числения обычных определителей и после приобретения практических
навыков оказывается достаточно простым. Кроме того, данный процесс
легко поддается алгоритмизации, а следовательно, и выполнению на ЭВМ.
Сущность рассматриваемого способа определения всех элементар-
ных путей в графе состоит в том, что на основе матрицы смежности
вершин графа строится матрица непосредственных путей, а по ней с
помощью алгебры квазиминоров находится полная матрица путей.
Определение 2.3.5. Матрицей непосредственных путей графа
G с n вершинами будем называть квадратную матрицу U
[n]
, строки и
столбцы которой соответствуют вершинам графа, а элементы опреде-
ляются по формуле
() ()
– если данная дуга существует;
0 – в противном сл
у
чае, =1 1 , 1 1 .
ij
ij
u
u
inj n
=
=
Матрица непосредственных путей легко получается из матрицы
смежности вершин, если в ней все элементы, не равные нулю, заменить
соответствующими символами дуг.
Определение 2.3.6. Полной матрицей путей графа G с n вер-
шинами будем называть квадратную матрицу A
[n]
, строки и столбцы
которой соответствуют вершинам графа, а значение элементов a
ij
,
i = 1(1)n, j = 1(1)n равно числу всех элементарных путей из вершины
x
i
графа в вершину x
j
.
Доказано, что число всех элементарных путей, ведущих из k-й верши-
ны в l-ю, т. е. значение элемента a
kl
полной матрицы путей A
[n]
, равно зна-
чению квазиминора элемента u
kl
матрицы непосредственных путей U
[n]
:
, если .
kl ij lk
kl
au kl
−
=≠
(2.3.7)
Элементы a
kk
, k = 1(1)n полной матрицы путей можно вычислить с
помощью выражения
a
kk
= |u
ij
|
kk
, k = 1(1)n. (2.3.8)
При этом в квазиминор вписывается вся матрица без вычеркивания
столбцов и строк.

Страницы