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

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

Предположим, что уже построена простая цепь m_k _-1 = {e ₁ , e ₂ , …, e_k _-1 } для k ³2 методом, указанным в алгоритме. Пусть e_k _-1 = (x_k _-2 , x_k _-1 ) и x_k _-1 ¹a . Рассмотрим подграф , который получается из подграфа G _k _-1 (X , E\ m_k _-1 ) удалением всех изолированных вершин. Вершина x_k _-1 в этом подграфе имеет нечетную степень, поэтому существует по крайней мере одно ребро e_k ÎE\ m_k _-1 , инцидентное x_k _-1 . Если это ребро единственное, то оно не является мостом в графе . В противном случае вершина a будет связана с некоторой вершиной единственной цепью, содержащей ребро e_k , что противоречит существованию эйлерова цикла в графе G . Поскольку e_k - не мост, то процесс можно продолжать, взяв . Если ребро e_k не единственное инцидентное вершине x_k _-1 , то среди этих ребер есть по крайней мере одно, не являющееся мостом. В противном случае один из этих мостов можно выбросить так, что вершины x_k _-1 и a попадут в разные компоненты связности графа . Если x_k _-1 принадлежит компоненте M , то в этой компоненте все вершины имеют четную степень, поэтому существует эйлеров цикл в M , проходящий через x_k _-1 . Этот цикл содержит все ребра, инцидентные x_k _-1 и принадлежащие , являющиеся одновременно мостами. Получено противоречие, так как ребра из эйлерова цикла мостами быть не могут. Итак, в рассмотренном случае существует ребро e_k , инцидентное вершине x_k _-1 и не являющееся мостом. Значит, и в этом случае процесс можно продолжать, взяв

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