Page 71 - 4336

k
Визначимо на множині R вектор =( , , , , …, , , ).
, ,
,
Елементи даного вектора задають довжини k найкоротших дуг,
що ведуть із вершини i у вершину j. Якщо будь-які дві дуги, що
ведуть із i у j, мають однакові довжини, то відповідне число

визначає лише один з елементів вектора . Якщо серед
,
розглянутих дуг не можна знайти k дуг, що мають різні довжини,

то невизначені елементи вектора умовно приймаються
,
рівними ∞. Наприклад, якщо вершина i з'єднана з вершиною j
трьома дугами, що мають довжини відповідно 9, 13 і 9, то для k=4

=(9, 13, ∞, ∞). При i=j вважаємо, що існує деяка дуга нульової
,

довжини, що є петлею у вершині i. Позначимо через D матрицю,

елемент якої збігається з вектором .
,
Занумеруємо вершини вихідного графа цілими числами від

k

1 до N. Введемо вектор =( , , , , …, )R , елементи
, ,
, ,
,
якого задають довжини k найкоротших шляхів, що ведуть із
вершини i у вершину j та використовують у якості проміжних

вершини 1, 2, .., m. Позначимо через D матрицю, кожний

елемент якої збігається із .
,
∗
∗
∗
k
Позначимо через =( , , , , , , …, ∗ )R вектор,
,
, ,
елементи якого збігаються з довжинами k найкоротших шляхів,
що ведуть із вершини i у вершину j. Ці довжини будемо називати
оптимальними довжинами відповідних шляхів. Позначимо через

∗
∗
D матрицю, кожний елемент якої збігається із .
,
k
Виберемо із множини R вектори F=(0, ∞, ∞, …, ∞) та
k
V=(∞, ∞, ∞, …, ∞). Тоді, для будь-якого вектора AR
справедливі наступні співвідношення:

A V  A, (4.11)

71