Построение эйлерова цикла. Алгоритм Форда и Уоршелла (стр. 2 из 3)

.

Из предыдущего следует, что процесс нельзя продолжать тогда и только тогда, когда мы попадем в вершину a, причем степень вершины a относительно непройденных ребер равна нулю. Докажем, что в этом случае построенный цикл m - простой цикл. Покажем, что m содержит все ребра графа G. Если не все ребра графа G принадлежат m, то не принадлежащие m ребра порождают компоненты связности C₁, …, C_m (m³1) в подграфе

. Пусть компонента C_i, 1£i£m соединяется с циклом m в вершине y_i. Если существует ребро eÎm , такое, что e=(y_i, a), то при построении цикла m было нарушено правило выбора ребра e, что невозможно. Если часть цикла m, соединяющая y_i и a, состоит более чем из одного ребра, то первое ребро этой части было мостом, и поэтому было нарушено правило выбора , что невозможно. Итак, непройденных ребер быть не может, поэтому m - эйлеров цикл.

2. НАХОЖДЕНИЕ КРАТЧАЙШИХ ПУТЕЙ В ГРАФЕ

Рассматрим ориентированные графы G(X, E) каждой дуге eÎE которого ставится в соответствие вещественное число l(e). Т.е. на множестве Е создана функция l:E®R. Такой граф принято называть нагруженным. Само число l называется весом дуги.

Можно увидеть аналогию между, например, картой автомобильных или железных дорог. Тогда множество вершин Х будет соответствовать городам, множество дуг – магистралям, соединяющим города, а веса – расстояниям. (На практике, при этом, фактически получится неориентированный граф).

В связи с изложенной аналогией будем называть веса дуг расстояниями.

Определение 2.1. Пусть имеется последовательность вершин x₀, x₁, …, x_n, которая определяет путь в нагруженном графе G(X, E), тогда длина этого пути определяется как

.

Естественный интерес представляет нахождение кратчайшего пути между двумя заданными вершинами x и y.

Алгоритм Форда отыскания кратчайшего пути.

Будем предполагать, что все расстояния в графе положительны. (Если это не так, то ко всем весам можно всегда добавить такую константу, что все эти веса станут положительными).

Пусть мы ищем путь от вершины x₀ к вершине x_n. Будем каждой вершине x_i ставить в соответствие некоторое число l_i по следующим правилам.

1° Положим l₀= 0, l_i= ¥ (достаточно большое число) для "i > 0.

2° Ищем в графе дугу (x_i, x_j) удовлетворяющую следующему условию

l_j - l_i > l(x_i, x_j), (1)

после чего заменяем l_j на

.

Пункт 2°повторяется до тех пор, пока невозможно будет найти дугу, удовлетворяющую условию (1). Обоснуем этот алгоритм и укажем как определяется кратчайший путь.

Отметим, что l_n монотонно уменьшается, то после завершения алгоритма найдется дуга

, такая, что

для которой последний раз уменьшалось l_n. (Иначе вообще нет пути между x₀ и x_n или для верно (1)).

По этой же самой причине найдется вершина

, такая , что

,

этот процесс может продолжаться и дальше, так что получится строго убывающая последовательность

. Отсюда следует, что при некотором k мы получим .

Покажем, что

– минимальный путь с длиной l_n, т.е. длина любого другого пути между x₀ и x_n не превышает k_n.

Возьмем произвольный путь

и рассмотрим его длину .

После завершения алгоритма имеем следующие соотношения

Сложив все эти неравенства, получим

,

что и требовалось доказать.

Рассмотрим пример.

а б

Рис. 2.1

На рис. 2.1а изображен исходный помеченный граф и начальные значения l_i. На рис. 2.1б для того же графа указаны конечные значения l_i и выделен кратчайший путь. Пометка вершин графа происходила в следующем порядке (в скобках указана дуга, вдоль которой выполняется (1)):

l₁ = 6 (x₀, x₁),

l₂ = 7 (x₀, x₂),

l₃ = 6 (x₀, x₃),

l₄ = 12 (x₁, x₃),

l₄ = 11 (x₂, x₄),

l₅ = 16 (x₃, x₄),

l₅ = 15 (x₄, x₅),

l₆ = 18 (x₄, x₆),

l₆ = 17 (x₅, x₆).

Иногда возникает задача отыскания кратчайших расстояний между всеми парами вершин. Одним из способов решения этой задачи является

Алгоритм Флойда

Обозначим l_ij длину дуги (x_i, x_j), если таковой не существует примем l_ij = ¥, кроме того, положим l_ii = 0. Обозначим

длину кратчайшего из путей из x_i в x_j с промежуточными вершинами из множества {x₁, …, x_m}. Тогда можно получить следующие уравнения

, (2)

. (3)

Уравнение (2) очевидно. Обоснуем уравнение (3). Рассмотрим кратчайший путь из x_i в x_j с промежуточными вершинами из множества {x₁, …, x_m, x_m+1}. Если этот путь не содержит x_m+1, то

. Если же он содержит x_m+1, то деля путь на отрезки от x_i до x_m+1 и от x_m+1 до x_j, получаем равенство .

Уравнения (2) и (3) позволяют легко вычислить матрицу расстояний [d_ij] между всеми парами вершин графа G(X, E). На первом этапе согласно (2) составляем n´n матрицу

равную матрице [l_ij] весов ребер (n – число вершин G(X, E)). n раз производим вычисление по итерационной формуле (3), после чего имеем – матрицу расстояний.

Отметим, что алгоритм Флойда непосредственно не указывает сам кратчайший путь между вершинами, а только его длину. Алгоритм Флойда можно модифицировать таким образом, чтобы можно было находить и сами пути. Для этого получим вспомогательную матрицу [R_ij], которая будет содержать наибольший номер вершины некоторого кратчайшего пути из x_i в x_j (R_ij=0, если этот путь не содержит промежуточных вершин).