Прикладная программа. Раскраска графа

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Федеральное агентство по образованию

Курский государственный технический университет

Кафедра ПО ВТ

КУРСОВАЯ РАБОТА

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

Прикладная программа. Раскраска графа

Курск, 2007 г

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

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 Руководство пользователю

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

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

ВВЕДЕНИЕ

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

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

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

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 Требования к условиям эксплуатации

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.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, исходящих из . Тогда эти вершины можно разместить в соответствии с величинами степеней . Если все-таки найдутся вершины, у которых совпадают и степени , и степени , то можно вычислить трехшаговые степени (определяемые аналогичным способом) и разместить вершины с учетом степеней и т.д. Можно действовать иначе: размещать вершины сразу в соответствии с их степенями или степенями и применять тот же самый последовательный метод раскраски.

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

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

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

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

Главным объектом данных в программе является неориентированный граф, подлежащий раскраске. Для задания таких графов в математике обычно используют матрицы и списки. Наиболее просто представить граф матрицей смежности вершин. В такой матрице элемент, расположенный на пересечении строки i и столбца j, равен 1, если вершины i и j связаны ребром, и 0 в противном случае. Матрица смежности вершин обеспечивает высокую скорость выполнения основных операций над графами, но для графов большого размера не эффективна по затратам памяти, т.к. содержит большое число нулей. Однако в нашей задаче обработка таких графов не представляется возможной из-за довольно высокой трудоемкости алгоритма раскраски и сложности изображения графа с большим (более 20-25) числом вершин на форме, поэтому выбор матрицы смежности вполне оправдан. Представление графа в виде списка более эффективно по затратам памяти, но требует большего времени на выполнение типовых операций.

Итак, структура данных для представления исходного графа будет иметь следующий общий вид:

,

где , если вершины i и j связаны ребром, иначе.

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

Таким образом, структура данных для хранения цветов вершин будет представлена следующим образом:

,

где , если вершине i не назначен цвет, , если вершине i поставлен в соответствие цвет f.

Для хранения текущих значений «относительных» локальных степеней вершин графа в процессе раскраски введём вектор-строку L, i-ый элемент которой (обозначаемый через ) будет соответствовать i-ой вершине графа. Локальные степени будем рассчитывать без учёта уже окрашенных вершин, чего требует выбранный алгоритм раскраски.

Согласно сказанному, структура данных для хранения локальных степеней вершин будет определяться в виде:

,

где , если i-ая вершина не раскрашена, иначе.

Так как вектор L переупорядочивается по невозрастанию и соответствие между номерами вершин и его элементами нарушается, необходимо также хранить и вектор номеров вершин после переупорядочения. Этот вектор обозначим через O и определим в виде:

,

где - номер вершины, которой соответствует i-й элемент вектора L, до переупорядочения вектора L.

С целью задания в программе текущих координат вершин в области построения графа PaintBox введем вектор-столбец V следующего формата:

,

где , - декартовы координаты центра i-ой вершины в области построения графа.

Для удобства работы пользователя при редактировании графа в программе реализуется отмена и восстановление последнего удаления вершины или ребра. Поддержка этих операций требует введения структур данных для хранения информации о последнем удаленном элементе. Эти структуры должны модифицироваться всякий раз, когда выполняется операция по редактированию графа. Для отмены удаления ребра достаточно сохранять номера его концевых вершин. Для отмены удаления вершины нужно хранить ее порядковый номер и декартовы координаты, а также номера и координаты всех вершин, которые были смежны с ней до удаления. При этом следует учитывать автоматическую перенумерацию вершин после удаления. Также необходимо учитывать изменения векторов C и V и матрицы смежности вершин A.

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

,

где - порядковый номер вершины, - ее декартовы координаты (). Для удаленного ребра , , а - номера его концевых вершин. Для удаленной вершины - локальная степень, - ее порядковый номер до перенумерации, - ее декартовы координаты, а - соответственно номер до перенумерации и координаты j-ой вершины, смежной с удаленной ().

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

Разработаем граф-схему алгоритма раскраски графа по описанию, представленному в разделе «Эскизный проект» с учетом определённой выше структуры программы (см. рис.10).

В граф-схеме на рис.10 использованы разработанные выше структуры данных, а также следующие дополнительные переменные:

S - множество еще не раскрашенных вершин графа;

f - текущий цвет;

b - признак отсутствия вершин, которые можно раскрасить в цвет f;

- номер текущей раскрашиваемой вершины;

i - индекс для перебора вершин.

Рис. 10

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

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

бит,

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

