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

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

Кафедра информатики

РЕФЕРАТ

на тему:

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

МИНСК, 2008

1. Эйлеровы цепи и циклы

Рассматриваемая задача является одной из самых ста­рей­ших в теории графов. В городе Кенигсберге (ныне Калининград) имелось семь мостов, соединяющих два берега реки Преголь, и два основа на ней друг с другом (рис. 1а). Требуется, начав путешествие из одной точки города прой­ти по всем мостам по одному разу и вернуться в исходную точку.

а) б)

Рис. 1.

Если поставить в соответствие мостам ребра, а участкам суши — вершины, то получится граф (точнее псевдограф), в котором надо найти про­стой цикл, проходящий через все ребра. В общем виде эта задача была решена Эйлером в 1736 г.

Определение 1. Эйлеровой цепью в неориентированном графе G называется простая цепь, содержащая все ребра графа G. Эйлеровым циклом назы­вается замкнутая Эйлерова цепь. Аналогично, эйлеров путь в орграфе G — это простой путь, содержащий все дуги графа G. Эйлеров контур в орграфе G — это замкнутый эйлеров путь. Граф, в котором существует эйлеров цикл, называется эйлеровым.

Простой критерий существования эйлерова цикла в связном графе дается следующей теоремой.

Теорема 1. (Эйлер) Эйлеров цикл в связном неориентированном графе G(X, E) существует только тогда, когда все его вершины имеют четную степень.

Доказательство. Необходимость. Пусть  - эйлеров цикл в связном гра­фе G, x — произвольная вершина этого графа. Через вершину x эйлеров цикл проходит некоторое количество k (k1) раз, причем каждое прохождение, очевидно, включает два ребра, и степень этой вершины равна 2k, т.е. четна, так как x выбрана произвольно, то все вершины в графе G имеют четную сте­пень.

Достаточность. Воспользуемся индукцией по числу m ребер графа. Эйле­ровы циклы для обычных (не псевдо) графов можно построить начиная с m=3.Легко проверить, что единственный граф с m=3, имеющий все вершины с четными степенями, есть граф K_>3> (рис. 2). Существование эйлерова цикла в нем очевидно. Таким образом, для m=3 достаточность условий доказываемой теоремы имеет место. Пусть теперь граф G имеет m>3 ребер, и пусть утверждение справедливо для всех связных графов, имеющих меньше, чем m ребер. Зафиксируем произвольную вершину a графа G и будем искать простой цикл, идущий из a в a. Пусть (a, x) — простая цепь, иду­щая из a в некоторую вершину x. Если x  a, то цепь  можно продолжить из вершины x в некотором направлении. Через некоторое число таких про­дол­­же­ний мы придем в вершину zX, из которой нельзя продлить полу­чен­ную про­стую цепь. Легко видеть, что z = a так как из всех остальных вершин цепь может выйти (четные степени!); a в a она начиналась. Таким образом, нами построен цикл , идущий из a в a. Предположим, что построенный про­стой цикл не содержит всех ребер графа G. Удалим ребра, входящие в цикл , из графа G и рассмотрим полученный граф . В графе все вершины имеют четные степени. Пусть — компо­нен­ты связ­нос­ти графа , содержащие хотя бы по одному ребру. Соглас­но пред­поло­же­нию индукции все эти компоненты обладают эйлеровыми циклами _>1>, _>1>, …, _>k> соот­вет­ствен­но. Так как граф G связан, то цепь  встре­чает каждую из компонент. Пусть первые встречи цикла  с ком­понентами происходят соответственно в вершинах x_>1>, x_>2>, …, x_>k>. Тогда про­стая цепь

(a, a)=(a, x_>1>)  _>1>(x_>1>, x_>1>)  (x_>1>, x_>2>) … _>k>(x_>k>, x_>k>)  (x_>k>, a)

является эйлеровым циклом в графе G. Теорема доказана.

Замечание. Очевидно, что приведенное доказательство будет верно и для псевдографов, содержащих петли и кратные ребра (см. рис. 1,а).

Таким образом, задача о кенигсбергских мостах не имеет ре­ше­ния, так как соответствующий граф (см. рис. 1,б) не имеет эйлерова цикла из-за не­четности степеней все вершин.

Отметим, что из существования эйле­ро­ва цикла в неориентированном графе G не следует связность этого графа. Напри­мер, неориентированный граф G на рис. 3 обладает эйлеровым циклом и вместе с тем несвязен.

