Реферат: Построение эйлерова цикла. Алгоритм Форда и Уоршелла

                                          .

Из предыдущего следует, что процесс нельзя продолжать тогда и только тогда, когда мы попадем в вершину a, причем степень вершины a относительно непройденных ребер равна нулю. Докажем, что в этом случае построенный цикл m - простой цикл. Покажем, что m содержит все ребра графа G. Если не все ребра графа G принадлежат m, то не принадлежащие m ребра порождают компоненты связности C1, …, Cm (m³1) в подграфе . Пусть компонента Ci, 1£i£m соединяется с циклом m в вершине yi. Если существует ребро eÎm , такое, что e=(yi, a), то при построении цикла m было нарушено правило выбора ребра e, что невозможно. Если часть цикла m, соединяющая yi и a, состоит более чем из одного ребра, то первое ребро этой части  было мостом, и поэтому было нарушено правило вы­бора , что невозможно. Итак, непройденных ребер быть не может, поэ­тому m - эйлеров цикл.

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

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

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

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

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

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

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

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

Пусть мы ищем путь от вершины x0 к вершине xn. Будем каждой вершине xi ставить в соответствие некоторое число li по следующим правилам.

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

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

                                           lj - li > l(xi, xj),                                            (1)

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

                                         .

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

Отметим, что ln монотонно уменьшается, то после завершения алгоритма найдется дуга , такая, что  для которой последний раз уменьшалось ln. (Иначе вообще нет пути между x0 и xn или для  верно (1)).

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

                                     ,

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

Покажем, что  – минимальный путь с длиной ln, т.е. длина любого другого пути между x0 и xn не превышает kn.

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

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

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

                                ,

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

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

а                                                               б

Рис. 2.1

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

l1 = 6    (x0, x1),

l2 = 7    (x0, x2),

l3 = 6    (x0, x3),

l4 = 12   (x1, x3),

l4 = 11   (x2, x4),

l5 = 16   (x3, x4),

l5 = 15   (x4, x5),

l6 = 18   (x4, x6),

l6 = 17   (x5, x6).

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

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

Обозначим lij длину дуги (xi, xj), если таковой не существует примем lij = ¥, кроме того, положим lii = 0. Обозначим  длину кратчайшего из путей из xi в xj с промежуточными вершинами из множества {x1, …, xm}. Тогда можно получить следующие уравнения

                                                ,                                                 (2)

                               .                                 (3)

Уравнение (2) очевидно. Обоснуем уравнение (3). Рассмотрим кратчай­ший путь из xi в xj с промежуточными вершинами из множества {x1, …, xm, xm+1}. Если этот путь не содержит xm+1, то . Если же он содержит xm+1, то деля путь на отрезки от xi до xm+1 и от xm+1 до xj, получаем равенство .

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

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

Эта матрица вычисляется параллельно с  по следующим правилам

Последнее выражение следует из обоснования (3).

Теперь кратчайший путь выписывается из следующего рекурсивного алгоритма:

Кратчайший путь из xi в xj:

1°. Если Rij = 0    то выполнить 2°,

иначе выполнить 3°.

2°. Если i=j         то выписать xi и закончить,

иначе выписать xi и xj закончить.

3°. Выписать кратчайший путь между xi и .

4°. Выписать кратчайший путь между  и xj.

Пункты 3° и 4° предполагают рекурсивное обращение к рассмотренному алгоритму.

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

Напомним, что бинарным отношением на множестве Х называется произвольное подмножество E Ì X ´ X.

Страницы: 1, 2, 3