Алгоритм раскраски графа с перекраской двуцветных компонент
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
ых компонент может быть отнесен к классу точных полиномиальных алгоритмов. В [12] описан класс графов, для которого исследуемый алгоритм всегда находит минимальную раскраску. Эти графы получили название графов Мейниеля: у всех таких графов каждый нечетный цикл содержит, по крайней мере, две хорды. Доказано, что всякий граф Мейниеля является совершенным графом.
Что касается трудоемкости алгоритма раскраски вершин графа Мейниеля с перекраской двухцветных компонент, то она может быть оценена как шагов.
Программа. Описание разработанной программы
На основании изученного материала была разработана и реализована программа, раскрашивающая вершины заданного графа. Программа разработана в среде VisualStudio2010 С++ с использованием библиотеки с графами BoostGraphLibrary.
Данная программа работает с файлами. Входные файлы должны содержать граф, описанный на языке DOT [13, 14] (см. рис.6) - специальный язык для описания графов. Это довольно простой способ описания графов, как люди, так и компьютерные программы могут легко его использовать.Принято файлы делать с расширением .dot.
Рисунок 6. Входной файл
Выходной файл имеет такой же формат (см. рис.7).
Рисунок 7. Выходной файл
В результате работы программы выводит, какими цветами окрашены вершины, сколько цветов потребовалось на раскраску графа и какое потратилось время работы программы. Так же будет видно, в каком порядке окрашивались вершины и сколько раз использовался тот или иной цвет.
Опишем, как необходимо работать с программой.
Чтобы запустить программу, необходимо открыть командную строку, где лежит папка с программой (см. рис. 8):
Рисунок 8. Внешний вид программы
Далее необходимо прописать адрес, где лежит suboptimal_coloring.exe и затем, с помощью обозначений:
-input-filename- это откуда берётся выбранный файл;
-output-filename - это соответственно наоборот, куда он кладется;
out\Debug-Win32\suboptimal_coloring.exe--input-filenamedata/exp1.1.dot--output-filenamedata/exp1.1.colored.dot--report-filenamedata/report.csv(..9)">написать полностью строку вызова файла. Она должна выглядеть следующим образом: D:\XXX\graph_coloring-r181\trunk>out\Debug-Win32\suboptimal_coloring.exe --input-filename data/exp1.1.dot --output-filename data/exp1.1.colored.dot --report-filename data/report.csv (см. рис. 9)
Рисунок 9. Строка вызова программы
Далее нажимаем enterи получаем результат программы (см. рис. 10)
Рисунок 10. Демонстрации работы программы
Так же, как было сказано выше, результат так же выводится еще и в файл (см. рис 7). Там видно, какими цветами окрашена каждая из вершин.
Результат работы программы (файл) сохраняется в папке data, которая находится по адресу Имя_папки_с_программой\trunk\data, с названием ХХХ.colored.dot, ХХХ - название изначального файла.
По необходимости, если граф нужно нарисовать, можно воспользоваться программой Graphviz[15].
Graphviz - разработанный специалистами лаборатории AT&T пакет утилит по автоматической визуализации графов, заданных в виде описания на языке dot. Пакет распространяется с открытыми исходными файлами по лицензии CPL (CommonPublicLicense) и работает на многих операционных системах, включая Linux, Mac OS, Unix-подобные, MicrosoftWindows.
Используется при разработке программного обеспечения для визуализации структурированных данных.
В пакет утилит входит программа dot, автоматический визуализатор ориентированных графов, который принимает на вход текстовый файл с представлением графа в виде смежных списков, а на выходе формирует граф в виде графического, векторного или текстового файла.
Входной файл для программы dot является обычным текстовым файлом на специальном языке описания. Структура файла очень простая(см. рис.6).
Программа dot сама распознаёт все связи графа и упорядочивает его таким образом, чтобы было наименьшее количество пересечений.
Приведем пример работы программы Graphviz на нашем примере, который показан на рис. 6. На рис.11 видно как программа нарисовала 5-ти вершинный неориентированный граф.
Рисунок 11. Graphviz
Проведенный эксперимент
Данный эксперимент проводился на графах Мейниеля, то есть на графах имеющих определенную структуру. Она выглядит следующим образом:
Рисунок 12. Графы Мейниеля
То есть у всех таких графов каждый нечетный цикл содержит, по крайней мере, две хорды.
Для рассмотрения были выбраны графы (см. рис. 13), которые удовлетворяют условию графов Мейниеля:
Рисунок 13. Графы, удовлетворяющие структуре графов Мейниеля
Эти графы представляет собой некоторый подкласс класса графов Мейниеля.
На этих графах был проведен эксперимент, который показал что для этого подкласса хроматическое число равно трём.
Ниже приведен график работы программы (см. рис.14):
Рисунок 14. График работы программы
Данный график показывает зависимость времени работы от количества вершин графа. Время работы приведено в секундах.
Заключение
В данной выпускной квалификационной работе бакалавра был изучен алгоритм с перекраской двуцветных компонент. Так же данный алгоритм был запрограммирован и были получены экспериментальные данные по результатам работы программы. По этим экспериментальным данным было выяснено, что алгоритм с перекраской двуцветных компонент дает точную раскраску при использовании графов Мейниеля.
Список литератур?/p>