Warning: Illegal string offset 'html' in /var/www/lvp37/data/www/lvp37.ru/cache/skin_cache/cacheid_1/skin_topic.php on line 909
Эйлеров граф - олимпиадники-информатики

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


- - - - -

Эйлеров граф

граф путь

В этой теме нет ответов

#1 petuhovskiy

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

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

Отправлено 05 January 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





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

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