0
Эйлеров цикл — это эйлеров путь, являющийся циклом.
Эйлеров путь (эйлерова цепь) в графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу.
Полуэйлеров граф — граф, содержащий эйлеров путь (цепь).
В неориентированном графе
Эйлеров цикл существует тогда и только тогда, когда граф связный и в нём отсутствуют вершины нечётной степени.
Эйлеров путь в графе существует тогда и только тогда, когда граф связный и содержит не более чем две вершины нечётной степени. Эйлеров путь существует только тогда, когда количество вершин нечётной степени равно нулю или двум. Причём когда оно равно нулю, эйлеров путь вырождается в эйлеров цикл.
В ориентированном графе
Ориентированный граф содержит эйлеров цикл тогда и только тогда, когда он сильно-связан (из каждой вершины можно добраться в любую другую) и в каждую вершину входит столько же ребер, сколько из неё и выходит.
Поиск эйлерова цикла в графе
Будем рассматривать самый общий случай — случай неориентированного мультиграфа, возможно, с петлями.
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.
