Прикладная программа для нахождения раскраски неориентированного графа ограниченным числом цветов - Курсовая работа

1. ТЕХНИЧЕСКОЕ ЗАДАНИЕ 1.1 Назначение разработки 1.2 Основание для разработки 1.3 Требования к программе 1.3.1 Входные данные 1.3.2 Выходные данные 1.3.3 Процессы обработки 1.3.4 Требования пользователя 1.3.5 Функциональные требования 1.3.6 Требования к условиям эксплуатации 1.3.7 Требования к численности и квалификации персонала 1.3.8 Требования по сохранности информации 1.3.9 Требования по стандартизации и унификации 1.3.10 Требования к программной совместимости 1.3.11 Результирующие компоненты изделия 1.3.12 Этапы разработки программы 1.3.13 Требования к документации 2. ВАРИАНТ ЗАДАНИЯ 3. ЭСКИЗНЫЙ ПРОЕКТ 4.1 Переборный алгоритм раскраски 4.2 Последовательный алгоритм раскраски 4.3 Разработка структуры программы 5. ТЕХНИЧЕСКИЙ ПРОЕКТ 5.1 Сценарий диалога с пользователем 5.2 Разработка основных форматов данных 5.3 Детализация алгоритма раскраски графа 5.4 Разработка формата файла для хранения графов 6. РАБОЧИЙ ПРОЕКТ 6.1 Выбор удобочитаемых идентификаторов 6.2 Общая организация проекта 6.3 Описание модулей 6.3.1 Модуль uMain 6.3.2 Модуль uData 6.3.3 Модуль uFiling 6.3.4 Модуль uColoring 6.3.5 Модуль uInputk 6.3.6 Модуль uHelp 6.4 Отладка и тестирование программного продукта 6.5 Руководство пользователю БИБЛИОГРАФИЧЕСКИЙ СПИСОК ПРИЛОЖЕНИЕ ВВЕДЕНИЕ Задачи на графах являются одними из наиболее трудоемких. Реализация задач данного класса на ПЭВМ позволяет повысить качество их решения за счет существенного увеличения числа анализируемых вариантов. В данной курсовой работе решается одна из известных графовых задач - поиск раскраски вершин заданным числом цветов. ТЕХНИЧЕСКОЕ ЗАДАНИЕ 1.1 Назначение разработки Разрабатываемая программа предназначена для нахождения раскраски заданного неориентированного графа ограниченным числом цветов с использованием алгоритма последовательного перебора. 1.2 Основание для разработки Данный программный продукт разрабатывается как курсовая работа по дисциплине «Программирование». 1.3 Требования к программе 1.3.1 Входные данные Входными данными программы являются неориентированный граф, число вершин которого не превышает заданного ограничения, число цветов, которыми необходимо раскрасить данный граф. 1.3.2 Выходные данные К выходным данным относятся вариант раскраски графа заданным числом цветов, хроматическое число графа, сообщения о невозможности нахождения раскраски. 1.3.3 Процессы обработки Ввод исходного графа и числа цветов, сохранение графа в файле, чтение графа из файла, нахождение раскраски, отображение раскраски. 1.3.4 Требования пользователя Разрабатываемая программа, с точки зрения пользователя, должна обладать следующими свойствами: · работа в условиях визуального (графического) режима; · удобство и простота ввода графа (задание с помощью мыши, клавиатуры и меню); · обеспечение автоматического контроля правильности входной информации, вводимой пользователем (контроль параметров графа, количества цветов); · возможность сохранения и считывания сохраненных графов из файлов; · однозначность и наглядность представления результатов вычислений (цветовое выделение раскраски, выдача сообщения при невозможности раскраски). 1.3.5 Функциональные требования Программа должна удовлетворять следующим функциональным требованиям: · ввод исходного графа в графическом режиме с помощью манипуляций с мышью. Необходимо обеспечить добавление вершин и ребер, а также удаление вершин с автоматической перенумерацией оставшихся и удаление ребер при наведении и нажатии левой клавиши мыши; · отображение графа в виде матрицы смежности вершин. Допускается открытие любого файла с ранее сохраненным графом с проверкой корректности формата файла; · обработка графа должна выполняться по матрице смежности или эквивалентному способу описания, при этом алгоритм обработки (раскраски) определяется разработчиком. Задача о раскраске состоит в нахождении правильной раскраски данного графа G в наименьшее число цветов. Операция слияния состоит в удалении вершин x и y и добавлении новой вершины z и ребер, соединяющих ее с каждой вершиной, с которой была смежна хотя бы одна из вершин x, y. Заметим, что граф имеет столько же вершин, сколько исходный граф, но у него больше ребер. 5 Окно включает следующие основные элементы управления: PaintBox (в качестве PaintBox используется фрагмент клиентской области главного окна, стандартный компонент PaintBox из-за присущих ему ограничений не используется) - область отображения графа, подлежащего раскраске; MainMenu - главное меню программы; StringGrid - строковая матрица, предназначенная для отображения и ввода матрицы смежности вершин исходного графа; SaveDialog - стандартное диалоговое окно для сохранения файлов; OpenDialog - стандартное диалоговое окно для открытия файлов; кнопки для быстрого доступа к часто используемым пунктам меню и выполнения других действий (очистка области отображения для ввода нового графа, запуск процесса раскраски текущего графа и выход из программы); StatusBar - полоса статуса, предназначенная для отображения текущего состояния программы. Нажатие кноп