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

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

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

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

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

По дисциплине «Дискретная математика»

Тема: Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов.

Выполнил

студент группы

АСОиУзс-07-01

Быстров Евгений М.

Шифр: 742301020016500

Проверил

Гапанович И.В.. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Тюмень 2008

 

Содержание.

 

 

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

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

      Студент группы АСОиУзс-07-01 Быстров Евгений  М.

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

      Тема: Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов.

      ЗАДАНИЕ 13. Построить гамильтонову цепь в графе, используя алгоритм с возвратом.

Определения.

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

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

      Граф  G называется связным, если для любых двух его вершин существует маршрут, их соединяющий, то есть любая вершина достижима из любой вершины.

      Матрица смежности графа – квадратная матрица, показывающая взаимосвязь вершин и рёбер.

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

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

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

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

      Для того, что сократить число шагов  в предложенном методе, рассмотрим следующий алгоритм. Предположим, что решение имеет вид последовательности v1…vi. Идея метода состоит в следующем: решение строится последовательно, начиная с пустой последовательности (длины 0). Далее, имея частичное решение ищем такое допустимое значение vi+1, которое ещё не было использовано, добавляем его к пройденному частичному решению и продолжаем процесс для нового частичного решения v1…vi+1. В противном случае, если такого значения vi+1 не существует, возвращаемся к предыдущему частичному решению v1…vi-1 и продолжаем процесс, пытаясь определить новое, еще не использованное допустимое значение vk. Такие алгоритмы носят название «алгоритмы с возвратом». Процесс поиска с возращением будет продемонстрирован в разделе «Ручной просчет» и «Тестирование программы» на примерах, показывающих как работает программа.

      Алгоритм  работы программы:

1. Создаётся пустая последовательность цепи длиной v (количество вершин).
2. Создаётся динамический массив для таблицы смежности графа, который заполняется из файла или прямо из программы.
3. Начинается поиск цепи с первой вершины (нулевая для матрицы).
4. Поочерёдно просматривается матрица смежности циклом for(где i - строка, j - столбец). Если от вершины идёт ребро, то проверяем была ли уже такая вершина. Если такая вершина уже есть в пути, то выходим из цикла и ищем следующую вершину. Если такой вершины не было, то записываем вершину в путь и продолжаем поиск с найденной вершины. Здесь же проверяем: если это последняя j-тая вершина, а ребер больше нет, то проверяем готова ли цепь, если последняя вершина пути не пуста, то цепь найдена. Если цепь не готова, записываем частичное решение сначала в переменную временной цепи (tempput), затем сравниваем это значение пути с уже имеющимися, если найдено совпадение, то возвращаемся на предыдущую вершину, а если такого пути не было, то записываем неполный путь в список временных путей.

      Если идет не ребро, если это последняя j-тая вершина, а ребер больше нет, то проверяем готова ли цепь. Если последняя вершина пути не пуста, то цепь найдена. Если цепь не готова записываем частичное решение сначала в переменную временной цепи (tempput), затем сравниваем это значение пути с уже имеющимися, если найдено совпадение, то возвращаемся на предыдущую вершину, а если такого пути не было, то записываем неполный путь в список временных путей.

5. Когда гамильтонова цепь найдена, она выводится в окно «Результат». Список частичных решений выводится в окно «Ход поиска цепи».

4. Ручной просчёт.

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

      Возьмём для примера следующий граф: 

       0, 1, 2, 3 – вершины  графа;

        Рёбра графа;

        Гамильтонова цепь в графе. 
 
 
 

      Рис. 1 Граф. 

      Теперь  покажем дерево данного графа:

        
 

         0312 – гамильтонова цепь

      
 
 
 
 
 
 

      Рис. 2 Дерево графа. 

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

        

      0 – если между вершинами нет  ребра

      1 – если между вершинами есть  ребро (или петля) 

      При расчёте гамильтоновой цепи, программа обращается к графу и работает с ним только посредством матрицы смежности.

      Расчёт  происходит так: сначала программа  создает пустую цепь длиной 4 символа. Создаётся массив куда заносятся  элементы матрицы. Берёт первый элементы пути и присваивает ему 0. То есть начинает поиск с нулевой вершины. Просматривает в матрице строку 0, находит значение 1 (есть ребро), проверяет номер столбца «1» и записывает номер столбца в путь, если такого там нет. Записывает неполный путь «01» в список временных путей. Далее поиск ведется в строке «1», находит 1 на пересечении строки «1» и столбца «0» и проверяет была ли такая вершина в пути, была, пропускает, ищет дальше, находит 1 на пересечении строки «1» и столбца «2». Проверка, такой вершины не было, записывает в маршрут (он теперь «012»), записывает неполный маршрут в список временных путей, ищет далее в строке «2». Смотрим: «2» «0» - значение 0 , «2» «1» - значение 1 было, «2» «2» - значение 0,     «2» «3» - значение 0. Теперь получается что это последняя j-тая вершина (столбец), а ребер больше нет, программа проверяет готова ли цепь. Так как цепь не готова, записывает частичное решение в список временных путей. Делает шаг назад, запоминает последнюю вершину, затем стирает её, и начинает поиск с предыдущей, пропуская текущую. Теперь маршрут снова «01», программа ищет дальше в строке «1», пропуская столбец «2» и находит 1 в следующем столбце «3». Проверяет, такой не было, записывает в путь, записывает неполный путь в список путей. Ищет в строке «3», не находит ничего подходящего, делает шаг назад, и начинает снова поиск со строки «1» столбца «0». Доходит до столбца «2», тут проверка показывает, что в списке неполных путей такой путь уже был. Не записывая повтор, делает шаг назад в пути «01», стирает единицу, запомнив её, и продолжает поиск в строке «0», пропустив столбец «1». Находит 1 в столбце «3» (путь «03»), затем «031», и наконец завершает гамильтонову цепь, найдя «2». Цепь готова: «0312».

 

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

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

      Программа состоит из одного главного окна (рис. 3)

        
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 
 
 

Рис. 3 Главное  окно программы. 

      Как видно из рисунка, программа состоит  из трёх блоков:

1. Входная информация. Здесь можно создать новый граф, указав количество вершин и его имя или загрузить готовые графы, которые записаны в папку с программой в текстовые файлы.
2. Тоже входная информация, а также основной цикл поиска гамильтоновой цепи (кнопка «Построить гамильтонову цепь»). Если создаётся новый граф, то для него вручную вводятся значения наличия или отсутствия (1 или 0 соответственно) рёбер между вершинами. Если выбирается готовый, то эти значения подставляются автоматически.
3. Выходная информация. Здесь выводится весь список временных вершин, а также результат: гамильтонова цепь. Также здесь можно сохранить набранный во втором блоке граф в текстовый файл.

 

      Ограничения программы.

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

6. Тестирование программы.

      Первый  тест уже подробно продемонстрирован  на рис. 1, 2, 3.

       Далее будут  продемонстрированы ещё два более  сложных теста программы с  рисунками графов и снимками внешнего вида программы после расчёта гамильтоновых цепей. 
 
 
 
 
 
 
 
 
 
 
 
 
 

      Рис. 4 Граф с 6-ю вершинами.