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

UptoLike

ВУЗ: 

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

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

Рубрика: 

66
Рис. 1.25.
Определение 1.63. Множество K
i
= {и
i
, и
1
i
,..., u
j
i
}
образует простой разрез, который называется фун-
даментальным разрезом графа G относительно
ветви и
i
остова Т.
Определение 1.64. Множество {K
1
, K
2
, …, К.
п–c
}
всех фундаментальных разрезов графа G называ-
ется фундаментальным множеством коциклов
графа G относительно остова Т.
Отметим, что мощность фундаментального
множества коциклов не зависит от выбора остова
T и равна корангу v*(G) = п – с.
Каждому фундаментальному разрезу K
i
ста-
вится в соответствие векторам
1
=( , ..., )
ii im
bb b, оп-
ределенный по правилу
1, если
0, если
j
i
ij
j
i
wK
b
wK
∈
⎧
⎪
=
⎨
∉
⎪
⎩
Фундаментальное множество коциклов зада-
ется матрицей фундаментальных разрезов К,
строки которой являются векторами
*12 ()
, , ..., :
vG
bb b
111
Задача 1. Дан ориентированный граф G, требуется
найти в G гамильтонов цикл (или все циклы), если
существует хотя бы один такой цикл.
Задача 2. Дан полный ориентированный цикл G,
дугам которого приписаны произвольные веса
C.=.[c
ij
], найти такой гамильтонов цикл, который
имеет наименьший общий вес. Следует отметить,
что если ориентированный граф G не полный, то
его можно рассматривать как полный ориентиро-
ванный граф, приписывая отсутствующим дугам
бесконечный вес.
Алгоритмы решения задачи коммивояжера и
ее вариантов имеют большое число практических
приложений в различных областях человеческой
деятельности. Рассмотрим,
например, задачу, в ко-
торой грузовик выезжает с центральной базы для
доставки товаров данному числу потребителей и
возвращается назад на базу. Стоимость перевозки
пропорциональна пройденному грузовиком рас-
стоянию, и при заданной матрице расстояний ме-
жду потребителями маршрут с наименьшими
транспортными затратами получается как решение
соответствующей задачи коммивояжера. Анало-
гичные типы задач
возникают при сборе почтовых
отправлений из почтовых ящиков, составлении
графика движения школьных автобусов по задан-
ным остановкам и т.д. Задача очень легко обобща-
ется и на тот случай, когда доставкой (сбором) за-
                                                                 Задача 1. Дан ориентированный граф G, требуется
                                                                 найти в G гамильтонов цикл (или все циклы), если
                                                                 существует хотя бы один такой цикл.
                          Рис. 1.25.                             Задача 2. Дан полный ориентированный цикл G,
                                                                 дугам которого приписаны произвольные веса
Определение 1.63. Множество Ki = {иi, и i1 ,..., u i j }
                                                                 C.=.[cij], найти такой гамильтонов цикл, который
образует простой разрез, который называется фун-                 имеет наименьший общий вес. Следует отметить,
даментальным разрезом графа G относительно                       что если ориентированный граф G не полный, то
ветви иi остова Т.                                               его можно рассматривать как полный ориентиро-
Определение 1.64. Множество {K1, K2, …, К.п–c}                   ванный граф, приписывая отсутствующим дугам
всех фундаментальных разрезов графа G называ-                    бесконечный вес.
ется фундаментальным множеством коциклов                               Алгоритмы решения задачи коммивояжера и
графа G относительно остова Т.                                   ее вариантов имеют большое число практических
      Отметим, что мощность фундаментального                     приложений в различных областях человеческой
множества коциклов не зависит от выбора остова                   деятельности. Рассмотрим, например, задачу, в ко-
T и равна корангу v*(G) = п – с.                                 торой грузовик выезжает с центральной базы для
      Каждому фундаментальному разрезу Ki ста-                   доставки товаров данному числу потребителей и
вится в соответствие векторам bi =( bi1 , ..., bim ) , оп-       возвращается назад на базу. Стоимость перевозки
ределенный по правилу                                            пропорциональна пройденному грузовиком рас-
                                ⎧⎪1, если w j ∈ K i              стоянию, и при заданной матрице расстояний ме-
                          bij = ⎨                                жду потребителями маршрут с наименьшими
                                 ⎪⎩0, если w j ∉ K i             транспортными затратами получается как решение
         Фундаментальное множество коциклов зада-                соответствующей задачи коммивояжера. Анало-
ется матрицей фундаментальных разрезов К,                        гичные типы задач возникают при сборе почтовых
строки             которой               являются    векторами   отправлений из почтовых ящиков, составлении
b1 , b2 , ..., bv*( G ) :                                        графика движения школьных автобусов по задан-
                                                                 ным остановкам и т.д. Задача очень легко обобща-
                                                                 ется и на тот случай, когда доставкой (сбором) за-

                                 66                                                        111

Страницы