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

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

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

. ТЕХНИЧЕСКОЕ ЗАДАНИЕ

.1 Назначение разработки

.2 Основание для разработки

.3 Требования к программе

.3.1 Входные данные

.3.2 Выходные данные

.3.3 Процессы обработки

.3.4 Требования пользователя

.3.5 Функциональные требования

.3.6 Требования к условиям эксплуатации

.3.7 Требования к численности и квалификации персонала

.3.8 Требования по сохранности информации

.3.9 Требования по стандартизации и унификации

.3.10 Требования к программной совместимости

.3.11 Результирующие компоненты изделия

.3.12 Этапы разработки программы

.3.13 Требования к документации

. ВАРИАНТ ЗАДАНИЯ

. КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

. ЭСКИЗНЫЙ ПРОЕКТ

.1 Переборный алгоритм раскраски

.2 Последовательный алгоритм раскраски

.3 Разработка структуры программы

. ТЕХНИЧЕСКИЙ ПРОЕКТ

.1 Сценарий диалога с пользователем

.2 Разработка основных форматов данных

.3 Детализация алгоритма раскраски графа

.4 Разработка формата файла для хранения графов

. РАБОЧИЙ ПРОЕКТ

.1 Выбор удобочитаемых идентификаторов

.2 Общая организация проекта

.3 Описание модулей

.3.1 Модуль uMain

.3.2 Модуль uData

.3.3 Модуль uFiling

.3.4 Модуль uColoring

.3.5 Модуль uInputk

.3.6 Модуль uHelp

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

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

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

ПРИЛОЖЕНИЕ

ВВЕДЕНИЕ

Задачи на графах являются одними из наиболее трудоемких. Для многих из них не существуют достаточно эффективных алгоритмов решения. Это объясняется комбинаторным характером процесса поиска решений и сложной логикой действий на каждом его шаге. Реализация задач данного класса на ПЭВМ позволяет повысить качество их решения за счет существенного увеличения числа анализируемых вариантов.

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

В данной курсовой работе решается одна из известных графовых задач - поиск раскраски вершин заданным числом цветов. На основе известного алгоритма последовательного сокращенного перебора вершин разрабатывается граф-схема алгоритма раскраски. Выполняется программирование граф-схемы на языке Object Pascal, реализуется графическое отображение и редактирование графов, их сохранение в файлах специального упакованного формата. Все указанные действия осуществляются в среде программирования Delphi 7.0.

1. ТЕХНИЧЕСКОЕ ЗАДАНИЕ

.1 Назначение разработки

Разрабатываемая программа предназначена для нахождения раскраски заданного неориентированного графа ограниченным числом цветов с использованием алгоритма последовательного перебора.

.2 Основание для разработки

Данный программный продукт разрабатывается как курсовая работа по дисциплине «Программирование».

.3 Требования к программе

.3.1 Входные данные

Входными данными программы являются неориентированный граф, число вершин которого не превышает заданного ограничения, число цветов, которыми необходимо раскрасить данный граф.

.3.2 Выходные данные

К выходным данным относятся вариант раскраски графа заданным числом цветов, хроматическое число графа, сообщения о невозможности нахождения раскраски.

.3.3 Процессы обработки

Ввод исходного графа и числа цветов, сохранение графа в файле, чтение графа из файла, нахождение раскраски, отображение раскраски.

1.3.4 Требования пользователя

Разрабатываемая программа, с точки зрения пользователя, должна обладать следующими свойствами:

·        работа в условиях визуального (графического) режима;

·        удобство и простота ввода графа (задание с помощью мыши, клавиатуры и меню);

·        обеспечение автоматического контроля правильности входной информации, вводимой пользователем (контроль параметров графа, количества цветов);

·        возможность сохранения и считывания сохраненных графов из файлов;

·        однозначность и наглядность представления результатов вычислений (цветовое выделение раскраски, выдача сообщения при невозможности раскраски).

.3.5 Функциональные требования

Программа должна удовлетворять следующим функциональным требованиям:

·        отображение графа в виде матрицы смежности вершин. Требуется обеспечить возможность добавления ребер и их удаления через матрицу;

