Page 72 - 4336

A V  V , (4.12)

A F  A (4.13)

Нехай матриця L утворена з матриці D шляхом заміни всіх

елементів кожного вектора (при i≤j) величиною ∞. Нехай
,

матриця U утворена з матриці D шляхом заміни всіх елементів

кожного вектора (при i≥j) величиною ∞. Матриці L і U
,
називаються відповідно верхньою трикутною та нижньою

трикутною підматрицями матриці D (рис. 4.9).

d 0 1 , 1 d 0 2 , 1 d 0 3 , 1 V V V V d 0 2 , 1 d 0 3 , 1

0
D  d 0 1 , 2 d 0 2 , 2 d 0 3 , 2 , L  d 0 1 , 2 V V , U  V V d 0 3 , 2 .

d 0 1 , 3 d 0 2 , 3 d 0 3 , 3 d 0 1 , 3 d 0 2 , 3 V V V V

Рисунок 4.9.

Приклад 4.6. Розглянемо випадок, у якому k=2 і матриця D

є наступною:

) 1 , 0 ( , 6 ( 10 ) ) 9 , 2 (

D 0  ) 8 , 1 ( , 0 (  ) , 3 (  ) .

( ,  ) ) 4 , 2 ( , 0 (  )

Тоді матриці L і U матимуть наступний вигляд:

( ,  ) ( ,  ) ( ,  ) ( ,  ) , 6 ( 10 ) ) 9 , 2 (

L  ) 8 , 1 ( ( ,  ) ( ,  ) , U  ( ,  ) ( ,  ) , 3 (  ) .

( ,  ) ) 4 , 2 ( ( ,  ) ( ,  ) ( ,  ) ( ,  )

Якщо необхідно визначити довжини k найкоротших шляхів,

що ведуть із деякої фіксованої вершини (наприклад, вершини 1) у

кожну вершину вхідного графа, то слід визначити тільки перший

∗
∗
∗
∗
рядок ( , , …, , ) матриці D . Зазначимо, що цей рядок
,
,
72