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

UptoLike

ВУЗ: 

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

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

Рубрика: 

134
тий элемент второй строки и т.д. Изменение эле-
мента
(2)
13
8c =
по сравнению с
(2)
13
10c
=
, связанное
с тем, что стоимость прохождения из v
1
в v
3
по пу-
ти ранга 2 оказалась меньше, чем стоимость про-
хождения по пути ранга 1. Минимальная же
стоимость прохождения
(4)
13
5c =
получена по пути
ранга 4.
Задача 5.9.
Из пункта А в пункт В выехали пять машин одной
марки разного цвета: белая, черная, красная, си-
няя, зеленая. Черная едет впереди синей, зеленая –
впереди белой, но позади синей, красная впереди
черной. Какая машина едет первой и какая по-
следней?
Решение.
Решаем задачу, построив ориентированный
граф для отношения f: «x едет сзади у». На плоско-
сти отметим пять точек, соответствующих каждой
машине, и обозначим их первой буквой цвета ма-
шины (рис. 5.11).
Б
Ч
К
З
С
43
Рис. 1.17.
Шаг 1. Введем число вершин графа n = 5. Матрица
весов этого графа после замены знаков при длинах
дуг на противоположные имеет вид:
C =
1 3
8 7 1
5
2
4
∞
−∞∞−
⎛⎞
⎜⎟
∞
∞− − −
⎜⎟
⎜⎟
∞∞∞∞
⎜⎟
∞
∞− ∞ ∞
⎜⎟
⎜⎟
∞
∞∞− ∞
⎝⎠
.
Шаг 2. Положим Uk = 0U,
λ
1
(0) = 0,
λ
2
(0) =
λ
3
(0) =
λ
4
(0) =
λ
5
(0) = ∞.
Эти значения занесем в первый столбец табли-
цы.1.3.
Шаг 3. Uk = 1U.
λ
1
(1) = 0.
Равенство (1) для k = 1 имеет вид:
λ
i
(1) =
51
min
≤≤ j
{
λ
j
(0) + c
ji
}. 
тий элемент второй строки и т.д. Изменение эле-
мента c13 = 8 по сравнению с c13 = 10 , связанное
         (2)                    (2)


с тем, что стоимость прохождения из v1 в v3 по пу-
ти ранга 2 оказалась меньше, чем стоимость про-
хождения по пути ранга 1. Минимальная же
стоимость прохождения c13 = 5 получена по пути
                         (4)


ранга 4.                                                                       Рис. 1.17.
                      Задача 5.9.
                                                     Шаг 1. Введем число вершин графа n = 5. Матрица
Из пункта А в пункт В выехали пять машин одной       весов этого графа после замены знаков при длинах
марки разного цвета: белая, черная, красная, си-     дуг на противоположные имеет вид:
няя, зеленая. Черная едет впереди синей, зеленая –
                                                                            ⎛ ∞ −1 ∞ ∞       − 3⎞
впереди белой, но позади синей, красная впереди                             ⎜∞ ∞ −8 − 7
черной. Какая машина едет первой и какая по-                                ⎜                − 1 ⎟⎟
следней?                                                                C = ⎜∞ ∞ ∞ ∞           5⎟ .
                     Решение.                                               ⎜                     ⎟
                                                                            ⎜∞ ∞ − 2 ∞        ∞⎟
      Решаем задачу, построив ориентированный                               ⎜∞ ∞ ∞ − 4        ∞ ⎟⎠
граф для отношения f: «x едет сзади у». На плоско-                          ⎝
сти отметим пять точек, соответствующих каждой       Шаг 2. Положим k = 0, U    U




машине, и обозначим их первой буквой цвета ма-           λ1 (0) = 0, λ2 (0) = λ3 (0) = λ4 (0) = λ5 (0) = ∞ .
шины (рис. 5.11).                                    Эти значения занесем в первый столбец табли-
          Б            Ч               К             цы.1.3.
                                                     Шаг 3. k = 1.
                                                              U     U




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



                           134                                                         43

Страницы