байт,

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

бит.

На рисунке 11 дано графическое представление хранимой в файле информации (а) и формата файла (б).

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

1. Чтение числа вершин n и проверка правильности значения.

2. Циклическое побайтовое считывание оставшейся части файла в одномерный массив, содержащий B байт.

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

4. Доопределение матрицы смежности вершин путем симметричного отображения верхней треугольной части на нижнюю и обнуления элементов главной диагонали.

Алгоритм записи графа в файл будет содержать следующие этапы:

1. Побитовое копирование строк верхней треугольной части матрицы смежности вершин в одномерный массив из B байт.

2. Запись в файл числа вершин графа n.

3. Циклическая перезапись массива с матрицей смежности в хвост файла.

(а)

(б)

Рис. 11

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

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

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

Таблица 1

№	Обозначение в алгоритме	Программный идентификатор
1	A	AdMatrix
2	n	VCount
3	C	VColor
4	L	VDegree
5	U	UndoItem
6	S	Uncolored
7	f	CurColor
8	b	Colorable
9	q	VCur
10	V	VCenter
11	O	VNumber
11	индексы i, j, k и т.д.	без изменений

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

Данный проект состоит из 6-ти модулей: uMain, uData, uHelp, uFiling, uColoring, uInputk.

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

6.3.1 Модуль uMain

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

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

fmMain: TfmMain - основная форма;

TUndoItem - тип данных для представления информации о последнем выполненном действии над графом (используется в режимах Отмена и Восстановление);

VRadius - радиус окружности вершины графа;

AdMatrix: TAdMatrix - матрица смежности вершин текущего графа;

VCount: Byte - число вершин текущего графа;

VColor: TColoring - текущая раскраска вершин;

VCenter: array of TPoint - массив координат центров вершин;

UndoItem: array of TUndoItem - информация об отмененной операции;

k: Byte - требуемое число цветов;

GraphChanged: Boolean - признак измененного и не сохраненного графа.

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

Компоненты модуля uMain представлены в таблице 2.

Таблица 2

Компонент	Свойства, отличные от свойств по умолчанию	Функции
fmMain: TForm	BorderStyle: bsToolWindow, Caption: Раскраска графа, ClientHeight: 554, ClientWidth: 792, Color: clBtnFace, Menu: MainMenu, Position: poScreenCenter	Форма - контейнер
btnColoring: TBitBtn	Caption: Раскраска, Kind: bkOK	Кнопка «Раскраска» для запуска процесса раскраски графа
btnExit: TBitBtn	Caption: &Выход, Kind: bkClose	Кнопка «Выход» для выхода из программы
btnNew: TBitBtn	Caption: &Новый граф, Kind: bkRetry	Кнопка «Новый граф» для создания нового графа
MainMenu: TMainMenu	Items	Выбор необходимого режима работы при щелчке на соответствующем пункте главного меню
iFile	Caption: Файл	Пункты главного меню
iEdit	Caption: Редактирование
iHelp	Caption: Справка
iFNew	Caption: Новый, ShortCut: Ctrl+N	Подпункты пункта «Файл» главного меню
iFOpen	Caption: Открыть, ShortCut: Ctrl+O
iFSave	Caption: Сохранить, ShortCut: Ctrl+S
iFSaveAs	Caption: Сохранить как, ShortCut: Ctrl+A
iFBreak	Caption: -
iFExit	Caption: Выход, ShortCut: F10
iEUndo	Caption: Отмена, ShortCut: Ctrl+Z	Подпункты пункта «Редактирование» главного меню
iERedo	Caption: Восстановление, ShortCut: Ctrl+Alt+Z
iEBreak	Caption: -
iEAddV	Caption: Добавить вершину, ShortCut: F2
iEDelV	Caption: Удалить вершину, ShortCut: Del
iHHelp	Caption: Помощь, ShortCut: F1	Подпункты пункта «Справка» главного меню
iHAbout	Caption: О программе...
SaveDialog: TSaveDialog	DefaultExit: *.zot, Filter: Graph files (*.zot)|*.zot, Options: ofPathMustExist, Title: Сохранение графа в файл	Стандартное диалоговое окно для сохранения файлов
OpenDialog: TOpenDialog	DefaultExit: *.zot, Filter: Graph files (*.zot)|*.zot, Options: ofPathMustExist, ofFileMustExist, Title: Открытие файла для загрузки графа	Стандартное диалоговое окно для открытия файлов
sgMatrix: TStringGrid	DefaultColWidth: 20, DefaultRowHeight: 20, ScrollBars: ssBoth	Строковая таблица для отображения и ввода матрицы смежности вершин исходного графа
StatusBar: TStatusBar	SimplePanel: True, SizeGrip: False	Полоса статуса для отображения текущего состояния программы
stGraph: TStaticText	Caption: Исходный граф:	Метка для размещения в окне надписи «Исходный граф:»
stMatrix: TStaticText	Caption: Матрица смежности:	Метка для размещения в окне надписи «Матрица смежности:»

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

