Основные понятия теории графов. Гладких О.Б - 46 стр.

UptoLike

ВУЗ: 

ЕГУ им. Бунина | Елец

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

Рубрика: 

46
λ
4
(4) = min{0 + ∞; – 1 – 7; – 10 + ∞; – 8 + ∞; – 4 – 4} = – 8.
λ
5
(4) = min{0 – 3; – 1 – 1; – 10 + 5; – 8 + ∞; – 4 + ∞} = – 5.
Полученные значения
λ
i
(4) занесем в пятый
столбец таблицы. Величины
λ
i
(4) равны длине
минимального пути из первой вершины в i–ую,
содержащего не более четырех дуг.
Таблица 1.3.
i (номер
вершины)
λ
i
(0)
λ
i
(1)
λ
i
(2)
λ
i
(3)
λ
i
(4)
1 0 0 0 0 0
2
∞
– 1 – 1 – 1 – 1
3
∞ ∞
– 9 – 10 – 10
4
∞ ∞
– 8 – 8 – 8
5
∞
– 3 – 3 – 4 – 5
Заменив в таблице 1.3 отрицательные числа
положительными, получим таблицу индексов мак-
симальных путей (таблица 1.4). При этом
λ
i.
(k) оп-
ределяет длину максимального пути из первой
вершины в i–ую, содержащего не более k дуг.
Таблица 1.4.
i (номер
вершины)
λ
i
(0)
λ
i
(1)
λ
i
(2)
λ
i
(3)
λ
i
(4)
1 0 0 0 0 0
2
∞
1 1 1 1
3
∞ ∞
9 10 10
4
∞ ∞
8 8 8
5
∞
3 3 4 5
131
(0)
,
1,
ij
ij
ij
ai j
c
ai j
≠
⎧
=
⎨
+
=
⎩
(3)
Тогда матрицу стоимостей С.=.А
*
можно
найти, вычисляя последовательно матрицы C
(k)
,
k.= 1, n по формулам (2), (3).
Вычисления по формулам (2) и (3) образуют
алгоритм Флойда – Уоршелла – Клини определе-
ния стоимости прохождения между любыми пара-
ми вершин.
Для полуколец В и R
+
в силу того, что в них
итерация любого элемента х равна единице полу-
кольца, получим упрощенный вариант формулы
(2):
() ( 1) ( 1) ( 1)kk kk
ij ij ik kj
cc cc
−
−−
=+ . (4)
Вычисления по формуле (4) начинают с мат-
рицы определяемой соотношением (3). Все даль-
нейшие вычисления удобно также проводить в
матричном виде. Для нахождения матрицы C
(k)
удобно определить сначала матрицу D
(k)
, элементы
которой вычисляются по формуле
() ( 1) ( 1)kkk
ij ik kj
dcc
−
−
= . (5)
Чтобы найти j – й столбец матрицы D
(k)
, дос-
таточно k – й столбец матрицы C
(k-1)
умножить на j
– й элемент k – й строки этой же матрицы.
Для нашего графа C
(0)
= A, где матрица А
имеет вид: 
λ4(4) = min{0 + ∞; – 1 – 7; – 10 + ∞; – 8 + ∞; – 4 – 4} = – 8.                                    ⎧ aij , i ≠ j
                                                                                         cij(0) = ⎨                    (3)
λ5(4) = min{0 – 3; – 1 – 1; – 10 + 5; – 8 + ∞; – 4 + ∞} = – 5.                                    ⎩1 + aij , i = j
     Полученные значения λi (4) занесем в пятый                         Тогда матрицу стоимостей С.=.А* можно
столбец таблицы. Величины λi (4) равны длине                     найти, вычисляя последовательно матрицы C(k),
минимального пути из первой вершины в i–ую,                      k.= 1, n по формулам (2), (3).
содержащего не более четырех дуг.                                       Вычисления по формулам (2) и (3) образуют
                                    Таблица 1.3.                 алгоритм Флойда – Уоршелла – Клини определе-
  i (номер                                                       ния стоимости прохождения между любыми пара-
               λi(0)   λi(1)      λi(2)      λi(3)      λi(4)    ми вершин.
 вершины)
      1         0        0         0           0         0              Для полуколец В и R+ в силу того, что в них
      2         ∞       –1         –1         –1        –1       итерация любого элемента х равна единице полу-
      3         ∞       ∞          –9         – 10      – 10     кольца, получим упрощенный вариант формулы
      4         ∞       ∞          –8          –8        –8      (2):
      5         ∞       –3         –3         –4        –5                       cij( k ) = cij( k −1) + cik( k −1) ckj( k −1) . (4)
     Заменив в таблице 1.3 отрицательные числа                          Вычисления по формуле (4) начинают с мат-
положительными, получим таблицу индексов мак-                    рицы определяемой соотношением (3). Все даль-
симальных путей (таблица 1.4). При этом λi.(k) оп-               нейшие вычисления удобно также проводить в
ределяет длину максимального пути из первой                      матричном виде. Для нахождения матрицы C(k)
вершины в i–ую, содержащего не более k дуг.                      удобно определить сначала матрицу D(k), элементы
                                                                 которой вычисляются по формуле
                                                Таблица 1.4.
  i (номер                                                                               dij( k ) = cik( k −1) ckj( k −1) .      (5)
               λi(0)   λi(1)      λi(2)      λi(3)      λi(4)
 вершины)
                                                                       Чтобы найти j – й столбец матрицы D(k), дос-
      1         0        0          0         0          0
                                                                 таточно k – й столбец матрицы C(k-1) умножить на j
      2         ∞        1          1         1          1
      3         ∞        ∞          9         10         10      – й элемент k – й строки этой же матрицы.
      4         ∞        ∞          8          8          8            Для нашего графа C(0) = A, где матрица А
      5         ∞        3          3         4          5       имеет вид:


                                  46                                                                   131

Страницы