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

UptoLike

ВУЗ: 

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

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

Рубрика: 

34
Алгоритм Дейкстры
Пусть граф G = (M, R) – взвешенный граф,
W.= (w
ij
) – матрица весов графа G., где w
ij
> 0; a
i
–
выделенный источник. Зададим строку D
(1)
= (
(1)
1
d ,
(1)
2
d , ...,
(1)
n
d ), полагая, что
(1)
i
d = 0,
(1)
j
d = w
ij
, i ≠ j.
Обозначим через
Т
(1)
множество вершин М \ {a
i
}.
Предположим, что на шаге
s уже определены
строка
D
(s)
= (
()
1
s
d , ...,
()
s
n
d ), и множество вершин
Т
s
. Выбкркм теперь вершину a
j
´ Т
s
так, что
() ()
min { }
ss
j
ks
k
ddaT=∈.
Положим
Т
s+1
= Т
s
\ {a
j
}, D
(s+1)
= (
(1)
1
s
d
+
, ...,
(1)
s
n
d
+
),
где
(1) () ()
min { , + }
sss
kkjjk
dddw
+
= , если a
k
´ Т
s+1
, и
(1) ()
s
s
kk
dd
+
= , если a
k
µ Т
s+1
.
На шаге s = n – 1, образуется строка D
(n – 1)
w-расстояний между вершиной a
i
и остальными
вершинами графа:
(1)
(, )
n
kwij
daa
ρ
−
= .
В общем случае задача решается с помощью
алгоритмов Флойда, Форда, Беллмана и др.
Алгоритмы нахождения минимального пути
могут быть использованы для поиска кратчайших
путей в ориентированном графе без контуров. Для
этого нужно каждой дуге приписать вес, равный
единице.
143
Задача 5.16.
В составе экспедиции должно быть 6 спе-
циалистов: биолог, врач, синоптик, гидролог, ме-
ханик и радист. Имеется 8 кандидатов, из которых
и нужно выбрать участников экспедиции; услов-
ные имена претендентов: A, B, C, D, E, F, G и H.
Обязанности биолога могут исполнять E и G, вра-
ча – A и D, синоптика – F и G,
гидролога – B и F,
радиста – С и D, механика – C и H. Предусмотре-
но, что в экспедиции каждый из них будет выпол-
нять только одну обязанность. Кого и в какой
должности следует включить в состав экспеди-
цию, если F
не может ехать без B, D – без H и C, C
не может ехать вместе с G, A – вместе с B?
Решение.
Заметим, что задать возможный вариант ре-
шения, то есть описать точный состав экспедиции,
можно с помощью четного графа, в котором вер-
шины разделены на две группы, а ребра могут со-
единять лишь вершины разных групп.
Применительно к задаче об экспедиции одна
группа вершин есть группа из 8 кандидатов, а вто-
рая
– из 6 должностей.
Задача 5.17.
Планета имеет форму выпуклого многогран-
ника, причем в его вершинах расположены города,
а каждое ребро является дорогой. Две дороги за-
               Алгоритм Дейкстры                                                                  Задача 5.16.
     Пусть граф G = (M, R) – взвешенный граф,                                        В составе экспедиции должно быть 6 спе-
W.= (wij) – матрица весов графа G., где wij > 0; ai –                          циалистов: биолог, врач, синоптик, гидролог, ме-
выделенный источник. Зададим строку D(1) = ( d1(1) ,                           ханик и радист. Имеется 8 кандидатов, из которых
                                                                               и нужно выбрать участников экспедиции; услов-
d 2(1) , ..., d n(1) ), полагая, что di(1) = 0, d (1)        j = wij, i ≠ j.
                                                                               ные имена претендентов: A, B, C, D, E, F, G и H.
Обозначим через Т(1) множество вершин М \ {ai}.                                Обязанности биолога могут исполнять E и G, вра-
Предположим, что на шаге s уже определены                                      ча – A и D, синоптика – F и G, гидролога – B и F,
строка D(s) = ( d1( s ) , ..., d n( s ) ), и множество вершин                  радиста – С и D, механика – C и H. Предусмотре-
Тs. Выбкркм теперь вершину aj ´ Тs так, что                                    но, что в экспедиции каждый из них будет выпол-
                       d (j s ) = min {d k( s ) a k ∈ Ts } .                   нять только одну обязанность. Кого и в какой
                                                                               должности следует включить в состав экспеди-
Положим
                                                                               цию, если F не может ехать без B, D – без H и C, C
          Тs+1 = Тs \ {aj}, D(s+1) = ( d1( s +1) , ..., d n( s +1) ),          не может ехать вместе с G, A – вместе с B?
где d k( s +1) = min {d k( s ) , d (j s ) + w jk } , если ak ´ Тs+1, и
                                                                                                   Решение.
    d k( s +1) = d k( s ) , если ak µ Тs+1.                                          Заметим, что задать возможный вариант ре-
      На шаге s = n – 1, образуется строка D (n – 1)                           шения, то есть описать точный состав экспедиции,
w-расстояний между вершиной ai и остальными                                    можно с помощью четного графа, в котором вер-
вершинами графа: d k( n−1) = ρ w (ai , a j ) .                                 шины разделены на две группы, а ребра могут со-
       В общем случае задача решается с помощью                                единять лишь вершины разных групп.
алгоритмов Флойда, Форда, Беллмана и др.                                             Применительно к задаче об экспедиции одна
       Алгоритмы нахождения минимального пути                                  группа вершин есть группа из 8 кандидатов, а вто-
могут быть использованы для поиска кратчайших                                  рая – из 6 должностей.
путей в ориентированном графе без контуров. Для                                                   Задача 5.17.
этого нужно каждой дуге приписать вес, равный                                        Планета имеет форму выпуклого многогран-
единице.                                                                       ника, причем в его вершинах расположены города,
                                                                               а каждое ребро является дорогой. Две дороги за-

                                        34                                                               143

Страницы