Эйлеровы циклы
    Эйлеров цикл - это такой цикл, который проходит ровно один раз по каждому ребру.
   Связный неориентированный граф G содержит Эйлеров цикл тогда и только тогда, когда число вершин нечетной степени равно нулю.
   Не все графы имеют Эйлеровы циклы, но если Эйлеров цикл существует, то это означает, что, следуя вдоль этого цикла, можно нарисовать граф на бумаге, не отрывая от нее карандаша. Дан граф G, удовлетворяющий условию теоремы. Требуется найти Эйлеров цикл. Используется просмотр графа методом поиска в глубину, при этом ребра удаляются. Порядок просмотра (номера вершин) запоминается. При обнаружении вершины, из которой не выходят ребра, мы их удалили, ее номер записывается в стек, и просмотр продолжается от предыдущей вершины. Обнаружение вершин с нулевым числом ребер говорит о том, что найден цикл. Его можно удалить, четность вершин (количество выходящих ребер) при этом не изменится. Процесс продолжается до тех пор, пока есть ребра. В стеке после этого будут записаны номера вершин графа в порядке, соответствующем Эйлерову циклу.
Procedure Search (v: integer);
{*глобальные переменные*}
{*A - матрица смежности, Cv - стек*}
{* yk - указатель стека*}
var j: integer;
Begin
For j: =1 to N do if A [v, j] <>0 then begin
A[v, j]:=0; A [j, v]:=0; Search (j)
End;
Inc (yk);
Cv [yk]:=v;
end;

    Пример графа и содержимое стека Cv после работы процедуры Search.







    Если граф имеет цикл (не обязательно простой), содержащий все ребра графа по одному разу, то такой цикл называют эйлеровым циклом, а граф в свою очередь называют эйлеровым графом. Если граф имеет цепь (не обязательно простую), содержащую все ребра по одному разу, то такая цепь называется полуэйлеровым графом.
   Теорема 1. Связный граф является эйлеровым тогда и только тогда, когда каждая вершина имеет четную степень.
  Предположим, что Р является эйлеровым циклом в графе. Тогда при всяком прохождении цикла через любую вершину графа используется одно ребро для входа и одно ребро для выхода. Поскольку каждое ребро используется один раз, то каждая вершина должна иметь четную степень. Обратное утверждение доказываем индукцией по числу ребер в графе.
   Теорема 2. Связный граф G является полуэйлеровым тогда и только тогда, когда в нем существует точно две вершины нечетной степени. Аналогичное определение можно сделать для ориентированных графов. Ориентированный Эйлеров путь это ориентированный путь, содержащий каждую дугу точно один раз. Ориентированный граф называется эйлеровым, если в нем существует ориентированный Эйлеров путь.
   Теорема 3. Пусть G - Эйлеров граф. Тогда следующая процедура всегда возможна и приводит к построению эйлеровой цепи графа G.
   Выходя из произвольной вершины, идем по ребрам графа произвольным образом, соблюдая следующие правила:
1) стираем   ребра   по   мере   их   прохождения   (вместе   с изолированными вершинами, которые при этом образуются);
2) на каждом этапе идем по ребру, удаление которого нарушает связность, только в том случае, когда нет других возможностей.
   Убедимся сначала, что указанная процедура может быть  выполнена на каждом этапе. Пусть мы достигли некоторой вершины v, начав с вершины u, v=u. Удалив ребра пути из v в u, видим, что  оставшийся граф       связен и содержит ровно две нечетных вершины v и u. Согласно теореме 2 граф        имеет Эйлеров путь Р из v в u. Поскольку удаление первого ребра инцидентного и пути Р либо не нарушает связности      , либо происходит удаление вершины u и оставшийся граф    связен с двумя нечетными вершинами, то отсюда получаем, что описанное выше построение всегда возможно на каждом шаге. (Если v = u, то доказательство не меняется, если имеются ребра, инцидентные u). Покажем, что данная процедура приводит к Эйлерову пути. Действительно, в G не может быть ребер, оставшихся непройденными после использования последнего ребра, инцидентного и, поскольку в противном случае удаление ребра, смежному одному из оставшихся, привело бы к несвязному графу, что противоречит теореме 2).
   Вывод из теорем - если граф связан и нетривиален, то следующие утверждения эквивалентны:






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

    Вход: - Эйлеров граф G (V, Е), заданный списками смежности (Г[v] - список вершины, смежных с вершиной v).
     Выход: - записывается последовательность вершин эйлерова цикла.
          (формируем стек, в котором будут храниться вершины);
Select v V (формируется произвольная вершина);
v S (отправляем вершину v в стек S);
while S=     do
v:= top S (v - делаем верхним элементом стека)
if Г [v] =    then
v - S; yield v (выбираем очередную вершину эйлерова цикла)
else
select u    G Г[v] (берем первую вершину из списка смежности)
u - S (и помещаем и в стек)
Г[v]:=Г[v]\{u}; Г[u]:=Г[u]\{u} (затем удаляем ребро (у, и))
End if
End while.
   Принцип действия этого алгоритма заключается в следующем. Начав с произвольной вершины, строим путь, удаляя рёбра, и запоминаем вершины в стеке, до тех пор, пока множество смежности очередной вершины не окажется пустым, что означает, что путь удалить нельзя. Заметим, что при этом мы с необходимостью приведем в ту же вершину, с которой начали. В противном случае это означало бы, что вершина v имеет нечетную степень, что невозможно по условию. Таким образом, из графа были удалены рёбра цикла, а вершины цикла были сохранены в стеке S. Заметим, что при этом степени всех вершин остались чётными. Далее вершин v выводится в качестве первой вершины эйлерова цикла, а процесс продолжался с вершины, стоящей на вершине стека.