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

UptoLike

ВУЗ: 

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

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

Рубрика: 

42
λ
r
(0) + c
r2
=
λ
2
(1), x
r
∈ G
–1
(x
2
), (6)
где G
–1
(x
2
) – прообраз вершины x
2
.
G
–1
(x
2
) = {x
1
}.
Подставим в (6) r = 1, чтобы определить,
выполняется ли это равенство:
λ
1
(0) + c
12
= 0 + 1 =
λ
2
(1) = 1.
Таким образом, вершиной, предшествующей
вершине x
2
, является вершина x
1
.
Итак, найден минимальный путь – x
1
, x
2
, x
5
,
x
4
, x
3
, его длина равна 8.
9B1.9. Алгоритм нахождения максимального пути
При решении некоторых практических задач
возникает необходимость поиска максимального
пути (пути с наибольшей суммой длин дуг). Такая
задача сводится к задаче нахождения минимально-
го пути заменой знаков при длинах дуг (в матрице
весов C) на противоположные. При этом необхо-
димым является требование отсутствия в ориенти-
рованном графе контуров положительной длины.
Пример 1.21.
С помощью модифицированного алгоритма
найдем максимальный путь из вершины х
1
в вер-
шину х
3
в графе, изображенном на рис. 1.17.
135
Рис. 5.11.
Анализируя граф, получаем следующий порядок
движения: красная, черная, синяя, зеленая, белая.
Задача 5.10.
Пусть даны графы G
1
(Х, Е) и G
2
(У, Е), изо-
браженные на рис. 5.12. Установите, изоморфны
ли данные графы.
Решение.
Для доказательства того, что граф С
1
изо-
морфен графу С
2
необходимо и достаточно вы-
полнение условия: найти такую подстановку, ко-
торая граф С
1
переводит в граф С
2
.
Рис. 5.12.
Запишем элементы х ´ Х и у ´ У с соответ-
ствующими им парами чисел, где первое число –
число исходов из вершины, а второе – число захо-
       λr (0) + cr2 = λ2 (1),    xr ∈ G –1(x2), (6)                        Рис. 5.11.

где G –1(x2) – прообраз вершины x2.                   Анализируя граф, получаем следующий порядок
                    G –1(x2) = {x1}.                  движения: красная, черная, синяя, зеленая, белая.

     Подставим в (6) r = 1, чтобы определить,                               Задача 5.10.
выполняется ли это равенство:                               Пусть даны графы G1 (Х, Е) и G2 (У, Е), изо-
         λ1 (0) + c12 = 0 + 1 = λ2 (1) = 1.           браженные на рис. 5.12. Установите, изоморфны
        Таким образом, вершиной, предшествующей       ли данные графы.
вершине x2, является вершина x1.                                          Решение.
        Итак, найден минимальный путь – x1, x2, x5,         Для доказательства того, что граф С1 изо-
x4, x3, его длина равна 8.                            морфен графу С2 необходимо и достаточно вы-
                                                      полнение условия: найти такую подстановку, ко-
1.9. Алгоритм нахождения максимального пути
9B                                                    торая граф С1 переводит в граф С2.
      При решении некоторых практических задач
возникает необходимость поиска максимального
пути (пути с наибольшей суммой длин дуг). Такая
задача сводится к задаче нахождения минимально-
го пути заменой знаков при длинах дуг (в матрице
весов C) на противоположные. При этом необхо-
димым является требование отсутствия в ориенти-
рованном графе контуров положительной длины.
                      Пример 1.21.
                                                                           Рис. 5.12.
     С помощью модифицированного алгоритма
найдем максимальный путь из вершины х1 в вер-              Запишем элементы х ´ Х и у ´ У с соответ-
шину х3 в графе, изображенном на рис. 1.17.           ствующими им парами чисел, где первое число –
                                                      число исходов из вершины, а второе – число захо-


                                42                                               135

Страницы