Вычислительные сети. Крылов Ю.Д. - 98 стр.

UptoLike

ВУЗ: 

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

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

Рубрика: 

98
()()()( )
–11 –11 –11 –11
,,,,11,,2,2,,
1,...,
min min ; ;...
rr rr r
ij ik rj i j i j iN Nj
kN
lllllllll
=
=+=++ +
будет равен длине кратчайшего пути от УК
i
к УК
j
среди всех одно-
двух- и т. д. r-транзитных путей.
При наличии на сети N узлов коммутации число транзитных ветвей в
пути без петель не может быть больше (N–1). Следовательно, может
потребоваться вычисление матрицы L
r
, у которой r ≤ N–1.
Для конкретной сети может оказаться, что при r < N–1
1
LL.
rr
−
=
(5.4)
Так как при равенстве (5.4) всегда выполняется равенство L
r+1
= L
r
,
вычисление матрицы более высокой степени прекращается, если в про-
цессе вычисления матриц встретится равенство (5.4).
Матрица L
r–1
при выполнении условия (5.4) называется дистанцион-
ной матрицей и обозначается
–1
,
D=L L d .
rr
ij
==
(5.5)
Таким образом, элементы дистанционной матрицы равны длинам
кратчайших путей между соответствующими узлами сети связи. Мат-
рица D часто называется матрицей расстояний (длин, задержек).
Для рассматриваемого примера вычислим l
2
A,B
2 11111111
, ,,,,,,,,
min ( );( );( );( );
AB AA AB AB BB AC CB AD DB
l llllllll=+ + + +
()
1111
,,
( );( ) min (0 30);(30 0);( 15);(20 15); ;
AE BE AF FB
llll
++=++∞++∞+∞
( ) min 30;30; ;35; ; 30.∞+∞ = ∞ ∞ ∞ =
Аналогично вычислим остальные элементы матрицы L
2
, получим
2
ABCDE F
A 0 30 40 20 45
B 35 0 15 15 40 40
C 40 15 0 20 25 45
.
D 20 15 20 0 45 25
E30252510035
F15404525400
L
∞
=

Страницы