·        граф при необходимости сохраняется в файле специального формата (формат разрабатывается в ходе выполнения курсовой работы). Допускается открытие любого файла с ранее сохраненным графом с проверкой корректности формата файла;

·        обработка графа должна выполняться по матрице смежности или эквивалентному способу описания, при этом алгоритм обработки (раскраски) определяется разработчиком. При нахождении нескольких вариантов раскраски с одинаковым числом цветов, выбирается любой. Желательно, в дополнение, находить минимальную раскраску и выдавать хроматическое число графа на экран;

·        найденный вариант раскраски, удовлетворяющий заданному ограничению на число цветов, должен отображаться цветовым выделением вершин исходного графа. Выбор цветов определяется разработчиком;

·        при отсутствии возможности раскраски графа заданным числом цветов, на экране должно выводиться соответствующее сообщение, а исходный граф должен оставаться в первоначальном виде;

·        максимальное количество вершин графа должно быть ограничено некоторой константой, зависящей от применяемого алгоритма раскраски и быстродействия используемой ЭВМ. Количество ребер не ограничивается;

·        при обработке графов с большим числом вершин, а также при их сохранении и загрузке, необходимо использовать элементы управления для индикации текущего состояния процесса обработки;

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

.3.6 Требования к условиям эксплуатации

·        ПЭВМ класса IBM PC/AT;

·        операционная система Windows 2000, XP;

·        язык программирования Object Pascal;

·        среда программирования Delphi 7 и выше;

·        меню, сообщения и система поиска на русском языке;

·        разрешение экрана не менее 800x600 точек.

1.3.7 Требования к численности и квалификации персонала

Для работы с программой требуется один человек, квалифицированный в области теории графов и алгоритмизации, обладающий средней квалификацией в программировании на языке Pascal.

.3.8 Требования по сохранности информации

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

.3.9 Требования по стандартизации и унификации

Нотация идентификаторов и терминология комментариев во всех компонентах среды должны соответствовать терминологии, используемой в теории графов и вычислительной технике. Сценарий диалога с пользователем должен отвечать стандартам приложений ОС семейства Windows.

.3.10 Требования к программной совместимости

Код программы должен быть написан на стандартном языке Pascal с использованием стандартных компонент библиотеки VCL Delphi 7.0.

.3.11 Результирующие компоненты изделия

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

1.3.12 Этапы разработки программы:

·        проектирование структуры программы;

·        разработка сценария диалога с пользователем;

·        разработка основных алгоритмов;

·        проектирование формата файлов;

·        программирование алгоритмов и структур данных;

·        отладка и тестирование программы;

·        документирование.

1.3.13 Требования к документации

Перечень представляемых документов:

·        задание на курсовую работу;

·        техническое задание на разработку;

·        описание структуры программы;

·        описание сценария диалога с пользователем;

·        схемы основных алгоритмов;

·        описание форматов данных и файлов;

·        контрольные примеры и результаты программы;

·        листинги основных программных модулей;

·        краткая эксплуатационная документация.

Все документы оформляются на листах формата A4, на одной стороне листа, и представляются в виде пояснительной записки.

Документы по содержанию должны соответствовать ГОСТ 34.201-89, 34.602-89, 19.701-90.

2. ВАРИАНТ ЗАДАНИЯ

Заданы граф , где V - множество вершин; E - множество ребер, и положительное целое число , где  - мощность множества V. Раскрасить вершины графа K красками так, чтобы ни одно его ребро не имело соцветных концов. Если такая раскраска невозможна, выдать на экран соответствующее сообщение. Предусмотреть графическое представление исходного графа и цветовое выделение его вершин на экране.

граф раскраска алгоритм модуль

3. КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

Раскраской вершин графа называется назначение цветов его вершинам. Обычно цвета - это числа 1,2…k. Тогда раскраска является функцией, определенной на множестве вершин графа и принимающей значения во множестве {1,2…k}. Раскраску можно также рассматривать как разбиение множества вершин , где  - множество вершин цвета i. Множества  называют цветными классами. Раскраска называется правильной, если каждый цветной класс является независимым множеством. Иначе говоря, в правильной раскраске любые две смежные вершины должны иметь разные цвета. Задача о раскраске состоит в нахождении правильной раскраски данного графа G в наименьшее число цветов. Это число называется хроматическим числом графа и обозначается .

