Алгоритм DSatur для раскраски графа
Раскраска графа — это задача присвоения цветов вершинам графа таким образом, чтобы:
- парам смежных вершин присваиваются разные цвета, и
- количество различных цветов, используемых на графике, минимально.
Следующий график раскрашен с использованием всего трех цветов (здесь красный, синий и зеленый). На самом деле это минимальное количество цветов, необходимое для данного конкретного графа, то есть мы не можем раскрасить этот граф, используя менее трех цветов, при этом гарантируя, что соседние вершины окрашены по-разному.
Минимальное количество цветов, необходимое для раскрашивания графа G , известно как хроматическое число и обычно обозначается χ(G) . Определение хроматического числа графа NP-трудно. Соответствующая проблема принятия решения о том, существует ли k -раскраска для графа G, также является NP-полной.
Подобные посты на этом сайте уже описывали жадный алгоритм раскраски графа. Этот алгоритм прост в применении, но количество цветов, используемых в его решениях, очень сильно зависит от порядка рассмотрения вершин. В лучшем случае правильное упорядочивание даст решение, использующее χ(G) цветов; однако неправильный порядок может привести к решениям с использованием многих дополнительных цветов.
Алгоритм DSatur (сокращенно от « степень насыщения ») имеет сходное поведение с алгоритмом Greedy. Разница заключается в том, как он генерирует порядок вершин. В частности, следующая за цветом вершина всегда выбирается как неокрашенная вершина с наивысшей степенью насыщенности . Степень насыщенности вершины определяется как количество различных цветов, назначенных в данный момент соседним вершинам. Другие правила также используются для разрыва ничьей.
Пусть G — граф с n вершинами и m ребрами. Кроме того, предположим, что мы будем использовать цветовые метки 0, 1, 2, …, n-1 . (В решении никогда не требуется более n цветов). Алгоритм DSatur работает следующим образом
- Пусть v — неокрашенная вершина в G с наибольшей степенью насыщения. В случае равенства выбираем среди них вершину с наибольшей степенью в подграфе, порожденном неокрашенными вершинами. Дальнейшие связи могут быть разорваны произвольно.
- Назначьте v цвету i , где i — наименьшее целое число из набора {0, 1, 2, …, n} , которое в настоящее время не назначено ни одному соседу v .
- Если остались неокрашенные вершины, повторите все шаги еще раз, иначе закончите на этом шаге.
Алгоритм DSatur похож на алгоритм Greedy в том, что после выбора вершины ей назначается самая низкая цветовая метка, не назначенная ни одному из ее соседей. Таким образом, действия шага 1 обеспечивают основную силу алгоритма, поскольку они отдают приоритет вершинам, которые считаются « наиболее ограниченными », то есть вершинам, которые в настоящее время имеют наименьшее количество доступных для них вариантов цвета. Следовательно, эти «более ограниченные» вершины обрабатываются в первую очередь, что позволяет раскрашивать менее ограниченные вершины позже.
Анализ DSatur
Поскольку алгоритм DSatur генерирует порядок вершин во время выполнения, количество используемых им цветов более предсказуемо, чем в жадном алгоритме. Его решения также имеют меньше цветов, чем решения жадного алгоритма. Одной из особенностей алгоритма является то, что если граф состоит из нескольких компонентов, то все вершины одного компонента будут окрашены до того, как будут рассмотрены другие вершины. DSatur также точен для нескольких топологий графов, включая двудольные графы, графы циклов и графы колес. (С этими графами всегда будет получено решение с использованием цветов χ(G) .)
Общая сложность алгоритма DSatur составляет O(n 2 ) , где n — количество вершин в графе. Этого можно достичь, выполнив n отдельных приложений процесса O(n) , которые:
- Определяет следующую вершину для окрашивания в соответствии с правилами выбора DSatur.
- Раскрашивает эту вершину.
Ниже мы представляем реализацию DSatur на C++, которая работает за время O((n + m) log n) , где m — количество ребер в графе. Это намного быстрее, чем O(n 2 ) для всех графов, кроме самых плотных. Эта реализация включает использование красно-черного двоичного дерева для хранения всех вершин, которые еще не окрашены, вместе с их степенями насыщенности и их степенями в подграфе, порожденном неокрашенными вершинами. Красно-черные деревья — это тип самобалансирующегося двоичного дерева, которое используется с контейнером set в стандартной библиотеке шаблонов C++. Это позволяет выполнять выбор следующей вершины для окрашивания (в соответствии с правилами выбора DSatur) за постоянное время. Он также позволяет вставлять и удалять элементы за логарифмическое время.
Первая часть этой реализации включает инициализацию структур данных. Это включает в себя перебор каждой вершины и заполнение красно-черного дерева. Это занимает O(n log n) времени. В основной части алгоритма красно-черное дерево позволяет выполнять выбор следующей вершины u для окрашивания за константное время. После того, как u был окрашен, элементы, соответствующие неокрашенным соседям u , должны быть обновлены в красно-черном дереве. Выполнение этого для каждой вершины приводит к общему времени выполнения O(m log n) . Следовательно, общее время выполнения равно O((n log n) + (m log n)) = O((n+m) log n) .
Дополнительную информацию об этом и других алгоритмах раскраски графов можно найти в книге: Руководство по раскрашиванию графов: алгоритмы и приложения (2021 г.)