Процедура iFOpenClick - открывает файл при выборе пункта меню «Открыть», производит очистку и переформат таблицы матрицы смежности sgMatrix.

Процедура iFSaveClick - сохраняет файл при выборе пункта меню «Сохранить».

Процедура btnColoringClick - запускает процесс раскраски графа.

Процедура FormActivate - осуществляет инициализацию глобальных и компонентных данных модуля.

Процедура btnNewClick - создает новый граф при нажатии на кнопку «Новый граф».

Процедура iFNewClick - создает новый граф при выборе пункта меню «Новый».

Процедура iFSaveAsClick - сохраняет граф в другом файле при выборе пункта меню «Сохранить как».

Процедура iFExitClick - осуществляет выход из программы при выборе пункта меню «Выход».

Процедура btnExitClick - осуществляет выход из программы при нажатии на кнопку «Выход».

Процедура iEAddVClick - осуществляет добавление вершины, при этом изменяет матрицу смежности, определяет координаты новой вершины и осуществляет перерисовку вершин.

Процедура iEDelVClick - открывает форму fmInputk как модальную, осуществляет удаление выбранной вершины, удаление смежных с ней ребер, сброс цветов, перенумерацию и перерисовку оставшихся вершин.

Процедура iEUndoClick - осуществляет отмену последнего действия при выборе пункта меню «Отмена».

Процедура iERedoClick - осуществляет восстановление последнего отмененного действия при выборе пункта меню «Восстановление».

Процедура FillUndoDelVrx - осуществляет заполнение структуры данных для отмены удаления вершины.

Процедура iHHelpClick - осуществляет загрузку информации из файла помощи.

Процедура iHAboutClick - осуществляет загрузку информации о программе.

Процедура FormDeactivate - осуществляет освобождение памяти при закрытии формы.

Процедура sgMatrixSelectCell - осуществляет редактирование матрицы смежности вершин графа, сброс цветов и перерисовку вершин.

Процедура FormPaint - осуществляет перерисовку текущего графа в области построения, а также отображает границы области построения графа.

Процедура FormMouseUp - осуществляет добавление или удаление вершины графа при помощи мыши, при этом изменяет матрицу смежности, определяет координаты новой вершины, осуществляет перерисовку вершин после перенумерации и сброс цветов.

Процедура FormMouseDown - осуществляет захват вершины левой кнопкой мыши.

Процедура FormMouseMove - осуществляет соединение вершин перетаскиванием, очистку области, где ребро было на предыдущем шаге и прорисовку нового ребра в следующей позиции.

Процедура FormCloseQuery - запрос на закрытие формы.

Процедура InitForm - осуществляет приведение вида формы к исходному состоянию.

Процедура RemoveVertex - осуществляет удаление выбранной вершины, перезапись sgMatrix в матрицу смежности, формирование массива координат центров вершин, смежных с удаляемой, перенумерацию матрицы смежности и сдвиг массива координат центров вершин, а также изменение размеров структур данных и восстановление измененной матрицы смежности.

Процедура FillAdMatrix - осуществляет построение матрицы смежности по содержимому sgMatrix.

Процедура RepaintVertex - осуществляет перерисовку вершины на форме.

Процедура RepaintEdge - осуществляет перерисовку ребра на форме.

Процедура RepaintAllVertices - осуществляет перерисовку всех вершин на форме.

Процедура InitUndo - инициализирует структуру данных об отмененном действии.

Процедура FillUndoDelVrx - осуществляет заполнение структуры данных для отмены удаления вершины.

Процедура PrintGraphPath - осуществляет отображение пути к файлу с графом в заголовке.

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

Функция SaveRequest - вызывает запрос на сохранение графа в файле.

6.3.2 Модуль uData

Модуль служит для объединения общеиспользуемых констант и типов:

MaxVCount - максимальное число вершин графа;

TAdMatrix = array of array of Byte - матрица смежности графа;

TColoring = array of ShortInt - вектор цветов вершин;

TRealColors = array[0..MaxVCount-1] of TColor - системные имена цветов;

TVertices = array of TPoint - координаты центров вершин;

