Реферат: Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов
Рёбра графа;
Гамильтонова цепь в графе.
Рис. 1 Граф.
Теперь покажем дерево данного графа:
0312 – гамильтонова цепь
Рис. 2 Дерево графа.
Составим матрицу смежности для данного графа:
| v | 0 | 1 | 2 | 3 |
| 0 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
| 2 | 0 | 1 | 0 | 0 |
| 3 | 1 | 1 | 0 | 0 |
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 или 0 соответственно) рёбер между вершинами. Если выбирается готовый, то эти значения подставляются автоматически.
- Выходная информация. Здесь выводится весь список временных вершин, а также результат: гамильтонова цепь. Также здесь можно сохранить набранный во втором блоке граф в текстовый файл.
Ограничения программы.
- Программа предусматривает действительное наличие гамильтоновой цепи в заданном графе. В случае, если цепи в графе не существует, то программа этого определить не сможет и либо произойдёт зависание программы из-за того что основной поисковый цикл войдёт в бесконечное цикл, либо программа выдаст ошибочный результат.
- В блоке 2 при ручном вводе значений, допускается ввод только 0 или 1. Другие значения, а также пустая ячейка матрицы смежности приведёт либо к ошибке программы, либо к её зависанию.
6. Тестирование программы.
Первый тест уже подробно продемонстрирован на рис. 1, 2, 3.
Далее будут продемонстрированы ещё два более сложных теста программы с рисунками графов и снимками внешнего вида программы после расчёта гамильтоновых цепей.
Рис. 4 Граф с 6-ю вершинами.
Рис. 5 Тест № 1. Расчет гамильтоновой цепи.
 |
Рис. 6 Другой граф с 6-ю вершинами
Рис. 7 Тест № 2
Литература.
- В.С. Гапанович, И. В. Гапанович «Дискретная математика», уч. пособие для студентов ИВТ, ТГНГУ, Тюмень, 2002.
- http://programmersclub.ru/
- http://www.realcoding.net/article/rubric/CCplus
Приложение 1. Листинг программы.
//---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop
#include <fstream.h>
#include "Unit1.h"