ВУЗ:
Составители:
Рубрика:
80
c) Повторить пункт b) с предварительным увеличением номера
итерации на 1. ■
В результате выполнения этой процедуры на некоторой n-й итера-
ции получим, что условие L
n
(ν
k
) ≤ L
n
(ν
j
) + l
(ν
j
, ν
k
) выполняется для каждой
дуги (ν
j
, ν
k
), являющейся хордой дерева T
n
. В этом случае, согласно тео-
реме, дерево T
n
является максимальным деревом кратчайших расстояний.
Проиллюстрируем применение итерационной процедуры поиска
максимального дерева кратчайших расстояний на примере взвешенного
ориентированного графа, представленного на рис. 43.
Зададим в качестве нулевой итерации дерево Т
0
с корнем ν
0
, которое
включает в себя все вершины, достижимые из вершины ν
0
(рис. 44, а).
Каждой вершине ν
k
этого дерева сопоставлено значение L
0
(ν
k
).
Хорда (
*
1
v
, ν
5
) является «улучшающей» хордой, поскольку L
0
(ν
5
) = 3 >
> L
0
(
*
1
v
) + l
(
*
1
v
, ν
5
) = 0 + 1 = 1. Получим дерево Т
1
из дерева Т
0
добавле-
нием этой хорды и вычёркиванием дуги (ν
4
, ν
5
), конечной вершиной ко-
торой также является вершина ν
5
(рис. 44, б).
Хорды (ν
2
, ν
6
) и (ν
3
, ν
7
) «улучшающими» не являются, так как L
1
(ν
6
) =
= 1 ≤ L
1
(ν
2
) + l
(ν
2
, ν
6
) = 1 + 1 = 2 и L
1
(ν
7
) = 2 ≤ L
1
(ν
3
) + l
(ν
3
, ν
7
) = 3 + 2 = 5.
Добавлением «улучшающей» хорды (
*
5
v
, ν
9
) и вычёркиванием дуги
(ν
8
, ν
9
) получаем дерево Т
2
из дерева Т
1
(рис. 44, в).
Наконец, включение последней «улучшающей» хорды (
*
7
v
, ν
11
) даёт
дерево кратчайших расстояний Т
3
(рис. 44, г).
Проверяя все хорды дерева Т
3
, можно убедиться, что оно действи-
тельно является деревом кратчайших расстояний.
Заметим, что полагая длину l(u) = 1 для всех дуг u ∈ U графа G,
можно найти кратчайшие пути в том смысле, что они содержат наимень-
шее число дуг.
ν
0
ν
1
ν
2
ν
3
ν
4
ν
5
ν
6
ν
7
ν
8
ν
9
ν
10
ν
11
0
1
2
2
0
1
1
0 2
1
1
1
2
2
1 1
1
Рис. 43
Страницы
- « первая
- ‹ предыдущая
- …
- 78
- 79
- 80
- 81
- 82
- …
- следующая ›
- последняя »
