Дискретная математика. Громов Ю.Ю - 79 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

79
ны ν
i
∈
V в некоторую вершину ν
j
∈
V, которую обозначим через l
(ν
i
, ν
j
),
также будет представлять собой действительное число.
В зависимости от конкретного приложения эти действительные чис-
ла могут служить мерой физического расстояния, времени, стоимости
или какого-либо другого важного параметра. Для дальнейшего рассмот-
рения существенно, что длина должна быть аддитивна, т.е. длина пути
должна быть равна сумме длин дуг, составляющих этот путь.
Пусть ν
0
и ν
k
представляют две какие-либо вершины графа G. Тогда,
если в графе G существует по крайней мере один путь из ν
0
в ν
k
, задача
нахождения кратчайшего пути из вершины ν
0
в вершину ν
k
состоит в на-
хождении пути минимальной длины l
min
(ν
0
, ν
k
) с начальной вершиной ν
0
и
конечной вершиной ν
k
.
Можно решать и более общую задачу нахождения кратчайших пу-
тей из некоторой исходной вершины ν
0
в любую вершину ν
k
∈
V, дости-
жимую из вершины ν
0
.
Деревом кратчайших расстояний графа G относительно исходной
вершины ν
0
называется ориентированное дерево с корнем в вершине ν
0
такое, что единственный путь из ν
0
до любой вершины ν
k
этого дерева яв-
ляется кратчайшим путём из вершины ν
0
в вершину ν
k
в графе G.
Максимальным деревом кратчайших расстояний графа G относи-
тельно вершины ν
0
называется дерево кратчайших расстояний, которое
включает в себя все вершины графа G, достижимые из вершины ν
0
.
Обозначим длину l
(ν
0
, ν
k
) пути от вершины ν
0
до какой-либо верши-
ны ν
k
графа G через L(ν
k
) и приведём следующую теорему.
Теорема. Пусть Т – дерево с корнем ν
0
в ориентированном графе
G = <V, U>, которое содержит все вершины графа, достижимые из
вершины ν
0
. Дерево Т является деревом кратчайших расстояний относи-
тельно вершины ν
0
тогда и только тогда, когда для любой достижимой
из ν
0
вершины ν
k
любая хорда вида (ν
j
, ν
k
), граничные вершины которой
принадлежат Т, удовлетворяет соотношению L(ν
k
) ≤ L(ν
j
) + l
(ν
j
, ν
k
). ■
Эта теорема даёт основу для итерационной процедуры, в которой
через L
i
(ν
k
) обозначается расстояние от вершины ν
0
до вершины ν
k
в дере-
ве T
i
, полученном на i-й итерации:
a) Задать на нулевой итерации любое дерево Т
0
с корнем ν
0
, которое
включает в себя все вершины, достижимые из вершины ν
0
.
b) Если на i-й итерации каждая хорда вида (ν
j
, ν
k
) по отношению к
дереву Т
i
удовлетворяет условию L
i
(ν
k
) ≤ L
i
(ν
j
) + l(ν
j
, ν
k
), то дерево Т
i
есть
максимальное дерево кратчайших расстояний. Если условие L
i
(ν
k
) ≤ L
i
(ν
j
) +
+ l
(ν
j
, ν
k
) не выполняется, то пусть (
*
j
v , ν
k
) – «улучшающая» хорда такая,
что L
i
(ν
k
) > L
i
(
*
j
v
) + l
(
*
j
v
, ν
k
). Получить дерево Т
i+1
из дерева Т
i
добавле-
нием дуги (
*
j
v , ν
k
) и вычёркиванием другой дуги, конечной вершиной ко-
торой также является вершина ν
k
.

Страницы