Российско-Армянский (Славянский) государственный Университет

Факультет прикладной математики и информатики

Êурсовая работа

Òåìà:Нахождение эйлерова цикла в графе.

Êàôåäðà:Ñèñòåìíîå ïðîãðàììèðîâàíèå.

Èñïîëíèòåëü: ñòóäåíòêà III êóðñà Ãåâîðãÿí Ê.Ã.

Ðóêîâîäèòåëü: Егиазарян В.С.

Åðåâàí 2003ã.

Содержание.

Основные понятия………………………………………………………3

Поиск в ширину…………………………………………………………5

Поиск в глубину…………………………………………………………8

Эйлеров цикл……………………………………………………………11

Литература................................................................................................16

Основние понятия.

Ориентированный граф (directed graph) определяется как пара (V,E), где V-конечное множество , а E-бинарное отношение на V, т.е.подмножество множества V´V. Ориентированный граф иногда для краткости называют орграфом (digraph).Множество V называют множеством вершин графа (vartex set);его элемент называют вершиной графа(vartex) .Множество E называят множеством ребер (edge set) графа; его элементы называют ребрами .

В неориентированном (underected) графе G=(V,E) множество ребер E состоит из неупорядоченных (unordered) пар вершин : парами являются множества {u,v}, где u,vÎ V и u ¹v. Будем обозначть неориентированное ребро как (u,v) вместо {u,v}; при этом для неориентированного графа (u,v) и (v,u) обозначают одно и то же ребро.

Про ребро (u,v) орграфа говорят, что оно выходит из (incident from, leaves) вершины u и входит (incident to, enters) в вершину v. Про ребро (u,v) неорграфа говорят, что оно инцидентна вершинам (incident on vertics) u и v.

Если в графе G имеется ребро (u,v), то говорят, что вершина v смежна с вершиной u (is adjacent to u). Для ориентированных графов отношение смежности является симметричным, но для ориентированных графов это не обязательно.

Степенью (degree) вершины в неориентированном графе называется число инцидентных ей ребер.Для ориентированного графа различают исходящую степень(out degree), определяемую как число выходящих из нее ребер , и входящую степень(in-degree), определяемую как число входящих в нее ребер. Сумма исходящей и входящей степеней называют степенью вершины.

Путь длины k (path of length k) из вершины u в вершину v определяется как последовательность вершин (), в которой =u, =v и (,)ÎE для всех i=1,2,…,k.Таким образом, путь длины k состоит из k ребер.Этот путь содержит вершины и ребра (,),(,),…,(,). Вершину называют началом пути , вершину - его концом; говорят, что путь ведет из в . Если для данных вершин u и существует путь р из u в , то говорят, что вершина достижима из u по пути р .

Путь называется простым, если все вершины в нем различны.

Циклом в орграфе называется путь, в котором начальная вершина совпадает с конечной и который содержит хотя жы одно ребро. Цикл называется простым , если в нем нет одинаковых вершин.

В неориентированном графе путь <> называется (простым) циклом , если k³3, = и все вершины различны. Неориентированный граф называется связным, если для любой пары вершин существует путь из одной в другую.Для неориентированного графа отношение “быть достижимым из” является отношением эквивалентности на множестве вершин. Классы еквивалвнтности называются связными компонентами графа. Неориентированный граф связан тогда и только тогда, когда он состоит из единственной связной компоненты.

Ориентированный граф называется сильно связным , если из любой его вершины достижима любая другая. Любой ориентированный граф можно разбить на сильно связные компоненты, которые определяются как классы эквивалвнтности отношения “u достижимо из v и v достижимо из u”.Ориентированный граф сильно связан тогда и только тогда, когда состоит из единственной сильно связной компоненты.

Граф =(,) называют подграфом графа G=(V,E), если ÍE , ÍV.

Выбор соответствующей структуры данных для представления графа в памяти компьютера имеет принципиальное значение при разработке эффективных алгоритмов.

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

Матрица смежности –это двумерный массив размерности (количество_вершин)´(количество_вершин)

A[i,j]= 1, если вершина с номером i смежан с вершиной с номером j;

A[i,j]=0, в противном случае.

Например:

матрица смежности для данного графа

	a	b	c	d
a	0	1	1	0
b	1	0	1	0
c	1	1	0	1
d	0	0	1	0

a . . b

c . . d

Поиск в ширину.

