Эйлеров цикл — это эйлеров путь, являющийся циклом.
Эйлеров путь (эйлерова цепь) в графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу.
Полуэйлеров граф — граф, содержащий эйлеров путь (цепь).
В неориентированном графе
Эйлеров цикл существует тогда и только тогда, когда граф связный и в нём отсутствуют вершины нечётной степени.
Эйлеров путь в графе существует тогда и только тогда, когда граф связный и содержит не более чем две вершины нечётной степени. Эйлеров путь существует только тогда, когда количество вершин нечётной степени равно нулю или двум. Причём когда оно равно нулю, эйлеров путь вырождается в эйлеров цикл.
В ориентированном графе
Ориентированный граф содержит эйлеров цикл тогда и только тогда, когда он сильно-связан (из каждой вершины можно добраться в любую другую) и в каждую вершину входит столько же ребер, сколько из неё и выходит.
Поиск эйлерова цикла в графе
Будем рассматривать самый общий случай — случай неориентированного мультиграфа, возможно, с петлями.
procedure DFSE (v : longint); var i : longint; //Заводим счётчик для цикла begin for i:=1 to n do if g[v,i]>0 then //Ищем вершину к которой есть путь begin g[v,i]:=g[v,i]-1; //Удаляем g[i,v]:=g[v,i]; //Если граф ориентированный тогда эта строчка не нужна DFSE(i); //Пускаем этот алгоритм от следуещей вершины end; k:=k+1; //Увеличиваем количество пройденных вершин s[k]:=v; //Записываем вершину в массив S end;
Сложность полученного алгоритма — O(M), то есть линейная относительно количества рёбер М в данном графе.
Полная программа 1
Существует n вершин и m рёбер в ориентированном графе. Вводится m строк, в каждой по две вершины. Узнать, можно ли пройти по всем рёбрам по одному разу вернувшись в исходную вершину? Если можно, вывести путь.
var g : array [1..100,1..100] of longint; //Заводим матрицу смежности s,vh,vih : array [1..10100] of longint;//Массивы цикла, количества входов и выходов из вершин p : array [1..1000] of boolean; //Массив меток были ли мы здесь i,n,m,x,y,j,e,k : longint; //Счётчик цикла, количество вершин, рёбер , две переменные для ввода, счётчики циклов, длина цикла d : boolean; procedure DFSE (v : longint); var i : longint; //Заводим счётчик для цикла begin for i:=1 to n do if g[v,i]>0 then //Ищем вершину к которой есть путь begin g[v,i]:=g[v,i]-1; //Удаляем g[i,v]:=g[v,i]; //Если граф ориентированный тогда эта строчка не нужна DFSE(i); //Пускаем этот алгоритм от следуещей вершины end; k:=k+1; //Увеличиваем количество пройденных вершин s[k]:=v; //Записываем вершину в массив S end; procedure DFS (v : longint); var j : longint; //Заводим счётчик для цикла begin p[v]:=true; //Помечаем что мы здесь были for j:=1 to n do if (not(p[j]))and(g[v,j]>0) then DFS(j); //Ищем вершину, если мы тут не были и сюда можно пройти то идём сюда end; begin readln(n,m); //Считываем количество вершин и рёбер for i:=1 to m do begin readln(x,y); //Считываем данные ребра g[x,y]:=g[x,y]+1; //Заносим данное ребро в матрицу смежности end; i:=1; //Первая вершина - 1 j:=1;//Вторая вершина - 1 d:=true; //Пока думаем что граф эйлеров dfs(1); //Пускаем глубину while (i<=n)and(d) do //Пока идём по матрице смежности и граф эйлеров begin vh[j]:=vh[j]+g[i,j]; //Прибавляем количество вершин которые входят в j vih[i]:=vih[i]+g[i,j]; //Прибавляем количество вершин которые выходят из i d:=d and p[j];//Проверяем есть ли путь из i в j j:=j+1; //Увеличиваем j if j>n then //Если j вышло за пределы begin for e:=1 to n do p[e]:=false; //Думаем что никуда пути нет j:=1;//Мы снова в первом столбце матрицы i:=i+1; //Переходим в следующую строку DFS(i); //Пускаем глубину end; end; if d then for i:=1 to n do d:=d and (vh[i]=vih[i]); //Если граф ещё Эйлеров тогда идём по всем вершинам и думаем что граф элеров если мы ещё думаем что он эйлеров и в вершину входит столько же рёбер сколько выходит if not(d) then writeln('NO SOLUTION') else //Если граф не эйлеров тогда выводим NO SOLUTION begin //иначе k:=0; //Количество вершин в цикле - 0 DFSE(1); //Пускаем эйлеров цикл for i:=1 to k do write(s[i],' '); //Идём от 1 до длины цикла и выводим в какой вершине мы оказались end; end.
Полная программа 2
Существует n вершин и m рёбер в неориентированном графе. Вводится m строк, в каждой по две вершины. Узнать, можно ли пройти по всем рёбрам по одному разу вернувшись в исходную вершину? Если можно, вывести путь.
var g : array [1..100,1..100] of longint; //Заводим матрицу смежности s : array [1..10100] of longint;//Массивы цикла, количества входов и выходов из вершин i,n,m,x,y,j,k,vih : longint; //Счётчик цикла, количество вершин, рёбер , две переменные для ввода, счётчик цикла, длина цикла, количество выходящих вершин d : boolean; procedure DFSE (v : longint); var i : longint; //Заводим счётчик для цикла begin for i:=1 to n do if g[v,i]>0 then //Ищем вершину к которой есть путь begin g[v,i]:=g[v,i]-1; //Удаляем g[i,v]:=g[v,i]; //Если граф ориентированный тогда эта строчка не нужна DFSE(i); //Пускаем этот алгоритм от следуещей вершины end; k:=k+1; //Увеличиваем количество пройденных вершин s[k]:=v; //Записываем вершину в массив S end; begin readln(n,m); //Считываем количество вершин и рёбер for i:=1 to m do begin readln(x,y); //Считываем данные ребра g[x,y]:=g[x,y]+1; //Заносим данное ребро в матрицу смежности g[y,x]:=g[x,y]; //Заносим данное ребро в матрицу смежности end; i:=1; //Первая вершина - 1 j:=1;//Вторая вершина - 1 vih:=0; d:=true; //Пока думаем что граф эйлеров while (i<=n)and(d) do //Пока идём по матрице смежности и граф эйлеров begin vih:=vih+g[i,j]; j:=j+1; //Увеличиваем j if j>n then //Если j вышло за пределы begin d:=d and (vih mod 2=0) //Проверяем чётное ли количество выходящих вершин vih:=0; //Количество выходящих вершин присваеваем нулю. j:=1;//Мы снова в первом столбце матрицы i:=i+1; //Переходим в следующую строку end; end; if not(d) then writeln('NO SOLUTION') else //Если граф не эйлеров тогда выводим NO SOLUTION begin //иначе k:=0; //Количество вершин в цикле - 0 DFSE(1); //Пускаем эйлеров цикл for i:=1 to k do write(s[i],' '); //Идём от 1 до длины цикла и выводим в какой вершине мы оказались end; end.