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

UptoLike

ВУЗ: 

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

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

Рубрика: 

142
1
1 1 – 1 0 0 0 – 1 – 1 – 1
2
– 1 – 1 0 1 – 1 0 0 0 0
3
0 0 1 – 1 0 1 0 0 0
4
0 0 0 0 1 – 1 1 1 1
1 2 3 4 5 6 7 8 9
Задача 5.15.
Найдите цикл, содержащий все вершины до-
декаэдра, причем в точности по одному разу каж-
дую.
Решение.
Этот цикл: 1, 2, 3, 4, 5, 6, 19, 18, 14, 15, 16,
17, 7, 8, 9, 10, 11, 12, 13, 20. Этот цикл называется
гамильтоновым циклом (рис. 5.18).
Рис. 5.18.
35
8B1.8 Алгоритм Форда – Беллмана нахождения
минимального пути
Предполагается, что ориентированный граф
не содержит контуров отрицательной длины.
Алгоритм 1. (Алгоритм Форда – Беллмана)
Основными вычисляемыми величинами это-
го алгоритма являются величины
λ
j
(k), где i = 1, 2,
…, n (n – число вершин графа); k = 1, 2, … , n – 1.
Для фиксированных i и k величина
λ
j.
(k) равна
длине минимального пути, ведущего из заданной
начальной вершины х
1
в вершину х
i
и содержащего
не более k дуг.
Шаг 1. Установка начальных условий. Ввести чис-
ло вершин графа n и матрицу весов C = (c
ij
).
Шаг 2. Положить k = 0. Положить
λ
i
(0) = ∞ для
всех вершин, кроме х
1
; положить
λ
1
(0) = 0.
Шаг 3. В цикле по k, k = 1, ..., n – 1, каждой вер-
шине x
i
на k – ом шаге приписать индекс
λ
i
(k) по
следующему правилу:
λ
i
(k) =
nj≤≤1
min
{
λ
j
(k – 1) + c
ji
} (1)
для всех вершин, кроме х
1
, положить
λ
1
(k) = 0.
В результате работы алгоритма формируется
таблица индексов
λ
i
(k), i = 1, 2, … , n, k = 0, 1, 2, … , n – 1. 
    1 1  1 –1 0  0 0 –1 –1 –1                               1.8 Алгоритм Форда – Беллмана нахождения
                                                           8B




    2 –1 –1 0 1 –1 0  0  0  0                                             минимального пути
    3 0  0  1 –1 0  1 0 0  0                                    Предполагается, что ориентированный граф
    4 0  0  0 0  1 –1 1 1  1                              не содержит контуров отрицательной длины.
       1  2 3  4 5  6 7  8  9
                                                              Алгоритм 1. (Алгоритм Форда – Беллмана)
                      Задача 5.15.                              Основными вычисляемыми величинами это-
       Найдите цикл, содержащий все вершины до-           го алгоритма являются величины λj (k), где i = 1, 2,
декаэдра, причем в точности по одному разу каж-           …, n (n – число вершин графа); k = 1, 2, … , n – 1.
дую.                                                      Для фиксированных i и k величина λj.(k) равна
                        Решение.                          длине минимального пути, ведущего из заданной
       Этот цикл: 1, 2, 3, 4, 5, 6, 19, 18, 14, 15, 16,   начальной вершины х1 в вершину хi и содержащего
17, 7, 8, 9, 10, 11, 12, 13, 20. Этот цикл называется     не более k дуг.
гамильтоновым циклом (рис. 5.18).                         Шаг 1. Установка начальных условий. Ввести чис-
                                                          ло вершин графа n и матрицу весов C = (cij).
                                                          Шаг 2. Положить k = 0. Положить λi (0) = ∞ для
                                                          всех вершин, кроме х1; положить λ1 (0) = 0.
                                                          Шаг 3. В цикле по k, k = 1, ..., n – 1, каждой вер-
                                                          шине xi на k – ом шаге приписать индекс λi (k) по
                                                          следующему правилу:
                                                                          λi (k) = 1min
                                                                                    ≤ j≤ n
                                                                                           {λj (k – 1) + cji} (1)
                                                          для всех вершин, кроме х1, положить λ1 (k) = 0.
                                                                В результате работы алгоритма формируется
                                                          таблица индексов
                                                                λi (k), i = 1, 2, … , n, k = 0, 1, 2, … , n – 1.
                       Рис. 5.18.




                             142                                                           35

Страницы