TGraphFile = file of Byte - файл графа.

6.3.3 Модуль uFiling

Модуль содержит функции для управления записью графов в файлы и считывание сохраненных графов из файлов.

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

GraphFile: TGraphFile - файл для сохранения графа.

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

DoSaveFile - осуществляет сохранение графа в файле по матрице смежности.

DoReadFile - осуществляет чтение графа из файла в матрицу смежности.

6.3.4 Модуль uColoring

Модуль объединяет процедуры, функции и переменные, используемые при реализации алгоритма раскраски графа.

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

RealColors: TRealColors - фактические цвета раскраски вершин;

VDegree: array of ShortInt - массив относительных локальных степеней;

VNumber: array of Byte - отсортированный массив номеров вершин;

Uncolored: set of Byte - множество не раскрашенных вершин.

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

DoNonminColoring - осуществляет раскраску графа в NewColorCount цветов по найденной минимальной раскраске.

InsertionSort - осуществляет сортировку массива локальных степеней методом вставки.

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

DoMinColoring - осуществляет раскраску графа в минимальное число цветов.

ResetColoring - осуществляет обнуление массива цветов вершин графа.

6.3.5 Модуль uInputk

Модуль содержит определение диалога для ввода количества цветов при раскраске графа, а также номера удаляемой вершины.

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

fmInputk: TfmInputk - форма для ввода числа цветов k.

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

Компоненты модуля uInputk представлены в таблице 3.

Таблица 3

Компонент	Свойства, отличные от свойств по умолчанию	Функции
fmInputk: TForm	BorderStyle: bsDialog, Caption: Ввод числа цветов k, ClientHeight: 94, ClientWidth: 360, Color: clBtnFace, Position: poMainFormCenter	Форма - контейнер
btnCansel: TBitBtn	Caption: Отмена, Kind: bkCancel	Кнопка «Отмена» для отмены выбранного действия и закрытия окна «Ввод числа цветов k»
btnSet: TBitBtn	Caption: Задать, Kind: bkOK	Кнопка «Задать» для задания числа цветов k и закрытия окна «Ввод числа цветов k»
ComboBox: TComboBox	-	Список для выбора пользователем числа цветов k для раскраски графа
StaticText: TStaticText	Caption: Задайте число цветов для раскраски графа	Метка для размещения в окне надписи «Задайте число цветов для раскраски графа»

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

Процедура btnSetClick - устанавливает значение k при нажатии на кнопку «Задать».

Процедура btnCancelClick - игнорирует ввод k при щелчке по кнопке «Отмена».

Процедура ComboBoxChange - осуществляет проверку по числу вершин.

Процедура FormActivate - обнуляет поле ввода ComboBox при запуске формы ввода числа цветов.

6.3.6 Модуль uHelp

Модуль обеспечивает отображение справочной информации и окна о программе.

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

fmHelp: TfmHelp - форма для файла справки;

HelpFileName: string = 'coloring.hlp' - имя файла справки.

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

Компоненты модуля uHelp представлены в таблице 4.

Таблица 4

Компонент	Свойства, отличные от свойств по умолчанию	Функции
fmHelp: TForm	AutoSize: True, BorderStyle: bsDialog, Caption: Помощь, Color: clBtnFace, ClientHeight: 569, ClientWidth: 537, Color: clBtnFace, Position: poMainFormCenter	Форма - контейнер
Panel: TPanel	BevelOuter: bvLowered	Панель для создания рельефного прямоугольника в клиентской области формы
RichEdit: TRichEdit	Align: alClient, BorderStyle: bsNone, Color: clCream, HideScrollBars: False, ReadOnly: True, ScrollBars: ssVertical	Окно для отображения содержимого файла справки и информации о программе

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

Процедура FormActivate - производит настройку внешнего вида и заполнение окна отображения текстом из файла справки или информацию о программе.

Процедура FormDeactivate - восстанавливает стандартный шрифт.

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

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

Ниже представлены снимки экрана программы на различных этапах ее работы с разными исходными данными.

Рис. 12

Исходное состояние окна программы или после нажатия кнопки «Новый граф»



Рис. 13

Окно программы с загруженным из файла графом

Рис. 14

Окно выбора числа цветов при раскраске



Рис. 15

Окно программы с предупреждением о невозможности раскраски выбранным числом цветов

Рис. 16

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

Рис. 17

Окно программы после удаления вершины 5 из графа, изображенного на рисунке 16

Рис. 18

Окно программы после добавления вершины и ребра в граф, изображенный на рисунке 17

Рис. 19