Поиск в ширину (breadth-first search) –один из базисных алгоритмов, составляющий основу многих других. Например, алгоритм Дейкстры поиска кратчайших путей из одной вершины и алгоритм Прима поиска минимального покрывающего дерева могут рассматриваться как обобщение поиска в ширину.

Пусть фиксирована начальная вершина s . Алгоритм поиска в ширину перечисляет все достижимые из s (если идет по ребрам) вершины в порядке возрастания расстояния от s. Расстоянием считается длина (число ребер) кратчайшего пути. В процессе поиска из графа выделяется часть, называемая “деревом поиска в ширину” с корнем s.Она содержит все достижимые из s вершины. Для каждой из них путь из корня в дереве поиска будет одним из кратчайших путей (из начальной вершины) в графе. Алгоритм применим и к ориентированным и к неориентированным графам.

Название обúясняется тем, что в процессе поиска мы идем вширь, а не вглубь (сначала просматриваем все соседние вершины, затем соседей соседей и т.д.).

Для наглядности будем считать, что в процессе работы алгоритма вершины графа могут быть белыми, серыми и черными. Б начале они все белые, но в ходе работы алгоритма белая вершина может стать серой, а серая – черной (но не наоборот). Повстречав новую вершину, алгоритм поиска красит ее, так что окрашенные вершины(серые или черные) – это в точности те, которые уже обнаружены. Различие между серыми и черными вершинами используется алгоритмом для управления порядком обхода : серые вершины образуют “линию фронта”, а черные – “тыл”. Более точно, поддерживается такое свойство: если (u,v) Î E и u черная, то v- серая или черная вершина. Таким образом, только серуе вершины могут иметь смежные необнаруженные вершины.

Вначале дерево поиска состоит только из корня- начальной вершины s. Как только алгоритм обнаруживает новую вершину v, смежную с ранее найденной вершиной u, вешина v (вместе с ребром (u,v)) добавляется к дереву поиска, становясь ребенком вершины u, а u становится родителем v. Каждая вершина обнаруживается только один раз, так что двух родителей у нее быть не может. Понятия предка и потомка определяются как обычно (потомки-это дети, дети детей, и т.д.). Двигаясь от вершины к корню, мы проходим всех ее предков.

Приведенная ниже процедура использует представление графа матрицей смежных вершин. Для каждой вершины u графа дополнительно хранится ее цяет color[u] и ее предшественник pr[u]. Кроме того , расстояние от s до u записывается в поле d[u]. Процедура использует также ояередь Q (FIFO) для хранения множества серых вершин.

#include "iostream.h"

#include "fstream.h"

void Del(int *,int);

int main()

{

int m;//íîìåð îáðàáàòûâàåìîé âåðøèíû

int N;//êîëè÷åñòâî âåðøèí

int ** mat;//ìàòðèöà ñìåæíîñòè

ifstream fin("input.txt");

ofstream fout ("output.txt");

fin>>N;

mat=new int *[N];

for(int i=0;i<N;i++)

mat[i]=new int [N];

for(int j=0;j<N;j++)

for(int o=0;o<N;o++)

fin>>mat[j][o];//ïðî÷ëè èç ôàéëà

int *color;//öâåò 0-áåëûé, 1-ñåðûé,2-÷åðíûé

int * d;//ðàññòîÿíèå

int * pr;//ïðåäøåñòâåííèê

int *Q;//î÷åðåäü äëÿ ñìåæíûõ âåðøèí

color=new int [N];

d=new int [N];

pr=new int [N];

Q=new int [N];

for(int s=0;s<N;s++)

{ color[s]=0;

d[s]= 0;

pr[s]=0;

}

Q[0]=0;

int count=1;// ñ÷åò÷èê äëÿ Q

fout<<"Ocherednost passmatrivanija vershin:"<<'\n';

while(count!=0)

{

m=Q[0];

fout<<m<<" -Nomer vershini"<<'\n';

for(int k=1;k<N;k++)

{

if(mat[m][k]==1)// åñëè k ñìåæíà ñ m

{if(color[k]==0)

{ color[k]=1;

d[k]=d[m]+1;

pr[k]=m;

Q[count]=k;

count++;}}

}

Del(Q,count);

count--;

color[m]=2;

}

for(int h=0;h<N;h++)

{fout<< "Ver_Num "<<h<<" Wes "<<d[h]<<'\n';}

delete [] color;

delete [] d;

delete [] pr;

delete [] Q;

for(int f=0;f<N;f++)

delete [] mat[f];

delete mat;

return 0;

}

