МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ НЕФТЕГАЗОВЫЙ УНИВЕРСИТЕТ»

КАФЕДРА ИНФОРМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

КУРСОВАЯ РАБОТА

по дисциплине «Дискретная математика» Тема: «Построить гамильтонову цепь в графе, используя рекурсивный алгоритм генерации всех перестановок вершин в антилексикографическом порядке»

Выполнил:

студент группы АСОИУ-07-1

Проверила:

Тюмень 2008

Содержание

Введение
Задание на курсовую работу по дисциплине «Дискретная математика».

Студент группы АСОИУ

Специальность «Автоматизированные системы обработки информации и управления»

Тема: «Построить гамильтонову цепь в графе, используя рекурсивный алгоритм генерации всех перестановок вершин в антилексикографическом порядке.
Условие задачи:

1.Построение гамильтоновой цепи графе используя алгоритм генерации всех перестановок вершин.

2. Написать программу, выполняющую следующие действия:

- ввод с клавиатуры данных в матрицу смежности;

- вывод на экран графа;

- нахождение в полученном графе гамильтоновой цепи.

1. Постановка задачи

1. Построение гамильтоновой цепи графе используя алгоритм генерации всех перестановок вершин.

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

2. Рекурсивный алгоритм генерации всех перестановок вершин.
Алгоритм генерирования перестановок в антилексикографическом порядке сформулировать удобнее. Заметим, что последовательность перестановок множества {1,2,…, n} в этом случае имеет следующие свойства, вытекающие непосредственно из определения:

1. 
   в первой перестановке элементы идут в растущей последовательности, в последней – в убывающей другими словами, последняя перестановка – обращение первой,
   
2. 
   последовательность всех перестановок можно разделить на n блоков длины (n-1), соответствующих убывающим значениям элемента в последней позиции. Первые n-1 позиций блока, содержащего элемент р в последней позиции, определяют последовательность перестановок множества {1,2,…, n}\{р} в антилексикографическом порядке.
   

1.2 Назначение и область применения

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

2. Описание алгоритма решения задачи

2.1 Построение гамильтоновой цепи графе

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

2.2 Алгоритм генерации всех перестановок вершин в антилексикографическом порядке

Антилексикографический порядок (обозначим  ) определяется следующим образом:

x1,x2,…xn < y1,y2,…,y n  существует такое kn, что xk  yk и xp = yp для каждого p  k..

Для примера приведем перестановки множества X = {1,2,3} в антилексикографическом порядке: 123, 213, 132, 312, 231, 321.

Алгоритм генерирования перестановок в антилексикографическом порядке сформулировать удобнее. Заметим, что последовательность перестановок множества {1,2,…, n} в этом случае имеет следующие свойства, вытекающие непосредственно из определения:

3. 
   в первой перестановке элементы идут в растущей последовательности, в последней – в убывающей другими словами, последняя перестановка – обращение первой,
   
4. 
   последовательность всех перестановок можно разделить на n блоков длины (n-1), соответствующих убывающим значениям элемента в последней позиции. Первые n-1 позиций блока, содержащего элемент р в последней позиции, определяют последовательность перестановок множества {1,2,…, n}\{р} в антилексикографическом порядке.
   

Сгенерируем в антилексикографическом порядке все перестановки для n=4, получим

1	2	3	4		1	2	4	3		1	3	4	2		2	3	4	1
2	1	3	4		2	1	4	3		3	1	4	2		3	2	4	1
1	3	2	4		1	4	2	3		1	4	3	2		4	2	3	1
3	1	2	4		4	1	2	3		4	1	3	2		2	4	3	1
2	3	1	4		2	4	1	3		3	4	1	2		3	4	2	1
3	2	1	4		4	2	1	3		4	3	1	2		4	3	2	1

2.3 Описание программы


Данная программа написана на языке программирования Borland C++ Builder Enterprise v6.0.
Состоит программа из двух форм. На главной форме задается сам граф. Его можно задать двумя способами:

1. 
   Составить матрицу смежности;
   
2. 
   Установить вершины графа вручную, связав их ребрами.
   

В данной программе можно редактировать полученный граф, то есть добавлять или удалять вершину или ребро.
На второй форме показаны все возможные гамильтоновы циклы в заданном графе. Эта форма появляется на после нажатия на кнопку в «Задание» в главном меню.



Листинг программы


Пример. Построение гамильтоновой цепи графе используя рекурсивный алгоритм

##include <iostream.h>

#include <stdio.h>

FILE* fi = fopen("g_graph.txt","r"); // Файл с матрицей смежности

FILE* fo = fopen("g_cycle.txt","w"); // Файл с найденными циклами

bool **graph; //Матрица смежности для хранения графа

int n; //Количество вершин в графе

const int vertex = 1; // первая вершина при поиске

int *St; //Массив для хранения просмотренных вершин

int *Nnew; //Массив признаков: вершина просмотрена или нет

void out_way(int n){ //Процедура вывода Гамильтонова цикла

for(int i=0;i
fprintf(fo,"%d\ ",St[i]);

fprintf(fo,"%d\n",vertex);

}

void gamilton_path(int k){

int v = St[k-1]; // текущая вершина

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

if(graph[v][j]==1) // есть ребро между v и j

if(k==n && j==vertex)out_way(n); //прошли все вершины

else

if(Nnew[j]){ // вершина не просмотрена

St[k]=j; // добавляем ее к пройденному пути

Nnew[j]=false; // просмотрена

gamilton_path(k+1); //строим путь дальше

Nnew[j]=true; //возвращаемся назад и строим другие циклы

}

}

int main(){

fscanf(fi,"%d",&n); //Считываем количество вершин

St = new int[n];

Nnew = new int[n];

for(int i = 0;i < n;i++)Nnew[i]=1; // Нет просмотренных вершин

graph = new bool*[n];

for(int i=0;i
graph[i] = new bool[n]; //выделяем память под строку

for(int j=0;j
fscanf(fi,"%d",&graph[i][j]);

}

}

Nnew[vertex]=false; //первая вершина уже просмотрена

St[0]=vertex; // вершина с которой начали проход

gamilton_path(1);//параметр означает количество пройденных вершин

fcloseall();

return(0);

}

   

Литература

1. 
   Брукшир Дж. Гленн Введение в компьютерные науки. Учебник. – М.: Вильямс, 2001
   
2. 
   Шень А. Программирование: теоремы и задачи. Учебное пособие. – М:МЦ НМО, 1995
   
3. 
   Лозикова И.О., Мосягина Н.А. Информатика: Учебное пособие. - Тюмень: ТюмГНГУ, 2004.
   
4. 
   Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учебное пособие. - Москва: ЛБЗ, 2003.
   
5. 
   Гапанович И.В. Дискретная математика: Учебное пособие. - Тюмень: ТюмГНГУ, 2002.