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

UptoLike

ВУЗ: 

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

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

Рубрика: 

36
При этом
λ
i
(k) определяет длину минимального
пути из первой вершины в i – ую, содержащего не
более k дуг.
Шаг 5. Восстановление минимального пути. Для
любой вершины x
s
предшествующая ей вершина
x
r
определяется из соотношения:
λ
r
(n – 2) + c
rs
=
λ
s
(n – 1), x
r
∈ G
–1
(x
s
), (2)
где G
–1
(x
s
) – прообраз вершины x
s
.
Для найденной вершины x
r
предшествующая
ей вершина x
q
определяется из соотношения:
λ
q
(n – 3) + c
qr
=
λ
r
(n – 2), x
q
∈ G
–1
(x
r
),
где G
–1
(x
r
) – прообраз вершины x
r
, и т. д.
Последовательно применяя это соотноше-
ние, начиная от последней вершины x
i
, найдем ми-
нимальный путь.
Пример 1.20.
С помощью алгоритма 1 найдем минималь-
ный путь из вершины х
1
в вершину х
3
в графе, изо-
браженном на рис. 1.16.
Рис. 1.16.
141
а
23
= 1 – из 2 выходит одна стрелка к вершине 3;
а
24
= 0 – из 2 не выходит ни одной стрелки к
вершине 4;
а
31
= 1 – из 3 выходит одна стрелка к вершине 1;
а
32
= 0 – из 3 не выходит ни одной стрелки к вер-
шине 2;
а
33
= 0 – при 3 нет петель;
а
34
= 1 – из 3 выходит одна стрелка к вершине 4;
а
41
= 3 – из 4 выходит 3 стрелки к вершине 1;
а
42
= 1 – из 4 выходит одна стрелка к вершине 2;
а
43
= 0 – из 4 не выходит ни одной стрелки к вер-
шине 3;
а
44
= 0 – при 4 нет петель.
Строим орграф (рис. 5.17).
Рис. 5.17.
Для построенного графа запишем матрицу инци-
дентности: 
При этом λi (k) определяет длину минимального        а23 = 1 – из 2 выходит одна стрелка к вершине 3;
пути из первой вершины в i – ую, содержащего не      а24 = 0 – из 2 не выходит ни одной стрелки к
более k дуг.                                                   вершине 4;
Шаг 5. Восстановление минимального пути. Для         а31 = 1 – из 3 выходит одна стрелка к вершине 1;
любой вершины xs предшествующая ей вершина           а32 = 0 – из 3 не выходит ни одной стрелки к вер-
xr определяется из соотношения:                                шине 2;
                                                     а33 = 0 – при 3 нет петель;
   λr (n – 2) + crs = λs (n – 1),
                               xr ∈ G –1 (xs), (2)
                                                     а34 = 1 – из 3 выходит одна стрелка к вершине 4;
где G –1(xs) – прообраз вершины xs.                  а41 = 3 – из 4 выходит 3 стрелки к вершине 1;
      Для найденной вершины xr предшествующая        а42 = 1 – из 4 выходит одна стрелка к вершине 2;
ей вершина xq определяется из соотношения:           а43 = 0 – из 4 не выходит ни одной стрелки к вер-
      λq (n – 3) + cqr = λr (n – 2),xq ∈ G –1(xr),             шине 3;
где G –1(xr) – прообраз вершины xr, и т. д.          а44 = 0 – при 4 нет петель.
                                                            Строим орграф (рис. 5.17).
      Последовательно применяя это соотноше-
ние, начиная от последней вершины xi, найдем ми-
нимальный путь.
                  Пример 1.20.
     С помощью алгоритма 1 найдем минималь-
ный путь из вершины х1 в вершину х3 в графе, изо-
браженном на рис. 1.16.


                                                                          Рис. 5.17.

                                                     Для построенного графа запишем матрицу инци-
                                                     дентности:
                        Рис. 1.16.


                               36                                               141

Страницы