void Del(int *A, int a)

{

for(int k=0;k<a;k++)

A[k]=A[k+1];

A[a-1]=-1;

return;

}

Пример:

input.txt

5

0 1 0 0 1

1 0 1 0 1

0 1 0 1 1

0 0 1 0 1

1 1 1 1 0

output.txt

Поиск в глубину.

Стратегия поиска в глубину такова: идти “вглубь”, пока это возможно (есть непройденные исходящие ребра), и возвращаться и искать другой путь, когда такох ребер нет. Так делается пока не обнаружены все вершины , достижимые из исходной. (Если после этого остаются необнаруженные вершины , можно выбрать одну из них и повторить этот процесс, и делать так до тех пор, пока мы не обнаружим все вершины графа.)

Как и при поиске в ширину, обнаружив (впервые) вершину v, смежную с u, мы отмечаем это событие, помещая в поле pr[u] значение u.Получается дерево или несколько деревьев, если поиск повторяется из нескольких вершин. Говоря дальше о поиске в глубину, всегда будем предполагать , что так и делается (поиск повторяется). Получаем подграф предшествования, определенный так: , где

Подграф предшествовамия представляет собой лес поиска в глубину, состоящий из деревьев поиска в глубину.

Алгоритм поиска в глубину также использует цвета вершин. Каждая из вершин вначале белая. Будучи обнаруженной, она становися серой;она станет черной , когда будет полностью обработана, т.е. когда список смежных с ней вершин будет просмотрен. Каждая вершина попадает ровно в одно деревопоиска в глубину, так что эти деревья не пересекаются.

Помимо этого, поиск в глубину ставит на вершинах метки времени. Каждая вершина имеет две метки: в d[u] записано, когда эта вершина была обнаружена (и сделана серой), а в f[u] – когда была закончена обработка списка смежных вершин (и v стал черной).

Эти метки времвни используются во многих алготимах на графах и полезны для анализа свойств поиска в глубину.

В приводимой далее процедуре DFS( Depth-First Search- поиска в глубину) метки времени d[u] и f[u] являются целыми числами от 1 до 2|V| ; для любой вершины выполнено неравенство d[u]< f[u].

Вершина u будет белой до момента d[u], серой между d[u] и f[u] и черной после f[u].

Исходный граф может быть ориентированным или неориентированным. Переменная time – глобальная переменная текущего времени, используемого для пометок.

#include "iostream.h"

#include "fstream.h"

void DFS_Visit(int ** ,int *,int*,int*,int*,int);//ìàòð,öâåò,íà÷àëîîáíàð,êîíåöîáðàáîòêè,âåðøèíà

int time;

int N;//êîëè÷åñòâî âåðøèí

int main()

{

time=0;

ifstream fin ("input.txt");

ofstream fout("output.txt");

fin>>N;

int ** mat;//ìàòðèöà ñìåæíîñòè

mat=new int *[N];

for(int i=0;i<N;i++)

mat[i]=new int [N];

for(int j=0;j<N;j++)

for(int o=0;o<N;o++)

fin>>mat[j][o];//ïðî÷ëè èç ôàéëà

int *color;//öâåò 0-áåëûé, 1-ñåðûé,2-÷åðíûé

int * d;//âðåìÿ îáíàðóæåíèÿ

int * pr;//ïðåäøåñòâåííèê

int * f;//âðåìÿ îêîí÷àíèÿ îáðàáîòêè

color=new int [N];

d=new int [N];

pr=new int [N];

f=new int [N];

for(int s=0;s<N;s++)

{ color[s]=0;

pr[s]=-1;

}

for(int k=0;k<N;k++)

if(color[k]==0)

DFS_Visit(mat,color,d,f,pr,k);

for(int r=0;r<N;r++)

fout<<"Num_Versh- "<<r<<" Predshestvennik- "<<pr[r]<<" "<<d[r]<<"-nachalo; konec- "<<f[r]<<'\n';

delete [] d;

delete [] pr;

delete [] f;

delete [] color;

for(int u=0;u<N;u++)

delete [] mat[u];

delete mat;

return 0;

}

void DFS_Visit(int ** A,int * col,int * D,int *F,int * Pr,int u)

