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

UptoLike

ВУЗ: 

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

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

Рубрика: 

44
λ
2
(1) = min{
λ
1
(0) + c
12
;
λ
2
(0) + c
22
;
λ
3
(0) + c
32
;
λ
4
(0) + c
42
;
λ
5
(0) + c
52
;} =
= min{0 – 1;
∞ + ∞; ∞ + ∞; ∞ + ∞; ∞ + ∞} = – 1.
λ
3
(1) = min{
λ
1
(0) + c
13
;
λ
2
(0) + c
23
;
λ
3
(0) + c
33
;
λ
4
(0) + c
43
;
λ
5
(0) + c
53
;} =
= min{0 +
∞; ∞ – 8; ∞ + ∞; ∞ – 2; ∞ + ∞} = ∞ .
λ
4
(1) = min{
λ
1
(0) + c
14
;
λ
2
(0) + c
24
;
λ
3
(0) + c
34
;
λ
4
(0) + c
44
;
λ
5
(0) + c
54
;} =
= min{0 +
∞; ∞ – 7; ∞ + ∞; ∞ + ∞; ∞ – 4} = ∞ .
λ
5
(1) = min{
λ
1
(0) + c
15
;
λ
2
(0) + c
25
;
λ
3
(0) + c
35
;
λ
4
(0) + c
45
;
λ
5
(0) + c
55
;} =
= min{0 – 3;
∞ – 1; ∞ + 5; ∞ + ∞; ∞ + ∞} = –3.
Полученные значения
λ
i
(1) занесем во вто-
рой столбец таблицы. Убеждаемся, что второй
столбец, начиная со второго элемента, совпадает с
первой строкой матрицы весов, что легко объясня-
ется смыслом величин
λ
i
(1), которые равны длине
минимального пути из первой вершины в i–ую,
содержащего не более одной дуги.
Uk = 2.
λ
1
(2) = 0.
Равенство (1) для k = 2 имеет вид:
λ
i
(2) =
51
min
≤≤ j
{
λ
j
(1) + c
ji
}.
λ
2
(2) = min{0 – 1;–1 + ∞; ∞ + ∞; ∞ + ∞; –3 + ∞} = – 1.
λ
3
(2) = min{0 + ∞; –1 – 8; ∞ + ∞; ∞ – 2; –3 + ∞} = – 9 .
133
Затем, чтобы вычислить первый столбец
матрицы С
(2)
берем второй (выделенный) столбец
матрицы С
(1)
и умножаем (в полукольце R
+
) его
элементы по очереди на первый элемент второй
(выделенной) строки той же матрицы С
(1)
. Каждое
такое произведение складываем в полукольце с
одноименным элементом первого столбца матри-
цы С
(1)
. Поскольку умножение в полукольце R
+
–
это арифметическое сложение, а сложение – взя-
тие наименьшего из двух чисел, мы получим сле-
дующие элементы первого столбца матрицы С
(2)
:
(2) (1) (1) (1)
11 11 12 21
(2) (1) (1) (1)
21 21 22 21
(2) (1) (1) (1)
31 31 32 21
(2) (1) (1) (1)
41 41 42 21
min{ , min{0, } 0,
min{ , min{ , } ,
min{ , min{ , } ,
min{ , min{3, } 3.
cccc
cccc
cccc
cccc
=+=∞=
=
+= ∞∞=∞
=
+= ∞∞=∞
=+=∞=
Как видим, первый столбец матрицы С
(2)
не
изменился по сравнению с первым столбцом мат-
рицы С
(1)
. Это означает, что нельзя уменьшить
стоимость прохождения в первую вершину из дру-
гих вершин графа, идя через вторую вершину
(смотри рис. примера 2).
Точно так же для вычисления второго
столбца матрицы С
(2)
. Умножаем второй столбец
С
(1)
на второй элемент второй строки той же мат-
рицы, для вычисления третьего столбца – на тре-
   λ2(1) = min{λ1(0) + c12; λ2(0) + c22;                         Затем, чтобы вычислить первый столбец
   λ3(0) + c32; λ4(0) + c42; λ5(0) + c52;} =               матрицы С(2) берем второй (выделенный) столбец
   = min{0 – 1; ∞ + ∞; ∞ + ∞; ∞ + ∞; ∞ + ∞} = – 1.         матрицы С(1) и умножаем (в полукольце R+) его
   λ3(1) = min{λ1(0) + c13; λ2(0) + c23;                   элементы по очереди на первый элемент второй
   λ3(0) + c33; λ4(0) + c43; λ5(0) + c53;} =               (выделенной) строки той же матрицы С(1). Каждое
   = min{0 + ∞; ∞ – 8; ∞ + ∞; ∞ – 2; ∞ + ∞} = ∞ .          такое произведение складываем в полукольце с
                                                           одноименным элементом первого столбца матри-
   λ4(1) = min{λ1(0) + c14; λ2(0) + c24;
                                                           цы С(1). Поскольку умножение в полукольце R+ –
   λ3(0) + c34; λ4(0) + c44; λ5(0) + c54;} =
                                                           это арифметическое сложение, а сложение – взя-
   = min{0 + ∞; ∞ – 7; ∞ + ∞; ∞ + ∞; ∞ – 4} = ∞ .          тие наименьшего из двух чисел, мы получим сле-
   λ5(1) = min{λ1(0) + c15; λ2(0) + c25;                   дующие элементы первого столбца матрицы С(2):
   λ3(0) + c35; λ4(0) + c45; λ5(0) + c55;} =
   = min{0 – 3; ∞ – 1; ∞ + 5; ∞ + ∞; ∞ + ∞} = –3.                c11(2) = min{c11(1) , c12(1) + c21
                                                                                                 (1)
                                                                                                     = min{0, ∞} = 0,
      Полученные значения λi (1) занесем во вто-
                                                                  (2)
                                                                 c21  = min{c21
                                                                             (1)    (1)
                                                                                 , c22  + c21
                                                                                           (1)
                                                                                               = min{∞, ∞} = ∞,
рой столбец таблицы. Убеждаемся, что второй                       (2)
                                                                 c31  = min{c31
                                                                             (1)    (1)
                                                                                 , c32  + c21
                                                                                           (1)
                                                                                               = min{∞, ∞} = ∞,
столбец, начиная со второго элемента, совпадает с
первой строкой матрицы весов, что легко объясня-
                                                                  (2)
                                                                 c41  = min{c41
                                                                             (1)    (1)
                                                                                 , c42  + c21
                                                                                           (1)
                                                                                               = min{3, ∞} = 3.
ется смыслом величин λi (1), которые равны длине                  Как видим, первый столбец матрицы С(2) не
минимального пути из первой вершины в i–ую,                изменился по сравнению с первым столбцом мат-
содержащего не более одной дуги.                           рицы С(1). Это означает, что нельзя уменьшить
      k = 2.
      U



                                                           стоимость прохождения в первую вершину из дру-
      λ1(2) = 0.                                           гих вершин графа, идя через вторую вершину
Равенство (1) для k = 2 имеет вид:                         (смотри рис. примера 2).
               λi (2) = 1min
                         ≤ j ≤5
                                {λj (1) + cji}.                  Точно так же для вычисления второго
                                                           столбца матрицы С(2). Умножаем второй столбец
λ2(2) = min{0 – 1;–1 + ∞; ∞ + ∞; ∞ + ∞; –3 + ∞} = – 1.     С(1) на второй элемент второй строки той же мат-
λ3(2) = min{0 + ∞; –1 – 8; ∞ + ∞; ∞ – 2; –3 + ∞} = – 9 .   рицы, для вычисления третьего столбца – на тре-


                              44                                                             133

Страницы