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

1°. Пусть a — произвольная вершина графа G. Возьмем любое ребро e1=(a, x1) , инцидентное вершине a, и положим m = {e1}.

2°. Рассмотрим подграф G1(X, E\m1). Возьмем в качестве e2 ребро, инци­дентное вершине x1 и неинцидентное вершине a, которое также не является мостом в подграфе G1 (если такое ребро e2 существует!). Получим простую цепь m2 = {e1, e2}.

3°. Пусть e2 = (x1, x2), x ¹ a

. Рассмотрим подграф G2(X, E\m2) и удалим из него все изо­лированные вер­шины. В полученном подграфе выберем ребро e3ÎE\m2, инцидентное вершине a, которое не является мостом в под­графе (если такое ребро e3 суще­ству­ет!). Получим простую цепь

m3 = {e1, e2, e3}.

Продолжая указанный процесс, мы через конечное число шагов получим эйлеров цикл m = {e1, e2, …, en}, где n — число ребер графа G(X, E).

Обоснование алгоритма

Предположим, что уже построена простая цепь mk-1 = {e1, e2, …, ek-1} для k³2 методом, указанным в алгоритме. Пусть ek-1 = (xk-2, xk-1) и xk-1 ¹ a. Рас­смо­трим подграф , который получается из подграфа Gk-1(X, E\mk-1) удалением всех изолированных вершин. Вершина xk-1 в этом подграфе имеет нечет­ную степень, поэтому существует по крайней мере одно ребро ekÎE\mk-1, ин­ци­дентное xk-1. Если это ребро единственное, то оно не является мостом в графе . В противном случае вершина a будет связана с некоторой вер­ши­ной единственной цепью, содержащей ребро ek, что противоречит суще­ствованию эйлерова цикла в графе G. Поскольку ek - не мост, то процесс мож­но продолжать, взяв . Если ребро ek не единственное инци­дентное вершине xk-1, то среди этих ребер есть по крайней мере одно, не явля­ющееся мостом. В противном случае один из этих мостов можно выбро­сить так, что вершины xk-1 и a попадут в разные компоненты связности графа . Если xk-1 принадлежит компоненте M, то в этой компоненте все вер­шины имеют четную степень, поэтому существует эйлеров цикл в M, про­хо­дящий через xk-1. Этот цикл содержит все ребра, инцидентные xk-1 и при­над­лежащие , являющиеся одновременно мостами. Получено противоречие, так как ребра из эйлерова цикла мостами быть не могут. Итак, в рассмотренном случае существует ребро ek, инцидентное вершине xk-1 и не являющееся мостом. Значит, и в этом случае процесс можно продолжать, взяв

.

Из предыдущего следует, что процесс нельзя продолжать тогда и только тогда, когда мы попадем в вершину 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.

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

 Скачать реферат