Совершенно также, как теорема 1, могут быть доказаны следующие два утверждения.

Теорема 2. Связный неориентированный граф G обладает эйлеровой цепью тогда и только тогда, когда число вершин нечетной степени в нем равно 0 или 2, причем если это число равно нулю, то эйлерова цепь будет являться и циклом.

Теорема 3. Сильно связный орграф G(X, E) обладает эйлеровым кон­ту­ром тогда и только тогда, когда для любой вершины xX выполняется

.

Можно также обобщить задачу, которую решал Эйлер следующим обра­зом. Будем говорить что множество не пересекающихся по ребрам простых цепей графа G покрывает его, если все ребра графа G включены в цепи _>i>. Нужно найти наименьшее количество таких цепей, которыми можно покрыть заданный граф G.

Если граф G — эйлеров, то очевидно, что это число равно 1. Пусть теперь G не является эйлеровым графом. Обозначим через k число его вер­шин нечетной степени. По теореме … k четно. Очевидно, что каждая верши­на нечетной степени должна быть концом хотя бы одной из покрывающих G цепей _>i>. Следовательно, таких цепей будет не менее чем k/2. С другой сто­роны, таким количеством цепей граф G покрыть можно. Чтобы убедиться в этом, расширим G до нового графа , добавив k/2 ребер , соединяющих раз­личные пары вершин нечетной степени. Тогда оказывается эйлеровым графом и имеет эйлеров цикл . После удаления из ребер граф разло­жится на k/2 цепей, покрывающих G. Таким образом, доказана.

Теорема 4. Пусть G — связный граф с k>0 вершинами нечетной степени. Тогда минимальное число непересекающихся по ребрам простых цепей, покрывающих G, равно k/2.

Алгоритм построения эйлерова цикла

Для начала отметим, что теорема 1 также дает метод построения эйлерова цикла. Здесь мы рассмотрим несколько иной алгоритм.

Пусть G(X, E) — связный неорентированный граф, не имеющий вершин нечетной степени. Назовем мостом такое ребро, удаление которого из связного графа разбивает этот граф на две компоненты связности, имеющие хотя бы по одному ребру.

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

2. Рассмотрим подграф G_>1>(X, E\_>1>). Возьмем в качестве e_>2> ребро, инци­дентное вершине x_>1> и неинцидентное вершине a, которое также не является мостом в подграфе G_>1> (если такое ребро e_>2> существует!). Получим простую цепь _>2> = {e_>1>, e_>2>}.

3. Пусть e_>2 >= (x_>1>, x_>2>), x  a. Рассмотрим подграф G_>2>(X, E\_>2>) и удалим из него все изо­лированные вер­шины. В полученном подграфе выберем ребро e_>3>E\_>2>, инцидентное вершине a, которое не является мостом в под­графе (если такое ребро e_>3> суще­ству­ет!). Получим простую цепь

_>3> = {e_>1>, e_>2>, e_>3>}.

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

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

Предположим, что уже построена простая цепь _>k>_>-1> = {e_>1>, e_>2>, …, e_>k>_>-1>} для k2 методом, указанным в алгоритме. Пусть e_>k>_>-1> = (x_>k>_>-2>, x_>k>_>-1>) и x_>k>_>-1>  a. Рас­смо­трим подграф , который получается из подграфа G_>k>_>-1>(X, E\_>k>_>-1>) удалением всех изолированных вершин. Вершина x_>k>_>-1> в этом подграфе имеет нечет­ную степень, поэтому существует по крайней мере одно ребро e_>k>E\_>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 относительно непройденных ребер равна нулю. Докажем, что в этом случае построенный цикл  - простой цикл. Покажем, что  содержит все ребра графа G. Если не все ребра графа G принадлежат , то не принадлежащие  ребра порождают компоненты связности C_>1>, …, C_>m> (m1) в подграфе . Пусть компонента C_>i>, 1im соединяется с циклом  в вершине y_>i>. Если существует ребро e , такое, что e=(y_>i>, a), то при построении цикла  было нарушено правило выбора ребра e, что невозможно. Если часть цикла , соединяющая y_>i> и a, состоит более чем из одного ребра, то первое ребро этой части было мостом, и поэтому было нарушено правило вы­бора , что невозможно. Итак, непройденных ребер быть не может, поэ­тому  - эйлеров цикл.

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

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

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

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

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

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

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

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

