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

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

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

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

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

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

   Выполнил:

   студент группы АСОИУ-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, получим

      

   
 
 
 
 
 
 
 

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<n;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<n;i++){ 

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

    for(int j=0;j<n;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.