{

col[u]=1;

time=time+1;

D[u]=time;

for(int p=0;p<N;p++)

{

if(A[u][p]==1)

{

if(col[p]==0)

{

Pr[p]=u;

DFS_Visit(A,col,D,F,Pr,p);

}

}

}

col[u]=2;

time=time+1;

F[u]=time;

}

Пример:

6

0 1 0 1 0 0

0 0 0 0 1 0

0 0 0 0 1 1

0 1 0 0 0 0

0 0 0 1 0 0

0 0 0 0 0 1

input.txt

Output.txt

Num_Versh- 0 Predshestvennik- -1 1-nachalo; konec- 8

Num_Versh- 1 Predshestvennik- 0 2-nachalo; konec- 7

Num_Versh- 2 Predshestvennik- -1 9-nachalo; konec- 12

Num_Versh- 3 Predshestvennik- 4 4-nachalo; konec- 5

Num_Versh- 4 Predshestvennik- 1 3-nachalo; konec- 6

Num_Versh- 5 Predshestvennik- 2 10-nachalo; konec- 11

Эйлеров цикл.

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

Задача возникла из предложенной Эйлеру головоломки, получившей название "проблема кенигсбергских мостов". Река Прегель, протекающая через Калининград (прежде город назывался Кенигсбергом), омывает два острова. Берега реки связаны с островами так,

как это показано на рисунке.

В головоломке требовалось найти маршрут, проходящий по всем участкам суши таким образом, чтобы каждый из мостов был пройден ровно один раз, а начальный и конечный пункты маршрута совпадали.

Дадим теперь строгое определение эйлерову циклу и эйлерову графу. Если граф имеет цикл (не обязательно простой), содержащий все ребра графа по одному разу, то такой цикл называется эйлеровым циклом, а граф называется эйлеровым графом.

Ясно, что эйлеров цикл содержит не только все ребра по одному разу, но и все вершины графа (возможно, по несколько раз). Очевидно также, что эйлеровым может быть только связный граф.

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

Критерий существования эйлерова цикла:

Что необходимо, чтобы в графе существовал эйлеров цикл? Во-первых, граф должен быть связанным: для любых двух вершин должен существовать путь, их соединяющий. Во-вторых, для неориентированных графов число ребер в каждой вершине должно быть четным. На самом деле этого оказывается достаточно.

Теорема . Чтобы в связанном неориентированном графе G существовал эйлеров цикл, необходимо и достаточно, чтобы число вершин нечетной степени равнялась нулю.

Доказательство.

Необходимость. Любой эйлеров цикл должен прийти в вершину по одному ребру и покинуть ее по другому, так как любое ребро должно использоваться ровно один раз. Поэтому, если G содержит эйлеров цикл, то степени вершин должны быть четными.

Достаточность. Пусть G — связный неориентированный граф, все вершины которого имеют четную степень. Начнем путь из некоторой произвольной вершины x₀ и пойдем по некоторому ранее не использованному ребру к следующей вершине, и так до тех пор, пока не вернемся в вершину x₀ и не замкнем цикл. Если все ребра окажутся использованными, то нужный эйлеров цикл построен. Если же некоторые ребра не использованы, то пусть Ф — только что построенный цикл. Так как граф G связен, то цикл Ф должен проходить через некоторую вершину, скажем x_i, являющуюся конечной вершиной какого-либо до сих пор не использованного ребра. Если удалить все ребра, принадлежащие Ф, то в оставшемся графе все вершины по-прежнему будут иметь четную степень, так как в цикле Ф должно быть четное число ребер (0 является четным числом), инцидентных каждой вершине.

Начиная теперь с x_i, получаем цикл Ф’, начинающийся и оканчивающийся в x_i. Если все оставшиеся ранее ребра использованы для цикла Ф’, то процесс окончен. Нужный эйлеров цикл будет образован частью цикла Ф от вершины x₀ до x_i, затем циклом Ф’ и, наконец, частью цикла Ф от вершины x_i до x₀. Если же все еще остались неиспользованные ребра, то объединение построенных выше циклов Ф и Ф’ дает новый цикл Ф. Мы снова можем найти вершину x_j, принадлежащую циклу и являющуюся концевой вершиной некоторого неиспользованного ребра. Затем мы можем приступить к построению нового цикла Ф’, начинавшегося в x_j, и так до тех пор, пока не будут использованы все ребра и не будет получен таким образом эйлеров цикл Ф. Это доказывает теорему.Хотя доказательство проведено для неориентированных графов, оно сразу переносится на ориентированные, только требование четности заменяется теперь на такое: число входящих в каждую вершину ребер должно быть равно числу выходящих.