Пусть мы ищем путь от вершины x_>0> к вершине x_>n>. Будем каждой вершине x_>i> ставить в соответствие некоторое число _>i> по следующим правилам.

1 Положим _>0>= 0, _>i>_> >=  (достаточно большое число) для i > 0.

2 Ищем в графе дугу (x_>i>, x_>j>) удовлетворяющую следующему условию

_>j> - _>i> > l(x_>i>, x_>j>), (1)

после чего заменяем _>j> на

.

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

Отметим, что _>n> монотонно уменьшается, то после завершения алгоритма найдется дуга , такая, что для которой последний раз уменьшалось _>n>. (Иначе вообще нет пути между x_>0> и x_>n> или для верно (1)).

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

,

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

Покажем, что – минимальный путь с длиной _>n>, т.е. длина любого другого пути между x_>0> и x_>n> не превышает k_>n>.

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

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

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

,

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

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

а б

Рис. 2.1

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

_>1> = 6 (x_>0>, x_>1>),

_>2> = 7 (x_>0>, x_>2>),

_>3> = 6 (x_>0>, x_>3>),

_>4> = 12 (x_>1>, x_>3>),

_>4> = 11 (x_>2>, x_>4>),

_>5> = 16 (x_>3>, x_>4>),

_>5> = 15 (x_>4>, x_>5>),

_>6> = 18 (x_>4>, x_>6>),

_>6> = 17 (x_>5>, x_>6>).

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

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

Обозначим l_>ij> длину дуги (x_>i>, x_>j>), если таковой не существует примем l_>ij> = , кроме того, положим l_>ii> = 0. Обозначим длину кратчайшего из путей из x_>i> в x_>j> с промежуточными вершинами из множества x_>1>, …, x_>m>. Тогда можно получить следующие уравнения

, (2)

. (3)

Уравнение (2) очевидно. Обоснуем уравнение (3). Рассмотрим кратчай­ший путь из x_>i> в x_>j> с промежуточными вершинами из множества x_>1>, …, 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, если этот путь не содержит промежуточных вершин).

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

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

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

Кратчайший путь из x_>i> в x_>j>:

1. Если R_>ij> = 0 то выполнить 2,

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

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

иначе выписать x_>i> и x_>j> закончить.

3. Выписать кратчайший путь между x_>i> и .

4. Выписать кратчайший путь между и x_>j>.

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

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

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

Транзитивным называется отношение, удовлетворяющее следующему условию: если (x, y)  E и (y, z)  E, то (x, z)  E для всех x, y, z  X. Отметим, что бинарное отношение можно однозначно представить орграфом G(X, E). Теперь для произвольного отношения Е определим новое отношение Е* следующим образом

E* = {(x, y) | если в G(X, E) существует путь ненулевой длины из x в y}.

Легко проверить, что Е* - транзитивное отношение. Кроме того, Е* является наименьшим транзитивным отношением на Х в том смысле, что для произвольного транзитивного отношения F  E выполняется E*  F. Отно­ше­ние Е* называется транзитивным замыканием отношения Е.

Если отношение Е представить в виде графа G(X, E) в котором каждая дуга имеет вес 1, то транзитивное замыкание Е* можно вычислить с помощью алгоритма Флойда. При этом надо учесть, что

(x_>i>, x_>j>)  E* если .

Для большего удобства алгоритм Флойда в этом случае можно моди­фи­ци­ровать следующим образом.

Положим

.

Вместо (3) запишем

,

где  – дизъюнкция (логическое сложение),

 – конъюнкция (логическое умножение).

После завершения работы алгоритма будем иметь

Модифицированный таким образом алгоритм называется алгоритмом Уоршелла.

ЛИТЕРАТУРА

Баканович Э.А., Волорова Н.А., Епихин А.В. Дискретная математика:. В 2-х ч..– Мн.: БГУИР, 2000.– 52 с., ил. 14 ISBN 985-444-057-5 (ч. 2).

Аттетков А.В., Галкин С.В., Зарубин В.С. Методы оптимизации. М. Иза-во МГТУ им. Н.Э.Баумана, 2003.

Белоусов А.И., Ткачев С.Б. Дискретная математика: Учебник для ВУЗов / Под ред. В.С. Зарубина, А.П. Крищенко.– М.: изд-во МГТУ им. Н.Э. Баумана, 2001.– 744 с. (Сер. Математика в техническом университете; Вып XIX).