Перейти к содержимому


- - - - -

Эйлеров граф

граф путь

В теме одно сообщение

#1 petuhovskiy

    Пользователь

  • Пользователи
  • PipPip
  • 15 сообщений
  • ГородВитебск

Отправлено 05 января 2012 - 16:06

Эйлеров граф — граф, содержащий эйлеров цикл.
Эйлеров цикл — это эйлеров путь, являющийся циклом.
Эйлеров путь (эйлерова цепь) в графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу.
Полуэйлеров граф — граф, содержащий эйлеров путь (цепь).
В неориентированном графе

Эйлеров цикл существует тогда и только тогда, когда граф связный и в нём отсутствуют вершины нечётной степени.
Эйлеров путь в графе существует тогда и только тогда, когда граф связный и содержит не более чем две вершины нечётной степени. Эйлеров путь существует только тогда, когда количество вершин нечётной степени равно нулю или двум. Причём когда оно равно нулю, эйлеров путь вырождается в эйлеров цикл.

В ориентированном графе

Ориентированный граф содержит эйлеров цикл тогда и только тогда, когда он сильно-связан (из каждой вершины можно добраться в любую другую) и в каждую вершину входит столько же ребер, сколько из неё и выходит.
Поиск эйлерова цикла в графе

Будем рассматривать самый общий случай — случай неориентированного мультиграфа, возможно, с петлями.
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.

Yo

#2 LVP

    Продвинутый пользователь

  • Администраторы
  • 187 сообщений
  • ГородВитебск

Отправлено 26 января 2020 - 13:57

Автор программы - учащийся 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;
}
//Код для поиска эйлерова пути и эйлерова цикла при любом графе.

Виктория Павловна





Количество пользователей, читающих эту тему: 1

0 пользователей, 1 гостей, 0 анононимных