ДСатур

ДСатур
Сорт	Раскраска графа
Наихудшая пространственная сложность	Затем 2 )

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

Псевдокод

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

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

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

Пример

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

Вертекс $g$ (цвет 1)
Вертекс $a$ (цвет 2)
Вертекс $b$ (цвет 3)
Вертекс $c$ (цвет 2)
Вертекс $d$ (цвет 3)
Вертекс $e$ (цвет 2)
Вертекс $f$ (цвет 3)

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

Производительность

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

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

Ссылки

^ Jump up to: ^а ^б ^с ^д Брелаз, Даниэль (1 апреля 1979 г.). «Новые методы раскраски вершин графа» . Коммуникации АКМ . 22 (4): 251–256. дои : 10.1145/359094.359101 . ISSN 0001-0782 . S2CID 14838769 .
^ Jump up to: ^а ^б ^с ^д ^и Льюис, RMR (2021). Руководство по раскраске графов: алгоритмы и приложения . Тексты по информатике (2-е изд.). Берлин: Шпрингер. дои : 10.1007/978-3-030-81054-2 . ISBN 978-3-030-81053-5 . S2CID 57188465 .
^ Кубале, изд. (2004). Раскраски графов (Том 352) . Провиденс: Американское математическое общество. п. 13. ISBN 978-0-8218-3458-9 .
^ Льюис, Рид (19 января 2019 г.). «Конструктивные алгоритмы раскраски графов» . youtube.com . Событие происходит в 3:49.

Внешние ссылки

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

[:0-1] Jump up to: ^а ^б ^с ^д Брелаз, Даниэль (1 апреля 1979 г.). «Новые методы раскраски вершин графа» . Коммуникации АКМ . 22 (4): 251–256. дои : 10.1145/359094.359101 . ISSN 0001-0782 . S2CID 14838769 .

[:1-2] Jump up to: ^а ^б ^с ^д ^и Льюис, RMR (2021). Руководство по раскраске графов: алгоритмы и приложения . Тексты по информатике (2-е изд.). Берлин: Шпрингер. дои : 10.1007/978-3-030-81054-2 . ISBN 978-3-030-81053-5 . S2CID 57188465 .

[3] Кубале, изд. (2004). Раскраски графов (Том 352) . Провиденс: Американское математическое общество. п. 13. ISBN 978-0-8218-3458-9 .

[4] Льюис, Рид (19 января 2019 г.). «Конструктивные алгоритмы раскраски графов» . youtube.com . Событие происходит в 3:49.

[1]

[2]

[3]

[4]