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

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

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

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

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

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

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

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

С учетом указанного разбиения программы ее структуру определим так, как показано на рисунке 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

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

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