Введение 3
Постановка задачи 3
Глава 1. Используемые термины 4
Глава 2. Условные обозначения 4
Глава 3. Вспомогательные алгоритмы и структуры данных 5
3.1. Битовые множества 5
3.2. Алгоритм Брона-Кербоша 6
Глава 4. Алгоритм Олемского 8
4.1. Описание множеств и переменных 8
4.2. Описание проверок 10
4.3. Описание алгоритма 11
4.4. Псевдокод алгоритма 15
Глава 5. Алгоритмы перебора независимых множеств 20
5.1. Перебор всех возможных вариантов 20
5.2. Оптимизированный перебор 21
5.3. Перебор в матричном виде 23
Глава 6. Измерение быстродействия алгоритмов 26
6.1. Алгоритм Олемского И.В 26
6.2. Алгоритм перебора независимых множеств 29
6.3. Оптимизированный перебор 32
6.4. Перебор в матричном виде 34
Глава 7. Сравнение быстродействия алгоритмов 36
Глава 8. Заключение 40
Список литературы 41
Впервые проблема раскраски графа была официально поднята на встрече Лондонского математического сообщества в 1878 году, где она рассматривалась в контексте задачи о раскраске карты. В 1970-х годах раскраска графа стала рассматриваться как алгоритмическая проблема.
Данная задача постоянно исследуется по двум основным причинам:
1. Она находит применение в реальных задачах, например в составлении расписаний[1], распределение регистров в микропроцессорах^], распараллеливание численных методов[3].
2. На данный момент не найдено точного и эффективного алгоритма её решения, т.к. доказано что задача о раскраске является NP-полной.
Точные алгоритмы в основном используют полный перебор возможных вариантов раскраски. Таким образом, основным отличием таких алгоритмов является порядок перебора и используемые отсечения.
Например, в данной работе рассматривается алгоритм основанный на переборе максимальных независимых множеств, описанный в книге Новикова Ф.А.[4] и две его модификации.
Главным объектом исследования является разработанный Олемким И.В. алгоритм, и его сравнение с другими существующими алгоритмами.
В результате проделанной работы были реализованы[14] алгоритмы раскраски графа Олемского И.В. и Новикова Ф.А. Было доказано утверждение, позволившее разработать и реализовать две модификации алгоритма Новикова Ф.А.
Для всех реализованных алгоритмов было измерено время работы на графах с различным число вершин и плотностью. Результаты были представлены в виде трёхмерного графика зависимости времени от числа вершин и плотности. По полученным результатам было решено провести прямое сравнение алгоритма Олемского И.В. и двух модификаций алгоритма Новикова Ф.А.
Сравнение показало, что алгоритм Олемского И.В. работает дольше на графах малой размерности. Однако имеет более низкую скорость прироста требуемого на раскраску времени. Поэтому при раскраске небольших графов с числом вершин менее 12 применение модифицированных алгоритмов Новикова Ф.А. предпочтительнее, но с ростом числа вершин алгоритм Олемского И.В. становится более рациональным выбором.
