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

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

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

РЕФЕРАТ

на тему:

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

МИНСК, 2008

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

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

а) б)

Рис. 1.

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

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

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

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

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

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

. В графе все вершины имеют четные степени. Пусть — компоненты связности графа , содержащие хотя бы по одному ребру. Согласно предположению индукции все эти компоненты обладают эйлеровыми циклами m₁, m₁, …, m_k соответственно. Так как граф G связан, то цепь m встречает каждую из компонент . Пусть первые встречи цикла m с компонентами происходят соответственно в вершинах x₁, x₂, …, x_k. Тогда простая цепь

n(a, a)=m(a, x₁) Um₁(x₁, x₁) Um(x₁, x₂) U…Um_k(x_k, x_k) Um(x_k, a)

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

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

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

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

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

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

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

.

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

графа Gпокрывает его, если все ребра графа G включены в цепи m_i. Нужно найти наименьшее количество таких цепей, которыми можно покрыть заданный граф G.

Если граф G — эйлеров, то очевидно, что это число равно 1. Пусть теперь G не является эйлеровым графом. Обозначим через k число его вершин нечетной степени. По теореме … k четно. Очевидно, что каждая вершина нечетной степени должна быть концом хотя бы одной из покрывающих G цепей m_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₁=(a, x₁) , инцидентное вершине a, и положим m = {e₁}.

2°. Рассмотрим подграф G₁(X, E\m₁). Возьмем в качестве e₂ ребро, инцидентное вершине x₁ и неинцидентное вершине a, которое также не является мостом в подграфе G₁ (если такое ребро e₂ существует!). Получим простую цепь m₂ = {e₁, e₂}.

3°. Пусть e₂ = (x₁, x₂), x¹a. Рассмотрим подграф G₂(X, E\m₂) и удалим из него все изолированные вершины. В полученном подграфе

выберем ребро e₃ÎE\m₂, инцидентное вершине a, которое не является мостом в подграфе (если такое ребро e₃ существует!). Получим простую цепь

m₃ = {e₁, e₂, e₃}.

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

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

Предположим, что уже построена простая цепь 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 и не являющееся мостом. Значит, и в этом случае процесс можно продолжать, взяв