В заданном графе необходимо определить, существует ли цикл, проходящий по каждому ребру графа ровно один раз. Задача № 13 на графы (см. "Сборник задач по графам").
Немного теории:
Связный ориентированный граф содержит Эйлеров цикл тогда и только тогда, когда для каждой вершины графа её полустепень захода равна её полустепени исхода, то есть в вершину входит столько же ребер, сколько из нее выходит.
Алгоритм:
1)Считываем количество ребер и вершин.
2)Заполняем матрицу смежности.
3)Описываем процедуру, которая занимается поиском Эйлерового цикла:
а)создаем матрицу inout, в которую будем записывать, сколько ребер входит и выходит из данной вершины.
номер столбца -- вершина
0-я строка -- количество входных ребер
1-я строка -- количество выходных ребер
б)проходим по матрице смежности и заполняем матрицу inout.
в)проходим по матрице inout и сравниваем первую и вторую строку в каждом столбце. Если найдется хотя бы одно несовпадение, то Эйлерового цикла нет.
4)По результатам работы процедуры делаем вывод о существовании цикла в данном графе.
#include <stdafx.h>
#include <conio.h>
int matrica_smeznosti[ 50 ][ 50 ];
int top[ 50 ];
int inout[ 50 ][ 2 ];
int poisk_cikla( int size )
{
int count_1, count_2;
int id = 0;
for( count_1 = 0; count_1 < size; count_1++ ) //проходим по всей матрице
{ //и считаем, сколько ребер
for( count_2 = 0; count_2 < size; count_2++ ) //входят и выходят из каждой
{ //вершины
if( matrica_smeznosti[ count_1 ][ count_2 ] == 1 )
{
inout[ count_1 ][ 0 ] += 1; //то что получили заносим в
} //матрицу inout, где номер
if( matrica_smeznosti[ count_2 ][ count_1 ] == 1) //слолбца совпадает с номером
{ //вершины
inout[ count_1 ][ 1 ] += 1;
}
}
}
for( count_1 = 0; count_1 < size; count_1++ ) //проходим по матрице inout
{ //и сравниваем числа в каждом
if( inout[ count_1 ][ 0 ] != inout[ count_1 ][ 1 ] ) //столбце, если найдется
{ //хотя бы одно несовпадение
id += 1; //то Эйлерового цикла нет
}
}
if(id == 0) return 0;
else return 1;
}
int main()
{
int versini, rebra;
int count_1, count_2, i, j;
printf( "VVedite kol-vo versin i reber v grafe\n" );
scanf( "%d %d", &versini, &rebra );
printf( "Vvodite rebra\n" );
for( i = 0; i < rebra; i++ ) //считываем колличество ребер
{
scanf( "%d %d", &count_1, &count_2 ); //считываем ребра
matrica_smeznosti[ count_1 ][ count_2 ] = 1;
}
if( poisk_cikla( versini ) == 0 ) //ищем Эйлеров путь в графе
{
printf( "Ailerov cikl est'\n" );
}
else
{
printf( "Cikla net\n" );
}
getch();
return 0;
}
Ключевые слова:
граф, эйлеров цикл, ребра графа