Окно программы с запросом на сохранение изменений в графе при нажатии одной из кнопок - «Новый граф», «Выход», «Открыть»

Рис. 20

Окно для выбора файла с графом



Рис. 21

Окно программы с предупреждением о превышении числа вершин

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

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

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

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

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

В программе используется следующий алгоритм раскраски графов.

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

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

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

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

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

program Coloring;

uses

Forms,

uMain in 'uMain.pas' {fmMain},

uInputk in 'uInputk.pas' {fmInputk},

uColoring in 'uColoring.pas',

uFiling in 'uFiling.pas',

uData in 'uData.pas',

uHelp in 'uHelp.pas' {fmHelp};

{$R *.res}

begin

Application.Initialize;

Application.CreateForm(TfmMain, fmMain);

Application.CreateForm(TfmInputk, fmInputk);

Application.CreateForm(TfmHelp, fmHelp);

Application.Run;

end.

unit uMain;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, Menus, ExtCtrls, StdCtrls, ComCtrls, Grids, Buttons, uData;

type

TfmMain = class(TForm)

MainMenu: TMainMenu;

OpenDialog: TOpenDialog;

SaveDialog: TSaveDialog;

iFile: TMenuItem;

iFNew: TMenuItem;

iFOpen: TMenuItem;

iFSave: TMenuItem;

iFSaveAs: TMenuItem;

iFBreak: TMenuItem;

iFExit: TMenuItem;

iEdit: TMenuItem;

iEUndo: TMenuItem;

iERedo: TMenuItem;

iEBreak: TMenuItem;

iEAddV: TMenuItem;

iEDelV: TMenuItem;

iEAddE: TMenuItem;

iEDelE: TMenuItem;

iHelp: TMenuItem;

iHHelp: TMenuItem;

iHAbout: TMenuItem;

stGraph: TStaticText;

StatusBar: TStatusBar;

stMatrix: TStaticText;

sgMatrix: TStringGrid;

btnNew: TBitBtn;

btnColoring: TBitBtn;

btnExit: TBitBtn;

procedure iFOpenClick(Sender: TObject);

procedure iFSaveClick(Sender: TObject);

procedure btnColoringClick(Sender: TObject);

procedure FormActivate(Sender: TObject);

procedure btnNewClick(Sender: TObject);

procedure iFNewClick(Sender: TObject);

procedure iFSaveAsClick(Sender: TObject);

procedure iFExitClick(Sender: TObject);

procedure btnExitClick(Sender: TObject);

procedure iEAddVClick(Sender: TObject);

procedure iEDelVClick(Sender: TObject);

procedure iEAddEClick(Sender: TObject);

procedure iEDelEClick(Sender: TObject);

procedure iEUndoClick(Sender: TObject);

procedure iERedoClick(Sender: TObject);

procedure iHHelpClick(Sender: TObject);

procedure iHAboutClick(Sender: TObject);

procedure FormDeactivate(Sender: TObject);

procedure sgMatrixSelectCell(Sender: TObject; ACol, ARow: Integer;

var CanSelect: Boolean);

procedure FormPaint(Sender: TObject);

procedure FormMouseUp(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

procedure FormMouseDown(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

procedure FormMouseMove(Sender: TObject; Shift: TShiftState; X,

Y: Integer);

procedure FormCloseQuery(Sender: TObject; var CanClose: Boolean);

private

PaintAreaWidth: Integer; // Размеры области рисования

PaintAreaHeight: Integer;

PaintAreaXMin,PaintAreaYMin: Integer; // Положение области рисования

MouseIsHeld: Boolean;

MouseHeldVNo: Byte;

RepaintOldEdge: Boolean;

DrawnEdge: record src,dst: TPoint end;

// Приведение вида формы к исходному состоянию

procedure InitForm(Repaint: Boolean = True);

// Удаление выбранной вершины

procedure RemoveVertex(

VNo: Cardinal; var VCount: byte; var RemVrx: TVertices);

// Построение матрицы смежности

procedure FillAdMatrix(A: TAdMatrix);

// Перерисовка вершины на форме

procedure RepaintVertex(x,y: Integer; ForceUpdate: Boolean = true );

// Перерисовка ребра на форме

procedure RepaintEdge(x1,y1,x2,y2: Integer);

// Перерисовка всех вершин на форме

procedure RepaintAllVertices;

// Запрос на сохранение графа в файле

function SaveRequest: Boolean;

// Инициализация структуры данных об отмененном действии

procedure InitUndo;

// Заполнение структуры данных для отмены удаления вершины

...