Составители:
Рубрика:
96
Цифры на ребрах и дугах соответствуют длинам ветвей. Тогда мат-
рица расстояний будет следующей:
1
ABCDE F
A 0 30 20
B 0 15 15
C 15 0 20 25
.
D2015200 25
E2510040
F15 25400
L
∞∞∞
∞∞∞
∞∞
=
∞
∞∞
∞∞
(5.2)
Элементы главной диагонали равны 0, так как принимается, что рас-
стояние внутри узла равно нулю. Если между парой узлов отсутствует
ребро, то соответствующий элемент матрицы равен бесконечности (∞).
Если между узлами i и j имеется дуга
1
,ij
β
, то элемент
1
,ji
l
также прини-
мается равным бесконечности, например,
1
,AF
l =∞
, тогда же
1
,
15
FA
l =
.
При анализе сетей передачи данных длину ветви удобно трактовать
как задержку, которую вносит ветвь при передаче информации.
Матрица расстояний непосредственных связей неориентированной сети
всегда симметрична относительно своей главной диагонали. Для ориен-
тированной сети (как в примере) она может быть нессиметричной.
Возведем матрицу L
1
в квадрат L
2
= L
1
× L
1
. Тогда
2111111 11
,,,,11,,22, ,,
1
.
N
ij ik kj i j i j iN Nj
k
lllllll ll
=
=×=×+×++×
∑
(5.3)
Можно интерпретировать умножение как последовательное соеди-
нение ветвей, а сложение – как параллельное соединение ветвей.
Произведение
11
,,ik k j
ll×
соответствует двухтранзитному пути (т. е.
пути, проходящему через две транзитных ветви сети) от узла i
k
к узлу j
через узел k (рис. 5.3, а), а сумма, например, трех произведений
11 1 1 1 1
,, , , , ,ii ij ij jj ik kj
ll l l l l×+× +×
– трем двухтранзитным путям (рис. 5.3, б).
Страницы
- « первая
- ‹ предыдущая
- …
- 94
- 95
- 96
- 97
- 98
- …
- следующая ›
- последняя »
