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

UptoLike

ВУЗ: 

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

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

Рубрика: 

40
Таблица 1.2.
i (номер
вершины)
λ
i
(0)
λ
i
(1)
λ
i
(2)
λ
i
(3)
λ
i
(4)
1 0 0 0 0 0
2
∞
1 1 1 1
3
∞ ∞
9 9 8
4
∞ ∞
7 6 6
5
∞
3 2 2 2
Шаг 5. Восстановление минимального пути. Для
последней вершины x
3
предшествующая ей вер-
шина x
r
определяется из соотношения (2) получен-
ного при s = 3:
λ
r
(3) + c
r3
=
λ
3
(4), x
r
∈ G
–1
(x
3
), (3)
где G
–1
(x
3
) – прообраз вершины x
3
.
G
–1
(x
3
) = {x
2
, x
4
}.
Подставим в (3) последовательно r = 2 и r = 4, что-
бы определить, для какого r это равенство выпол-
няется:
λ
2
(3) + c
23
= 1 + 8 ≠
λ
3
(4) = 8,
λ
4
(3) + c
43
= 6 + 2 =
λ
3
(4) = 8.
Таким образом, вершиной, предшествующей
вершине x
3
, является вершина x
4
.
Для вершины x
4
предшествующая ей верши-
на x
r
определяется из соотношения (2) полученно-
го при s = 4:
λ
r
(2) + c
r4
=
λ
4
(3), x
r
∈ G
–1
(x
4
), (4)
137
Рис. 5.14.
Решение.
Матрица смежности
A
0 1 1 0 0
B
1 0 1 0 1
C
1 1 0 1 1
D
0 1 1 0 0
E
0 1 1 1 0
A B C D E
Матрица инцидентности
A
1 1 0 0 0 0 0
B
1 0 0 0 1 1 0
C
0 1 1 0 0 1 1
D
0 0 1 1 0 0 0
E
0 0 0 1 1 0 1
1 2
3 4
5 6 7
Задача 5.12.
Задан граф G (V, E), где V = {v
1
, v
2
, v
3
, v
4
, v
5
};
Е
1
v
= {v
1
, v
3
, v
5
}; Е
2
v
= ¬; Е
3
v
= {v
1
, v
2
, v
5
}; Е
4
v
= {v
1
};
Е
5
v
= {v
1
, v
2
, v
3
, v
4
, v
5
}.
1. Задайте граф с помощью бинарного отно-
шения, т. е. совокупности множества V и 
                                      Таблица 1.2.
                                                                                  Рис. 5.14.
 i (номер
            λi(0)   λi(1)   λi(2)   λi(3)    λi(4)
вершины)                                                                         Решение.
     1       0       0       0        0       0
     2       ∞       1       1        1       1              Матрица смежности
     3       ∞       ∞       9        9       8
                                                                      A     0      1     1     0   0
     4       ∞       ∞       7        6       6
                                                                      B     1      0     1     0   1
     5       ∞       3       2        2       2
                                                                      C     1      1     0     1   1
Шаг 5. Восстановление минимального пути. Для                          D     0      1     1     0   0
последней вершины x3 предшествующая ей вер-                           E     0      1     1     1   0
                                                                            A      B     C     D   E
шина xr определяется из соотношения (2) получен-
ного при s = 3:                                              Матрица инцидентности
       λr (3) + cr3 = λ3 (4), xr ∈ G –1 (x3), (3)
где G –1(x3) – прообраз вершины x3.                              A     1    1      0     0     0   0     0
                    G –1(x3) = {x2, x4}.                         B     1    0      0     0     1   1     0
                                                                 C     0    1      1     0     0   1     1
Подставим в (3) последовательно r = 2 и r = 4, что-              D     0    0      1     1     0   0     0
бы определить, для какого r это равенство выпол-                 E     0    0      0     1     1   0     1
няется:                                                                1    2      3     4     5   6     7
         λ2 (3) + c23 = 1 + 8 ≠ λ3 (4) = 8,
         λ4 (3) + c43 = 6 + 2 = λ3 (4) = 8.                                     Задача 5.12.
      Таким образом, вершиной, предшествующей                 Задан граф G (V, E), где V = {v1, v2, v3, v4, v5};
вершине x3, является вершина x4.                      Е v1 = {v1, v3, v5}; Е v2 = ¬; Е v3 = {v1, v2, v5}; Е v4 = {v1};
      Для вершины x4 предшествующая ей верши-         Е v5 = {v1, v2, v3, v4, v5}.
на xr определяется из соотношения (2) полученно-             1. Задайте граф с помощью бинарного отно-
го при s = 4:                                                   шения, т. е. совокупности множества V и
       λr (2) + cr4 = λ4 (3), xr ∈ G –1(x4), (4)


                            40                                                          137

Страницы