Начиная теперь с xi, получаем цикл Ф’, начинающийся и оканчивающийся в xi. Если все оставшиеся ранее ребра использованы для цикла Ф’, то процесс окончен. Нужный эйлеров цикл будет образован частью цикла Ф от вершины x0 до xi, затем циклом Ф’ и, наконец, частью цикла Ф от вершины xi до x0. Если же все еще остались неиспользованные ребра, то объединение построенных выше циклов Ф и Ф’ дает новый цикл Ф. Мы снова можем найти вершину xj, принадлежащую циклу и являющуюся концевой вершиной некоторого неиспользованного ребра. Затем мы можем приступить к построению нового цикла Ф’, начинавшегося в xj, и так до тех пор, пока не будут использованы все ребра и не будет получен таким образом эйлеров цикл Ф. Это доказывает теорему.

Хотя доказательство проведено для неориентированных графов, оно сразу переносится на ориентированные, только требование четно­сти заменяется теперь на такое: число входящих в каждую вершину ребер должно быть равно числу выходящих.

Следствие #1.

Для связного эйлерова графа G множество ребер можно разбить на простые циклы.

Следствие #2.

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

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

Выше был установлен эффективный способ проверки наличия эйлерова цикла в графе. А именно, для этого необходимо и достаточно убедиться, что степени всех вершин четные, что нетрудно сделать при любом представлении графа. Осталось заметить, что предложенный в доказательстве алгоритм линеен, т.е. число действий прямо пропорционально числу ребер.

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

Вход:эйлеров граф G(V,E), заданный матрицей смежности. Для простоты укажем, что Г[v]— множество вершин, смежных с вершиной v.

Выход:последовательность вершин эйлерова цикла.

S:=Ø {стек для хранения вершин}

select vV {произвольная вершина}

v→S {положить v в стек S}

while S≠Ø do

v←S; v→S {v — верхний элемент стека}

if Г[v]=Ø then

v←S;

yield v

else

select uГ[v] {взять первую вершину из списка смежности}

u→S {положить u в стек}

Г[v]:=Г[v]\{u}; Г[u]:=Г[u]\{v} {удалить ребро (v,u)}

end if

end while

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

Принцип действия этого алгоритма заключается в следующем. Начиная с произвольной вершины, строим путь, удаляя ребра и запоминая вершины в стеке, до тех пор пока множество смежности очередной вершины не окажется пустым, что означает, что путь удлинить нельзя. Заметим, что при этом мы с необходимостью придем в ту вершину, с которой начали. В противном случае это означало бы, что вершина v имеет нечетную степень, что невозможно по условию. Таким образом, из графа были удалены ребра цикла, а вершины цикла были сохранены в стеке S. Заметим, что при этом степени всех вершин остались четными. Далее вершина v выводится в качестве первой вершины эйлерова цикла, а процесс продолжается, начиная с вершины, стоящей на вершине стека.

Мне бы хотелось привести здесь еще один алгоритм построения эйлерова цикла в эйлеровом графе — это Алгоритм Флёри, он позволяет пронумеровать ребра исходного графа так, чтобы номер ребра указывал каким по счету это ребро войдет эйлеров цикл.

Алгоритм Флёри:

1. Начиная с любой вершины v присваиваем ребру vu номер 1. Вычеркиваем это ребро из списка ребер и переходим к вершине u.

2. Пусть w - вершина, в которую мы пришли в результате выполнения 1 шага алгоритма и k - номер, присвоенный очередному ребру на этом шаге. Выбираем произвольное ребро инцидентное вершине w, причем мост выбираем только в крайнем случае, если других возможностей выбора ребра не существует. Присваиваем ребру номер k+1 и вычеркиваем его. Процесс длится до тех пор, пока все ребра не вычеркнут.

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

Пример:

Приведем теперь строгое обоснование корректности алгоритма Флёри построения эйлерового цикла в данном эйлеровом графе.

Теорема 2. Пусть G(V,E) — эйлеров граф. Тогда следующая процедура всегда возможна и приводит к построению эйлерова цикла графа G(V,E).

Выходя из произвольной вершины, идем по ребрам графа произвольным образом, соблюдая при этом следующие правила:

1) Стираем ребра по мере их прохождения (вместе с изолированными вершинами, которые при этом образуются);

2) На каждом шаге идем по мосту только в том случае, когда нет других возможностей.

Доказательство.

Убедимся сначала, что указанная процедура может быть выполнена на каждом этапе. Пусть мы достигли некоторой вершины v, начав с вершины u, v ≠ u. Удалив ребра пути из v в u, видим, что оставшийся граф G1 связен и содержит ровно две нечетных вершины v и u. Согласно следствию #2 из теоремы 1 граф G1 имеет эйлеров путь P из v в u. Поскольку удаление первого ребра инцидентного u пути P либо не нарушает связности G1, либо происходит удаление вершины u и оставшийся граф G2 связен с двумя нечетными вершинами, то отсюда получаем, что описанное выше построение всегда возможно на каждом шаге. (Если v = u, то доказательство не меняется, если имеются ребра, инцидентные u). Покажем, что данная процедура приводит к эйлерову пути. Действительно, в G не может быть ребер, оставшихся не пройденными после использования последнего ребра, инцидентного u, поскольку в противном случае удаление ребра, смежного одному из оставшихся, привело бы к несвязному графу, что противоречит условию 2).

§4. Некоторые родственные задачи

Сразу же укажем ряд вопросов, связанных с тем, имеется ли в неориентированном графе эйлеров цикл. Например,

1) Каково наименьшее число цепей или циклов необходимое для того, чтобы каждое ребро графа G содержалось точно в одной цепи или в одном цикле? Очевидно, что если G имеет эйлеров цикл или эйлерову цепь, то ответом будет число один.

2) Ребрам графа G приписаны положительные веса. Требуется найти цикл, проходящий через каждое ребро графа G по крайней мере один раз и такой, что для него общий вес (а именно сумма величин njc(aj), где число nj показывает, сколько раз проходилось ребро aj, а c(aj) — вес ребра) минимален. Очевидно, что если G содержит эйлеров цикл, то любой такой цикл будет оптимальным, так как каждое ребро проходится по один раз и вес этого цикла равен тогда