Предположим, что уже построена простая цепь m k -1 = { e 1, e 2, …, ek -1} для k ³2 методом, указанным в алгоритме. Пусть ek -1 = (xk -2, xk -1) и xk -1 ¹ a. Рассмотрим подграф , который получается из подграфа Gk -1(X, E\ m k -1) удалением всех изолированных вершин. Вершина xk -1 в этом подграфе имеет нечетную степень, поэтому существует по крайней мере одно ребро ek Î E\ m k -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 ребра порождают компоненты связности C 1, …, Cm (m ³1) в подграфе . Пусть компонента Ci, 1£ i £ m соединяется с циклом m в вершине yi. Если существует ребро e Îm, такое, что e =(yi, a), то при построении цикла m было нарушено правило выбора ребра e, что невозможно. Если часть цикла m, соединяющая yi и a, состоит более чем из одного ребра, то первое ребро этой части было мостом, и поэтому было нарушено правило выбора , что невозможно. Итак, непройденных ребер быть не может, поэтому m - эйлеров цикл.
8.НАХОЖДЕНИЕ КРАТЧАЙШИХ ПУТЕЙ В ГРАФЕ
В этом параграфе рассматриваются ориентированные графы G (X, E) каждой дуге e Î E которого ставится в соответствие вещественное число l (e). Т.е. на множестве Е создана функция l: E ® R. Такой граф принято называть нагруженным. Само число l называется весом дуги.
Можно увидеть аналогию между, например, картой автомобильных или железных дорог. Тогда множество вершин Х будет соответствовать городам, множество дуг – магистралям, соединяющим города, а веса – расстояниям. (На практике, при этом, фактически получится неориентированный граф).
В связи с изложенной аналогией будем называть веса дуг расстояниями.
Определение 8.1. Пусть имеется последовательность вершин x 0, x 1, …, xn, которая определяет путь в нагруженном графе G (X, E), тогда длина этого пути определяется как .
Естественный интерес представляет нахождение кратчайшего пути между двумя заданными вершинами x и y.
Алгоритм Форда отыскания кратчайшего пути.
Будем предполагать, что все расстояния в графе положительны. (Если это не так, то ко всем весам можно всегда добавить такую константу, что все эти веса станут положительными).
Пусть мы ищем путь от вершины x 0 к вершине xn. Будем каждой вершине xi ставить в соответствие некоторое число l i по следующим правилам.
1° Положим l0= 0, l i = ¥ (достаточно большое число) для " i > 0.
2° Ищем в графе дугу (xi, xj) удовлетворяющую следующему условию
l j - l i > l (xi, xj), (1)
после чего заменяем l j на
.
Пункт 2° повторяется до тех пор, пока невозможно будет найти дугу, удовлетворяющую условию (1). Обоснуем этот алгоритм и укажем как определяется кратчайший путь.
Отметим, что l n монотонно уменьшается, то после завершения алгоритма найдется дуга , такая, что для которой последний раз уменьшалось l n. (Иначе вообще нет пути между x 0 и xn или для верно (1)).
По этой же самой причине найдется вершина , такая, что
,
этот процесс может продолжаться и дальше, так что получится строго убывающая последовательность . Отсюда следует, что при некотором k мы получим .
Покажем, что – минимальный путь с длиной l n, т.е. длина любого другого пути между x 0 и xn не превышает kn.
Возьмем произвольный путь и рассмотрим его длину .
После завершения алгоритма имеем следующие соотношения
Сложив все эти неравенства, получим
,
что и требовалось доказать.
Рассмотрим пример.
а б
Рис. 8.1
На рис. 1а изображен исходный помеченный граф и начальные значения l i. На рис. 1б для того же графа указаны конечные значения l i и выделен кратчайший путь. Пометка вершин графа происходила в следующем порядке (в скобках указана дуга, вдоль которой выполняется (1)):
l1 = 6 (x 0, x 1),
l2 = 7 (x 0, x 2),
l3 = 6 (x 0, x 3),
l4 = 12 (x 1, x 3),
l4 = 11 (x 2, x 4),
l5 = 16 (x 3, x 4),
l5 = 15 (x 4, x 5),
l6 = 18 (x 4, x 6),
l6 = 17 (x 5, x 6).
Иногда возникает задача отыскания кратчайших расстояний между всеми парами вершин. Одним из способов решения этой задачи является