DSatur

DSatur — это алгоритм раскраски графов , предложенный Даниэлем Брелазом в 1979 году. [ ^1] Подобно алгоритму жадной раскраски , DSatur раскрашивает вершины графа одну за другой, добавляя ранее неиспользованный цвет при необходимости. После того, как новая вершина раскрашена, алгоритм определяет, какая из оставшихся неокрашенных вершин имеет наибольшее количество цветов в своем окружении, и раскрашивает эту вершину следующей. Брелаз определяет это число как степень насыщенности данной вершины. ^[1] Сокращение термина «степень насыщенности» образует название алгоритма. ^[2] DSatur — это эвристический алгоритм раскраски графов, но при этом выдает точные результаты для двудольных, ^[1] циклических и колесных графов. ^[2] DSatur также упоминается в литературе как насыщенный LF. ^[3]

Пусть «степень насыщенности» вершины будет числом различных цветов, используемых ее соседями. Учитывая простой неориентированный граф , скомпрометировавший множество вершин и множество ребер , алгоритм назначает цвета всем вершинам с помощью цветовых меток . Алгоритм работает следующим образом: ^[4]${\displaystyle G}$${\displaystyle V}$${\displaystyle E}$${\displaystyle 1,2,3,...}$

1. Пусть будет неокрашенной вершиной в с наибольшей степенью насыщения. В случае связей выбираем вершину среди них с наибольшей степенью в подграфе, индуцированном неокрашенными вершинами.${\displaystyle v}$${\displaystyle G}$
2. Назначить наименьшую цветовую метку, не используемую ни одним из соседей.${\displaystyle v}$
3. Если все вершины были окрашены, то конец; в противном случае вернуться к шагу 1.

Шаг 2 этого алгоритма назначает цвета вершинам, используя ту же схему, что и алгоритм жадной раскраски . Основные различия между двумя подходами возникают на шаге 1 выше, где вершины, которые кажутся наиболее «ограниченными», окрашиваются первыми.

Рассмотрим граф, показанный справа. Это граф-колесо , и поэтому он будет оптимально раскрашен алгоритмом DSatur. Выполнение алгоритма приводит к выбору и раскрашиванию вершин следующим образом. (В этом примере, где возникают связи в обеих эвристиках DSatur, выбирается вершина с наименьшей лексикографической маркировкой среди них.)${\displaystyle G=(V,E)}$

1. Вершина (цвет 1)${\displaystyle г}$
2. Вершина (цвет 2)${\displaystyle а}$
3. Вершина (цвет 3)${\displaystyle б}$
4. Вершина (цвет 2)${\displaystyle с}$
5. Вершина (цвет 3)${\displaystyle д}$
6. Вершина (цвет 2)${\displaystyle е}$
7. Вершина (цвет 3)${\displaystyle f}$

Это дает окончательное трехцветное решение .${\displaystyle {\mathcal {S}}=\{\{g\},\{a,c,e\},\{b,d,f\}\}}$

Худшая сложность DSatur составляет , где — количество вершин в графе. Это связано с тем, что процесс выбора следующей вершины для окраски занимает время, и этот процесс выполняется раз. Алгоритм также может быть реализован с использованием двоичной кучи для хранения степеней насыщенности, работающей в , или с использованием кучи Фибоначчи, где — количество ребер в графе. ^[2] Это обеспечивает гораздо более быстрые прогоны с разреженными графами. ${\displaystyle O(n^{2})}$${\displaystyle n}$${\displaystyle O(n)}$${\displaystyle n}$${\displaystyle O((n+m)\log n)}$${\displaystyle O(m+n\log n)}$${\displaystyle м}$

Известно, что DSatur точен для двудольных графов ^[1] , а также для циклических и колесных графов. ^[2] В эмпирическом сравнении, проведенном Льюисом в 2021 году, DSatur дал значительно лучшие раскраски вершин, чем жадный алгоритм на случайных графах с вероятностью ребра , в то же время давая значительно худшие раскраски, чем рекурсивный алгоритм наибольшего первого элемента . ^[2]${\displaystyle p=0.5}$

• Высокопроизводительные алгоритмы раскраски графов Набор алгоритмов раскраски графов (реализованных на языке C++), использованных в книге «Руководство по раскраске графов: алгоритмы и приложения» (Springer International Publishers, 2021).
• Реализация алгоритма DSatur на языке C++, представленная в статье «Алгоритм DSatur для раскраски графов», Geeks for Geeks (2021)