Эйлеров граф
petuhovskiy 05 янв 2012
Эйлеров граф — граф, содержащий эйлеров цикл.
Эйлеров цикл — это эйлеров путь, являющийся циклом.
Эйлеров путь (эйлерова цепь) в графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу.
Полуэйлеров граф — граф, содержащий эйлеров путь (цепь).
В неориентированном графе
Эйлеров цикл существует тогда и только тогда, когда граф связный и в нём отсутствуют вершины нечётной степени.
Эйлеров путь в графе существует тогда и только тогда, когда граф связный и содержит не более чем две вершины нечётной степени. Эйлеров путь существует только тогда, когда количество вершин нечётной степени равно нулю или двум. Причём когда оно равно нулю, эйлеров путь вырождается в эйлеров цикл.
В ориентированном графе
Ориентированный граф содержит эйлеров цикл тогда и только тогда, когда он сильно-связан (из каждой вершины можно добраться в любую другую) и в каждую вершину входит столько же ребер, сколько из неё и выходит.
Поиск эйлерова цикла в графе
Будем рассматривать самый общий случай — случай неориентированного мультиграфа, возможно, с петлями.
Сложность полученного алгоритма — O(M), то есть линейная относительно количества рёбер М в данном графе.
Полная программа 1
Существует n вершин и m рёбер в ориентированном графе. Вводится m строк, в каждой по две вершины. Узнать, можно ли пройти по всем рёбрам по одному разу вернувшись в исходную вершину? Если можно, вывести путь.
Полная программа 2
Существует n вершин и m рёбер в неориентированном графе. Вводится m строк, в каждой по две вершины. Узнать, можно ли пройти по всем рёбрам по одному разу вернувшись в исходную вершину? Если можно, вывести путь.
Эйлеров цикл — это эйлеров путь, являющийся циклом.
Эйлеров путь (эйлерова цепь) в графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу.
Полуэйлеров граф — граф, содержащий эйлеров путь (цепь).
В неориентированном графе
Эйлеров цикл существует тогда и только тогда, когда граф связный и в нём отсутствуют вершины нечётной степени.
Эйлеров путь в графе существует тогда и только тогда, когда граф связный и содержит не более чем две вершины нечётной степени. Эйлеров путь существует только тогда, когда количество вершин нечётной степени равно нулю или двум. Причём когда оно равно нулю, эйлеров путь вырождается в эйлеров цикл.
В ориентированном графе
Ориентированный граф содержит эйлеров цикл тогда и только тогда, когда он сильно-связан (из каждой вершины можно добраться в любую другую) и в каждую вершину входит столько же ребер, сколько из неё и выходит.
Поиск эйлерова цикла в графе
Будем рассматривать самый общий случай — случай неориентированного мультиграфа, возможно, с петлями.
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.
LVP 26 янв 2020
Автор программы - учащийся 7 класса Гимназии №8 Рубиш Артур
#include <bits/stdc++.h> using namespace std; const int N = 1000; int g[N][N], n; vector < int > t; bool p[N]; void DFS(int v) { p[v] = false; for (int j = 0; j < n; j++) if (p[j] == true && g[v][j] >= 1) DFS(j); } void DFS_E(int v) { for (int j = 0; j < n; j++) if (g[v][j] > 0) { g[v][j]--; g[j][v]--; DFS_E(j); } t.push_back(v); } int main() { setlocale(LC_ALL,"RUS"); cout << "Программа находит в программе эйлеров путь или эйлеров цикл." << endl; int m; cin >> n >> m; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) g[i][j] = 0; for (int i = 0; i < m; i++) { int x, y; cin >> x >> y; x--; y--; g[x][y]++; g[y][x]++; } for (int i = 0; i < n; i++) p[i] = true; int k = 0; for (int i = 0; i < n; i++) if (p[i] == true) { cout << i << endl; DFS(i); k++; } cout << k << endl; if (k > 1) cout << "Что есть в этом графе:ничего,граф-то не связный."; else { cout <<"Что есть в этом графе:"; int z = 0; for (int i = 0; i < n; i++) { int lol = 0; for (int j = 0; j < n; j++) if (g[i][j] > 0 && i != j) lol += g[i][j]; if (lol % 2 == 1) z++; } if (z == 0) { cout << "эйлеров цикл." << endl << "Тут "; DFS_E(0); cout <<t.size() + 1 <<" элементов, и вот они:" << endl; for (int i = 0; i < t.size(); i++) cout << t[i] + 1 << ' '; } else if (z == 2) { cout << "эйлеров путь." << endl << "Тут "; int z1 = 0; for (int i = 0; i < n; i++) { int lol = 0; for (int j = 0; j < n; j++) if (g[i][j] > 0 && i != j) lol += g[i][j]; if (lol % 2 == 1) z++; { g[n][i] = 1; g[i][n] = 1; z1 = i; } } DFS_E(z1); cout << t.size() << " элементов, и вот они:" << endl; for (int i = 0; i < t.size(); i++) cout << t[i] + 1 << ' '; } else cout << "ничего: ни эйлерова цикла, ни эйлерова пути."; } return 0; } //Код для поиска эйлерова пути и эйлерова цикла при любом графе.