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

UptoLike

ВУЗ: 

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

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

Рубрика: 

138
подмножества множества упорядоченных
пар (v
i
, v
j
) ´ V×V.
2. Изобразите орграф.
3. Постройте матрицу смежности.
Решение.
1. V = {v
1
, v
2
, v
3
, v
4
, v
5
}.
Множество пар:
{(v
1
, v
1
), (v
1
, v
3
), (v
1
, v
5
), (v
3
, v
1
), (v
3
, v
2
), (v
3
, v
5
),
(v
4
, v
1
), (v
5
, v
1
), (v
5
, v
2
), (v
5
, v
3
), (v
5
, v
4
), (v
5
, v
5
)}.
2. См. рис. 5.15.
Рис. 5.15.
3.
10101
00000
11001
10000
11111
⎛⎞
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎝⎠
39
Uk = 3.
λ
1
(3) = 0.
Равенство (1) для k = 3 имеет вид:
λ
i
(3) =
51
min
≤≤ j
{
λ
j
(2) + c
ji
}.
λ
2
(3) = min{0 + 1; 1 + ∞; 9 + ∞; 7 + ∞; 2 + ∞} = 1.
λ
3
(3) = min{0 + ∞; 1 + 8; 9 + ∞; 7 + 2; 2 + ∞} = 9 .
λ
4
(3) = min{0 + ∞; 1 + 7; 9 + 1; 7 + ∞; 2 + 4} = 6 .
λ
5
(3) = min{0 + 3; 1 + 1; 9 – 5; 7 + ∞; 2 + ∞} = 2.
Полученные значения
λ
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 + ∞; 9 + ∞; 6 + ∞; 2 + ∞} = 1.
λ
3
(4) = min{0 + ∞; 1 + 8; 9 + ∞; 6 + 2; 2 + ∞} = 8.
λ
4
(4) = min{0 + ∞; 1 + 7; 9 + 1; 6 + ∞; 2 + 4} = 6.
λ
5
(4) = min{0 + 3; 1 + 1; 9 – 5; 6 + ∞; 2 + ∞} = 2.
Полученные значения
λ
i
(4) занесем в пятый
столбец таблицы. Величины
λ
i
(4) равны длине
минимального пути из первой вершины в i–ую,
содержащего не более четырех дуг. 
         подмножества множества упорядоченных                          k = 3.
                                                                         U




         пар (vi, vj) ´ V × V.                                         λ1 (3) = 0.
      2. Изобразите орграф.                                       Равенство (1) для k = 3 имеет вид:
      3. Постройте матрицу смежности.                                           λi (3) = 1min
                                                                                          ≤ j ≤5
                                                                                                 {λj (2) + cji}.
                            Решение.
                                                                  λ2(3) = min{0 + 1;     1 + ∞; 9 + ∞; 7 + ∞; 2 + ∞} = 1.
1. V = {v1, v2, v3, v4, v5}.
                                                                  λ3(3) = min{0 + ∞;     1 + 8; 9 + ∞; 7 + 2; 2 + ∞} = 9 .
        Множество пар:
   {(v1, v1), (v1, v3), (v1, v5), (v3, v1), (v3, v2), (v3, v5),   λ4(3) = min{0 + ∞;     1 + 7; 9 + 1; 7 + ∞; 2 + 4} = 6 .
   (v4, v1), (v5, v1), (v5, v2), (v5, v3), (v5, v4), (v5, v5)}.   λ5(3) = min{0 + 3;     1 + 1; 9 – 5; 7 + ∞; 2 + ∞} = 2.
2. См. рис. 5.15.                                                       Полученные значения λi (3) занесем в чет-
                                                                  вертый столбец таблицы. Величины λi (3) равны
                                                                  длине минимального пути из первой вершины в i–
                                                                  ую, содержащего не более трех дуг.
                                                                        k = 4.
                                                                         U




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

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


                                    138                                                            39

Страницы