Алгоритм построения эйлерова цикла заключается в следующем. Начиная с произвольной вершины (для конкретности, с первой вершины), строим путь, ыдаляя ребра и запоминая вершины в стеке, до тех пор, пока множество смежности очередной вершины не окажется пустым, что означает, что путь удлинить нельзя. При этом с необходимостью придем в ту вершину, с которой начали. В противном случае это означало бы, что вершина имеет нечетную степень, что не возможно по условию. Таким образом, из графа были удалены ребра цикла, а вершины цикла были сохранены в стеке. При этом степени всех вершин остались четными. Далее эта вершина выводится в качестве первой вершины эйлерова цикла, а процесс продолжается , начиная с вершины, стоящей на вершине стека.

Header File

#include "iostream.h"

# include "stdlib.h"

struct node

{ int info;

node * link;

};

class Stack

{

private:

node * first;

public:

Stack();

~Stack();

bool Empty();

void Pop(int&);

void Push(int);

};

Stack ::Stack()

{first= NULL;}

Stack::~Stack()

{node *p=first, *q;

while(p)

{ q=p;

p=p->link;

delete q;

}

}

bool Stack::Empty()

{ if(first==NULL)

return true;

else

return false;

}

void Stack::Pop(int &k)

{ if(Empty()==true)

{ cout<<"ErrorP"<<endl;

exit(1);

}

else

{ node * p=first;

k=first->info;

first=first->link;

delete p;

return;

}

}

void Stack::Push(int k)

{node * q;

q=new node;

if(q)

{ q->info=k;

q->link=first;

first=q;

return;

}

else

{ cout<<"Erroe";

exit(1);

}

}

Source File

#include "iostream.h"

#include "fstream.h"

# include "stk.h"

int main()

{

Stack S;

int d;//äëÿ ïîäñ÷åòà ñòåðåíåé âåðøèí

int m;//òåêóùàÿ âåðøèíà

int sum;// äëÿ ïîäñ÷åòà ñìåæíûõ âåðøèí

int N;//êîëè÷åñòâî âåðøèí

int ** mat;//ìàòðèöà ñìåæíîñòè

ifstream fin("input.txt");

ofstream fout ("output.txt");

fin>>N;

mat=new int *[N];

for(int i=0;i<N;i++)

mat[i]=new int [N];

for(int j=0;j<N;j++)

for(int o=0;o<N;o++)

fin>>mat[j][o];

for(int g=0;g<N;g++)// ïðîâåðÿåìá åñòü ëè ýéëåðîâ öèêë

{d=0;

for(int h=0;h<N;h++)

d=d+mat[g][h];

if(d%2!=0)

{fout<<"Eulerov cikla net"<<'\n';

return 0;}

}

S.Push(0); // åñòü öèêë, íàéäåì åãî

while(!S.Empty())

{ sum=0;

S.Pop(m);

S.Push(m);

for(int t=0;t<N;t++)

sum=sum +mat[m][t];

if(sum==0)

{ S.Pop(m);

fout<<m<<" ";

}

else

{ for(int r=0;r<N;r++)

if(mat[m][r]==1)

{ S.Push(r);

mat[m][r]=0;

mat[r][m]=0;

break;

}

}

}

for(int u=0;u<N;u++)

delete [] mat[u];

delete mat;

return 0;

}

Пример:

input.txt

0

6

1

4

3

2

1

0

7

0 1 0 0 0 0 1

1 0 1 0 1 0 1

0 1 0 1 0 0 0

0 0 1 0 1 0 0

0 1 0 1 0 1 1

0 0 0 0 1 0 1

1 1 0 0 1 1 0

После 7-ого шага стек: , потом 0 выводится.

6

5

4

6

1

4

3

2

1

0

output.txt

0 6 5 4 6 1 4 3 2 1 0

После 10-ого шага стек: , и все остальные

поочередно выводятся.

Литература.

1. Кормен, Лейзерсон “Алгоритмы, построение и анализ”.

2. С.Окулов “Программирование в алгоритмах”.

3. www.codenet.ru

4. www.algolist.ru