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

UptoLike

ВУЗ: 

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

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

Рубрика: 

38
λ
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; ∞ + 1; ∞ + ∞; ∞ + 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.
λ
4
(2) = min{0 + ∞; 1 + 7; ∞ + 1; ∞ + ∞; 3 + 4} = 7.
λ
5
(2) = min{0 + 3; 1 + 1; ∞ – 5; ∞ + ∞; 3 + ∞} = 2.
Полученные значения
λ
i
(2) занесем в третий
столбец таблицы. Величины
λ
i
(2) равны длине ми-
нимального пути из первой вершины в i–ую, со-
держащего не более двух дуг.
139
Задача 5.13.
Дано множество V = {1, 2, 3, 4, 5}. На этом
множестве задано отношение f: х > у. Постройте
орграф данного отношения.
Решение.
Для того чтобы построить орграф данного
отношения f: х > у, изобразим все элементы мно-
жества V точками на плоскости и проведем стрел-
ку от каждого большего числа к меньшему
(рис./5.16).
Рис. 5.16.
Задача 5.14. 
    λ4(1) = min{λ1(0) + c14; λ2(0) + c24; λ3(0) +
    + c34; λ4(0) + c44; λ5(0) + c54;} =                                 Задача 5.13.
    = min{0 + ∞ ; ∞ + 7; ∞ + 1; ∞ + ∞; ∞ + 4} = ∞ .        Дано множество V = {1, 2, 3, 4, 5}. На этом
    λ5(1) = min{λ1(0) + c15; λ2(0) + c25; λ3(0) +     множестве задано отношение f: х > у. Постройте
    + c35; λ4(0) + c45; λ5(0) + c55;} =               орграф данного отношения.
    = min{0 + 3; ∞ + 1; ∞ – 5; ∞ + ∞; ∞ + ∞} = 3.
                                                                          Решение.
      Полученные значения λi (1) занесем во вто-
                                                            Для того чтобы построить орграф данного
рой столбец таблицы. Убеждаемся, что второй
                                                      отношения f: х > у, изобразим все элементы мно-
столбец, начиная со второго элемента, совпадает с
                                                      жества V точками на плоскости и проведем стрел-
первой строкой матрицы весов, что легко объясня-
                                                      ку от каждого большего числа к меньшему
ется смыслом величин λi (1), которые равны длине
                                                      (рис./5.16).
минимального пути из первой вершины в i–ую,
содержащего не более одной дуги.
      k = 2.
      U




      λ1 (2) = 0.
Равенство (1) для k = 2 имеет вид:
               λi (2) = 1min
                         ≤ j ≤5
                                {λj (1) + cji}.

λ2(2) = min{0 + 1; 1 + ∞; ∞ + ∞; ∞ + ∞; 3 + ∞} = 1.
λ3(2) = min{0 + ∞; 1 + 8; ∞ + ∞; ∞ + 2; 3 + ∞} = 9.
λ4(2) = min{0 + ∞; 1 + 7; ∞ + 1; ∞ + ∞; 3 + 4} = 7.
λ5(2) = min{0 + 3; 1 + 1; ∞ – 5; ∞ + ∞; 3 + ∞} = 2.
     Полученные значения λi(2) занесем в третий
столбец таблицы. Величины λi(2) равны длине ми-                           Рис. 5.16.
нимального пути из первой вершины в i–ую, со-
держащего не более двух дуг.                                            Задача 5.14.


                             38                                                 139

Страницы