В правильной раскраске полного графа  все вершины должны иметь разные цвета, поэтому . Если в каком-нибудь графе имеется полный подграф с k вершинами, то для раскраски этого подграфа необходимо k цветов. Отсюда следует, что для любого графа выполняется неравенство .

Однако хроматическое число может быть и строго больше кликового числа. Например, для цикла длины 5 , а . Другой пример показан на рис. 1. На нем изображен граф, вершины которого раскрашены в 4 цвета (цвета вершин показаны в скобках). Нетрудно проверить, что трех цветов для правильной раскраски этого графа недостаточно. Следовательно, его хроматическое число равно 4. Очевидно также, что кликовое число этого графа равно 3.

Рис. 1.

Очевидно, что  тогда и только тогда, когда G - пустой граф. Нетрудно охарактеризовать и графы с хроматическим числом 2 (точнее, не больше 2). По определению, это такие графы, у которых множество вершин можно разбить на два независимых множества. Но это совпадает с определением двудольного графа. Поэтому двудольные графы называют еще бихроматическими. Согласно теореме Кенига, граф является бихроматическим тогда и только тогда, когда в нем нет циклов нечетной длины.

Для графов с хроматическим числом 3 такого простого описания мы не знаем. Неизвестны и простые алгоритмы, проверяющие, можно ли данный граф раскрасить в 3 цвета. Более того, задача такой проверки (вообще, задача проверки возможности раскрасить граф в k цветов при любом фиксированном ) является NP-полной.

4. ЭСКИЗНЫЙ ПРОЕКТ

4.1 Переборный алгоритм раскраски

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

Выберем в данном графе G две несмежные вершины  и  и построим два новых графа: , получающийся добавлением ребра  к графу G, и, получающийся из G слиянием вершин x и y. Операция слияния состоит в удалении вершин x и y и добавлении новой вершины z и ребер, соединяющих ее с каждой вершиной, с которой была смежна хотя бы одна из вершин x, y. На рис. 2 показаны графы  и , получающиеся из графа G, изображенного на рис. 1, с помощью этих операций, если в качестве x и y взять вершины a и .

Рис. 2.

Если в правильной раскраске графа G вершины x и y имеют разные цвета, то она будет правильной и для графа . Если же цвета вершин x и y в раскраске графа G одинаковы, то граф  можно раскрасить в то же число цветов: новая вершина z окрашивается в тот цвет, в который окрашены вершины x и y, а все остальные вершины сохраняют те цвета, которые они имели в графе G. И наоборот, раскраска каждого из графов , , очевидно, дает раскраску графа G в то же число цветов. Поэтому , что дает возможность рекурсивного нахождения раскраски графа в минимальное число цветов. Заметим, что граф  имеет столько же вершин, сколько исходный граф, но у него больше ребер. Поэтому рекурсия, в конечном счете, приводит к полным графам, для которых задача о раскраске решается тривиально.

4.2 Последовательный алгоритм раскраски

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

В этом простейшем из методов вершины вначале располагаются в порядке невозрастания их степеней.

Первая вершина окрашивается в цвет 1; затем список вершин просматривается сверху вниз (по невозрастанию степеней) и в цвет 1 окрашивается всякая вершина, которая не смежна с другой, уже окрашенной в этот цвет. Потом возвращаемся к первой в списке неокрашенной вершине, окрашиваем ее в цвет 2 и снова просматриваем список вершин сверху вниз, окрашивая в цвет 2 любую неокрашенную вершину, которая не соединена ребром с другой, уже окрашенной в цвет 2 вершиной. Аналогично действуем с цветами 3, 4 и т.д., пока не будут окрашены все вершины. Число использованных цветов будет тогда приближенным значением хроматического числа графа.

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

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

.3 Разработка структуры программы

Разобьем программу на несколько модулей по функциональному признаку с учетом требований, перечисленных выше. Основным из них будет модуль раскраски. Его задача - реализация выбранного алгоритма раскраски графа. Для редактирования графа введем отдельный модуль - редактор. С его помощью будем вводить вершины и ребра графа, мышью или с клавиатуры. Редактор будет проверять ограничения по максимальному числу вершин. Операции загрузки и сохранения графов в файлах объединим в модуле управления файлами. Для системы помощи определим отдельный модуль.

