Прикладная программа. Раскраска графа - Курсовая работа

Курский государственный технический университет КУРСОВАЯ РАБОТА по дисциплине «Программирование на языке высокого уровня»Реализация задач данного класса на ПЭВМ позволяет повысить качество их решения за счет существенного увеличения числа анализируемых вариантов. С точки зрения эффективности учебного процесса задачи на графах превосходят большинство других видов задач. Это обусловлено, с одной стороны, необходимостью разработки и проверки разветвленных и логически сложных алгоритмов, с другой стороны, потребностью в проектировании комплексных структур данных. Все сказанное, в конечном счете, наилучшим образом способствует развитию логико-алгоритмической культуры обучаемого и приобретению навыков разработки и отладки графических приложений со стандартизированным интерфейсом.Разрабатываемая программа предназначена для нахождения раскраски заданного неориентированного графа ограниченным числом цветов с использованием алгоритма последовательного перебора.Данный программный продукт разрабатывается как курсовая работа по дисциплине «Программирование на языках высокого уровня».Входными данными программы являются неориентированный граф, число вершин которого не превышает заданного ограничения, число цветов, которыми необходимо раскрасить данный граф.К выходным данным относятся вариант раскраски графа заданным числом цветов, хроматическое число графа, сообщения о невозможности нахождения раскраски.Ввод исходного графа и числа цветов, сохранение графа в файле, чтение графа из файла, нахождение раскраски, отображение раскраски.Разрабатываемая программа, с точки зрения пользователя, должна обладать следующими свойствами: · работа в условиях визуального (графического) режима;Программа должна удовлетворять следующим функциональным требованиям: · ввод исходного графа в графическом режиме с помощью манипуляций с мышью. Необходимо обеспечить добавление вершин и ребер, а также удаление вершин с автоматической перенумерацией оставшихся и удаление ребер при наведении и нажатии левой клавиши мыши; Требуется обеспечить возможность добавления ребер и их удаления через матрицу; · граф при необходимости сохраняется в файле специального формата (формат разрабатывается в ходе выполнения курсовой работы). · обработка графа должна выполняться по матрице смежности или эквивалентному способу описания, при этом алгоритм обработки (раскраски) определяется разработчиком.· ПЭВМ класса IBM PC/AT; · операционная система Windows 2000, XP;Для работы с программой требуется один человек, квалифицированный в области теории графов и алгоритмизации, обладающий средней квалификацией в программировании на языке Pascal.Программа должна обеспечивать сохранение введенных графов и настроек в файлах на внешних носителях.Нотация идентификаторов и терминология комментариев во всех компонентах среды должны соответствовать терминологии, используемой в теории графов и вычислительной технике.Код программы должен быть написан на стандартном языке Pascal с использованием стандартных компонент библиотеки VCL Delphi 7.0.Результирующий программный продукт необходимо представить в виде исполнимого модуля, совокупности исходных программных модулей, снимков с экрана (скриншотов), набора тестовых примеров и эксплуатационной документации (в электронной форме и на бумажном носителе). 1.3.12 Этапы разработки программы: · проектирование структуры программы;Перечень представляемых документов: · задание на курсовую работу; · описание структуры программы; Все документы оформляются на листах формата A4, на одной стороне листа, и представляются в виде пояснительной записки.Заданы граф , где V - множество вершин; E - множество ребер, и положительное целое число , где - мощность множества V.Раскраской вершин графа называется назначение цветов его вершинам. Тогда раскраска является функцией, определенной на множестве вершин графа и принимающей значения во множестве {1,2…k}. Раскраску можно также рассматривать как разбиение множества вершин , где - множество вершин цвета i. Задача о раскраске состоит в нахождении правильной раскраски данного графа G в наименьшее число цветов. Если в каком-нибудь графе имеется полный подграф с k вершинами, то для раскраски этого подграфа необходимо k цветов.Рассмотрим алгоритм решения задачи о раскраске, основанный на полном рекурсивном переборе различных вариантов. Данный алгоритм оперирует деревом вариантов, обход которого позволяет найти точное решение (хроматическое число графа). Выберем в данном графе G две несмежные вершины и и построим два новых графа: , получающийся добавлением ребра к графу G, и, получающийся из G слиянием вершин x и y. Операция слияния состоит в удалении вершин x и y и добавлении новой вершины z и ребер, соединяющих ее с каждой вершиной, с которой была смежна хотя бы одна из вершин x, y.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

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. ЭСКИЗНЫЙ ПРОЕКТ

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.1.1 Основные переменные, константы и типы модуля

6.3.1.2 Компоненты модуля

6.3.1.3 Процедуры модуля

6.3.1.4 Функции модуля

6.3.2 Модуль UDATA

6.3.3 Модуль UFILING

6.3.3.1 Основные переменные, константы и типы модуля

6.3.3.2 Функции модуля

6.3.4 Модуль UCOLORING

6.3.4.1 Основные переменные, константы и типы модуля

6.3.4.2 Процедуры модуля

6.3.4.3 Функции модуля

6.3.5 Модуль UINPUTK

6.3.5.1 Основные переменные, константы и типы модуля

6.3.5.2 Компоненты модуля

6.3.5.3 Процедуры модуля

6.3.6 Модуль UHELP

6.3.6.1 Основные переменные, константы и типы модуля

6.3.6.2 Компоненты модуля

6.3.6.3 Процедуры модуля

6.4 Отладка и тестирование программного продукта

6.5 Руководство пользователю

ПРИЛОЖЕНИЕ: Листинг программы

БИБЛИОГРАФИЧЕСКИЙ СПИСОК