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

UptoLike

ВУЗ: 

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

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

Рубрика: 

130
При первом способе следования стоимость
прохождения из вершины v
i
в v
j
по всем путям
ранга, не большего k – 1, составит
(1)k
ij
c
−
.
При втором способе следования стоимость
прохождения из v
i
в v
k
по всем путям ранга, не
большего k – 1, будет равна
(1)k
ik
c
−
. Стоимость про-
хождения из v
k
в v
k
по всем замкнутым путям ран-
га, не большего k – 1, составит
(1)k
kk
c
−
.
Стоимость прохождения из вершины v
k
в
вершину v
j
по пути ранга, не большего k – 1, рав-
на
(1)k
kj
c
−
(смотри рис. 5.10).
Таким образом, стоимость прохождения по
пути ранга, не большего k, при указанном способе
следования составит
(1) (1)*(1)
()
kk k
ik kk kj
cc c
−− −
(1)
Описание «путешествия» из v
i
в v
j
по путям
ранга, не большего k, приводит к следующей фор-
муле для вычисления элемента матрицы C
(k)
:
() (1) (1) (1)*(1)
()
kk kk k
ij ij ik kk kj
cc cc c
−
−− −
=+ . (2)
Пусть a
ij
– элементы матрицы меток дуг ори-
ентированного графа. Поскольку каждый путь
ранга 0 между несовпадающими вершинами со-
стоит из одной дуги, а каждая вершина достижима
сама из себя по пути нулевой длины с меткой 1
или по петле с меткой a
ii
, то элементы матрицы
С
(0)
имеют вид:
47
Шаг 5. Восстановление максимального пути про-
изводится по тому же правилу, что и для мини-
мального пути.
Длина максимального пути равна 10. Этот
путь состоит из трех дуг, т. к.
λ
i
(3) =
λ
i
(4) = 10.
Поэтому в соотношении (2) будет выполнено, на-
чиная с n – 1.
Учитывая это замечание, для последней
вершины x
3
предшествующую ей вершину x
r
опре-
делим из соотношения (2) полученного при s = 3:
λ
r
(2) + c
r3
=
λ
3
(3), x
r
∈ G
–1
(x
3
), (7)
где G
–1
(x
3
) – прообраз вершины x
3
.
G
–1
(x
3
) = {x
2
, x
4
}.
Подставим в (7) последовательно r = 2 и r = 4, что-
бы определить, для какого r это равенство выпол-
няется:
λ
2
(2) + c
23
= 1 + 8 ≠
λ
3
(4) = 10,
λ
4
(2) + c
43
= 8 + 2 =
λ
3
(4) = 10.
Таким образом, вершиной, предшествующей
вершине x
3
, является вершина x
4
.
Для вершины x
4
предшествующая ей верши-
на x
r
определяется из соотношения (2) полученно-
го при s = 4:
λ
r
(1) + c
r4
=
λ
4
(2), x
r
∈ G
–1
(x
4
), (8)
где G
–1
(x
4
) – прообраз вершины x
4
.
G
–1
(x
4
) = {x
2
, x
5
}. 
            При первом способе следования стоимость                                     Шаг 5. Восстановление максимального пути про-
прохождения из вершины vi в vj по всем путям                                            изводится по тому же правилу, что и для мини-
ранга, не большего k – 1, составит cij( k −1) .                                         мального пути.
            При втором способе следования стоимость                                           Длина максимального пути равна 10. Этот
прохождения из vi в vk по всем путям ранга, не                                          путь состоит из трех дуг, т. к. λi (3) = λi (4) = 10.
большего k – 1, будет равна cik( k −1) . Стоимость про-                                 Поэтому в соотношении (2) будет выполнено, на-
хождения из vk в vk по всем замкнутым путям ран-                                        чиная с n – 1.
га, не большего k – 1, составит ckk( k −1) .                                                  Учитывая это замечание, для последней
                                                                                        вершины x3 предшествующую ей вершину xr опре-
            Стоимость прохождения из вершины vk в
                                                                                        делим из соотношения (2) полученного при s = 3:
вершину vj по пути ранга, не большего k – 1, рав-
                                                                                                λr (2) + cr3 = λ3 (3), xr ∈ G –1(x3), (7)
на ckj( k −1) (смотри рис. 5.10).
                                                                                        где G –1(x3) – прообраз вершины x3.
            Таким образом, стоимость прохождения по                                                         G –1(x3) = {x2, x4}.
пути ранга, не большего k, при указанном способе                                        Подставим в (7) последовательно r = 2 и r = 4, что-
следования составит                                                                     бы определить, для какого r это равенство выпол-
                               cik( k −1) (ckk( k −1) )* ckj( k −1)               (1)   няется:
            Описание «путешествия» из vi в vj по путям                                              λ2 (2) + c23 = 1 + 8 ≠ λ3 (4) = 10,
ранга, не большего k, приводит к следующей фор-                                                     λ4 (2) + c43 = 8 + 2 = λ3 (4) = 10.
муле для вычисления элемента матрицы C(k):                                                    Таким образом, вершиной, предшествующей
                   cij( k ) = cij( k −1) + cik( k −1) (ckk( k −1) )* ckj( k −1) . (2)   вершине x3, является вершина x4.
            Пусть aij – элементы матрицы меток дуг ори-                                       Для вершины x4 предшествующая ей верши-
ентированного графа. Поскольку каждый путь                                              на xr определяется из соотношения (2) полученно-
ранга 0 между несовпадающими вершинами со-                                              го при s = 4:
стоит из одной дуги, а каждая вершина достижима                                                 λr (1) + cr4 = λ4 (2), xr ∈ G –1(x4), (8)
сама из себя по пути нулевой длины с меткой 1                                           где G –1(x4) – прообраз вершины x4.
или по петле с меткой aii, то элементы матрицы                                                              G –1(x4) = {x2, x5}.
С(0) имеют вид:


                                            130                                                                     47

Страницы