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

UptoLike

ВУЗ: 

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

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

Рубрика: 

132
5101
23
1
34
A
∞
⎛⎞
⎜⎟
∞∞
⎜⎟
=
⎜⎟
∞∞∞
⎜⎟
∞∞
⎝⎠
,
используя формулу (4), последовательно находим
(1)
05101
03
10
38 4 0
C
⎛⎞
⎜⎟
∞∞
⎜⎟
=
⎜⎟
∞∞
⎜⎟
⎝⎠
,
(2)
0581
03
10
3840
C
⎛⎞
⎜⎟
∞
∞
⎜⎟
=
⎜⎟
∞
∞
⎜⎟
⎝⎠
(3)
0581
03
10
3540
C
⎛⎞
⎜⎟
∞
∞
⎜⎟
=
⎜⎟
∞
∞
⎜⎟
⎝⎠
,
(4)
0551
03
10
3540
C
⎛⎞
⎜⎟
∞
∞
⎜⎟
=
⎜⎟
∞
∞
⎜⎟
⎝⎠
Например, матрица С
(2)
по матрице С
(1)
вы-
числяется так. Сначала выделим в С
(1)
вторую
строку и второй столбец:
(1)
05101
03
10
38 4 0
C
⎛⎞
⎜⎟
∞∞
⎜⎟
=
⎜⎟
∞∞
⎜⎟
⎝⎠
45
λ
4
(2) = min{0 + ∞; –1 – 7; ∞ + ∞; ∞ + ∞; –3 – 4} = – 8 .
λ
5
(2) = min{0 – 3; –1 – 1; ∞ + 5; ∞ + ∞; –3 + ∞} = – 3.
Полученные значения
λ
i
(2) занесем в третий
столбец таблицы. Величины
λ
i.
(2) равны длине
минимального пути из первой вершины в i–ую,
содержащего не более двух дуг.
Uk = 3.
λ
1
(3) = 0.
Равенство (1) для k = 3 имеет вид:
λ
i
(3) =
51
min
≤≤ j
{
λ
j
(2) + c
ji
}.
λ
2
(3) = min{0 – 1; – 1 + ∞; – 9 + ∞; –8 + ∞; – 3 + ∞} = – 1.
λ
3
(3) = min{0 + ∞; – 1 – 8; – 9 + ∞; –8 – 2; – 3 + ∞} = – 10 .
λ
4
(3) = min{0 + ∞; – 1 – 7; – 9 + ∞; –8 + ∞; – 3 – 4} = – 8.
λ
5
(3) = min{0 – 3; – 1 – 1; – 9 + 5; –8 + ∞; – 3 + ∞} = – 4.
Полученные значения
λ
i.
(3) занесем в чет-
вертый столбец таблицы. Величины
λ
i.
(3) равны
длине минимального пути из первой вершины в i–
ую, содержащего не более трех дуг.
Uk = 4.
λ
1
(4) = 0.
Равенство (1) для k = 4 имеет вид:
λ
i
(4) =
51
min
≤≤ j
{
λ
j
(3) + c
ji
}.
λ
2
(4) = min{0 – 1; – 1 + ∞; – 10 + ∞; – 8 + ∞; – 4 + ∞} = – 1.
λ
3
(4) = min{0 + ∞; – 1 – 8; – 10 + ∞; – 8 – 2; – 4 + ∞} = – 10. 
                 ⎛ ∞ 5 10 1 ⎞                     λ4(2) = min{0 + ∞; –1 – 7; ∞ + ∞; ∞ + ∞; –3 – 4} = – 8 .
                 ⎜          ⎟                     λ5(2) = min{0 – 3; –1 – 1; ∞ + 5; ∞ + ∞; –3 + ∞} = – 3.
                 ⎜ ∞ 2 3 ∞⎟
              A=
                 ⎜∞ 1 ∞ ∞⎟ ,                           Полученные значения λi (2) занесем в третий
                 ⎜          ⎟
                 ⎝ 3 ∞ 4 ∞⎠                       столбец таблицы. Величины λi.(2) равны длине
                                                  минимального пути из первой вершины в i–ую,
используя формулу (4), последовательно находим    содержащего не более двух дуг.
          ⎛ 0 5 10 1 ⎞          ⎛0 5 8 1⎞              k = 3.
          ⎜            ⎟        ⎜          ⎟
                                                         U




          ⎜ ∞ 0 3 ∞⎟            ⎜ ∞ 0 3 ∞⎟             λ1(3) = 0.
   C =
     (1)
                         C =(2)
          ⎜∞ 1 0 ∞⎟ ,           ⎜∞ 1 0 ∞⎟         Равенство (1) для k = 3 имеет вид:
          ⎜            ⎟        ⎜          ⎟                    λi (3) = 1min    {λj (2) + cji}.
          ⎝3 8 4 0⎠             ⎝3 8 4 0⎠                                 ≤ j ≤5


           ⎛0 5 8 1⎞            ⎛0 5 5 1⎞         λ2(3) = min{0 – 1; – 1 + ∞; – 9 + ∞; –8 + ∞; – 3 + ∞} = – 1.
           ⎜           ⎟        ⎜          ⎟      λ3(3) = min{0 + ∞; – 1 – 8; – 9 + ∞; –8 – 2; – 3 + ∞} = – 10 .
             ∞ 0 3  ∞             ∞ 0 3  ∞
    C =⎜
      (3)              ⎟ C =⎜
                           (4)             ⎟
                                                  λ4(3) = min{0 + ∞; – 1 – 7; – 9 + ∞; –8 + ∞; – 3 – 4} = – 8.
           ⎜∞ 1 0 ∞⎟ ,          ⎜∞ 1 0 ∞⎟
           ⎜           ⎟        ⎜          ⎟      λ5(3) = min{0 – 3; – 1 – 1; – 9 + 5; –8 + ∞; – 3 + ∞} = – 4.
           ⎝3 5 4 0⎠            ⎝3 5 4 0⎠
                                                        Полученные значения λi.(3) занесем в чет-
     Например, матрица С(2) по матрице С(1) вы-   вертый столбец таблицы. Величины λi.(3) равны
числяется так. Сначала выделим в С(1) вторую      длине минимального пути из первой вершины в i–
строку и второй столбец:                          ую, содержащего не более трех дуг.
                      ⎛0    5 10    1⎞                  k = 4.
                                                         U




                      ⎜              ⎟                  λ1(4) = 0.
                        ∞   0   3   ∞⎟
             C (1)   =⎜                           Равенство (1) для k = 4 имеет вид:
                      ⎜∞    1   0   ∞⎟                           λi (4) = 1min    {λj (3) + cji}.
                      ⎜              ⎟                                     ≤ j ≤5
                      ⎝3    8   4   0⎠
                                                  λ2(4) = min{0 – 1; – 1 + ∞; – 10 + ∞; – 8 + ∞; – 4 + ∞} = – 1.
                                                  λ3(4) = min{0 + ∞; – 1 – 8; – 10 + ∞; – 8 – 2; – 4 + ∞} = – 10.

                            132                                                    45

Страницы