Рис. 3.

5. ТЕХНИЧЕСКИЙ ПРОЕКТ

5.1 Сценарий диалога с пользователем

Работу пользователя с разрабатываемой программой представим в виде сценария, заданного ориентированным графом переходов. Вершины графа поставим в соответствие основным окнам и диалогам программы, а дугами будем отображать все возможные переходы между ними. На каждой дуге запишем пункт меню или идентификатор кнопки, при выборе которых происходит соответствующий переход. Граф представлен на рис. 4. По графу легко проследить возможные переходы пользователя по диалогам. Например, при запуске программы открывается окно редактора графа (главное окно). Из него, выбрав пункт меню «Открыть», можно активировать окно выбора файла и загрузить граф из выбранного файла в окно редактора.

Рис. 4

Определим внешний вид окон, присутствующих в графе на рис. 4. Вид окна редактора графа дан на рис. 5:

Рис. 5

Окно включает следующие основные элементы управления: PaintBox (в качестве PaintBox используется фрагмент клиентской области главного окна, стандартный компонент PaintBox из-за присущих ему ограничений не используется) - область отображения графа, подлежащего раскраске; MainMenu - главное меню программы; StringGrid - строковая матрица, предназначенная для отображения и ввода матрицы смежности вершин исходного графа; SaveDialog - стандартное диалоговое окно для сохранения файлов; OpenDialog - стандартное диалоговое окно для открытия файлов; кнопки для быстрого доступа к часто используемым пунктам меню и выполнения других действий (очистка области отображения для ввода нового графа, запуск процесса раскраски текущего графа и выход из программы); StatusBar - полоса статуса, предназначенная для отображения текущего состояния программы.

Внешний вид окна ввода константы k представлен на рис. 6:

Рис. 6

Значение константы k выбирается из выпадающего списка ComboBox. Диапазон возможных значений зависит от числа вершин текущего графа N. Минимальное равно 1, а максимальное - N. Такой способ ввода k позволяет исключить заведомо неправильные значения (не число, не целое число, отрицательное число, значения за пределами допустимого диапазона) и является достаточно эффективным, т.к. диапазон значений невелик. Чтобы задать выбранное значение k, следует нажать кнопку «Задать». Нажатие кнопки «Отмена» отменяет сделанный выбор, оставляя ранее выбранное значение k.

Диалоговые окна сохранения и открытия файла, а также отображения справки имеют стандартный вид и рассматриваются в рабочем проекте (см. ниже). При возникновении ошибки открытия файла (файл поврежден, имеет некорректный формат и т.п.) выводится окно индикации ошибки открытия файла, показанное на рис. 7:

Рис. 7

Также при открытии файла на экране может появиться окно запроса на сохранение редактируемого графа, если этот граф изменился с момента последнего сохранения. Данное окно представлено на рис. 8.

Кроме описанных окон в программе могут использоваться дополнительные окна, вид которых будет определяться в рамках рабочего проекта.

Рис. 8

Состав пунктов главного меню программы отображен на рис. 9:

Рис. 9

Пункт «Файл» объединяет действия с файлами, содержащими графы, а также выход из программы. Подпункт «Новый» обеспечивает очистку области построения и матрицу смежности графа с закрытием текущего файла. Подпункт «Открыть» активирует диалоговое окно открытия файла и реализует загрузку графа из выбранного файла в область построения и матрицу смежности. Подпункт «Сохранить» позволяет сохранить внесенные изменения в текущий граф (при первом сохранении выводится окно запроса имени файла). Подпункт «Сохранить как» обеспечивает сохранение текущего графа (независимо от того изменен он или нет) в новый файл. Подпункт «Выход» служит для завершения программы (при наличии измененного и не сохраненного графа выводится окно запроса на сохранение файла).

Пункт «Редактирование» включает действия, обеспечивающие построение графа. Подпункт «Добавить вершину» позволяет ввести в граф новую вершину с проверкой ограничения на максимальное число вершин. Номер новой вершине присваивается автоматически.