Жадная раскраска ("g;ugx jgvtjgvtg)

Две раскраски жадным алгоритмом одного и того же графа, в которых используется различный порядок прохода вершин. Правый пример показывает, что граф с n вершинами, который можно раскрасить в два цвета, может быть раскрашен жадным алгоритмом в $n/2$ цветов.

Жадная раскраска в теории графов — раскраска вершин неориентированного графа, созданная жадным алгоритмом, который проходит вершины графа в некоторой предопределённой последовательности и назначает каждой вершине первый доступный цвет. Жадные алгоритмы, в общем случае, не дают минимально возможное число цветов, однако они используются в математике в качестве техники доказательств других результатов, относящихся к раскраске, а также в компьютерных программах для получения раскраски с небольшим числом цветов.

Жадные алгоритмы не всегда хороши

Корона (полный двудольный граф K_n,n с удалёнными рёбрами совершенного паросочетания) является особенно плохим случаем для жадного алгоритма — если в последовательности вершин поместить подряд две вершины, принадлежащие удалённому ребру из паросочетания, жадный алгоритм использует n цветов, в то время, как оптимальным числом для такого графа является два цвета. Существуют также графы, для которых с большой вероятностью случайно выбранная последовательность вершин приведёт к использованию числа цветов, существенно большему минимально необходимого. Таким образом, очень важно осторожно выбирать последовательность, в которой вершины проходятся жадным алгоритмом.

Для заданного графа G и числа k, определение, существует ли порядок вершин графа G, который приводит к использованию жадным алгоритмом k и более цветов, является NP-полной задачей. Это, в частности, означает, что трудно найти наихудший случай для графа G.

Оптимальное упорядочивание

Вершины любого графа всегда можно упорядочить таким образом, что жадный алгоритм даст оптимальную раскраску. Так, для любой оптимальной раскраски, перенумеруем сначала (в убывающем порядке) вершины из наименьшего по размеру множества одинаково выкрашенных вершин. Затем перенумеруем второе по размеру множество, и так далее. Если теперь применить жадный алгоритм с таким порядком вершин, полученная раскраска будет оптимальной. Более строго, для графов, обладающих совершенным порядком (в это семейство входят хордальные графы, графы сравнимости и дистанционно-наследуемые графы) существует порядок, который оптимален как для самого графа, так и для всех его порождённых подграфов. Однако нахождение этого оптимального порядка для произвольного графа является NP-полной задачей (хотя бы потому, что её решение можно использовать для получения оптимальной раскраски графа, то есть решения NP-полной задачи), и определение, существует ли в графе совершенное упорядочение вершин, тоже является NP-полной задачей. По этой причине для раскрашивания графа с целью уменьшения числа цветов используются эвристические алгоритмы, хотя они и не дают оптимального числа цветов.

Эвристические стратегии упорядочения

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

Для графа с максимальной степенью Δ любой жадный алгоритм использует максимум Δ + 1 цветов. Теорема Брукса утверждает, что за исключением двух исключений (клики и нечётные циклы) для раскраски необходимо не более Δ цветов. Одно из доказательств теоремы Брукса использует упорядочение вершин, при котором первые две вершины смежны конечной вершине, но не смежны между собой. Такая последовательность имеет для каждой вершины по меньшей мере одну предшествующую вершину, принадлежащую окрестности. Для последовательности вершин с такими свойствами жадный алгоритм использует максимум Δ цветов.

Альтернативные схемы выбора цветов

Можно построить жадный алгоритм, в котором вершины заданного графа раскрашиваются в предопределённой последовательности, но в котором цвет выбирается не обязательно первый попавшийся из свободных цветов. В качестве альтернативной стратегии выбора цвета изучались подходы с онлайновыми алгоритмами. В задаче онлайновой раскраски графа вершины графа подаются алгоритму раскраски последовательно по одной в произвольном порядке. Алгоритм должен выбрать цвет каждой вершины, опираясь только на цвета и смежность уже обработанных вершин. В этом контексте качество стратегии выбора цветов измеряется конкурентным отношением, отношением числа использованных цветов к оптимальному числу цветов раскраски графа.

Если не задано никаких других ограничений на графе, оптимальное конкурентное отношение лишь слегка сублинейно. Однако для интервальных графов в качестве конкурентного отношения возможна константа, в то время как для двудольных и разреженных графов можно получить логарифмическое отношение. Более того, для разреженных графов обычная стратегия выбора первого доступного цвета даёт эту оценку и можно показать, что эта оценка является нижней для конкурентного отношения любого онлайнового алгоритма раскраски.

Литература

• Václav Chvátal. Topics in Perfect Graphs / Claude Berge, Václav Chvátal. — Amsterdam: North-Holland, 1984. — Т. 21. — С. 63—68. — (Annals of Discrete Mathematics). Как цитировано в Maffray, 2003.
• Sandy Irani. Coloring inductive graphs on-line // Algorithmica. — 1994. — Т. 11, вып. 1. — С. 53—72. — doi:10.1007/BF01294263.
• H. A. Kierstead, W. A. Trotter. An extremal problem in recursive combinatorics // Congress. Numer.. — 1981. — Т. 33. — С. 143—153. Как цитировано в Irani, 1994.
• Luděk Kučera. The greedy coloring is a bad probabilistic algorithm // Journal of Algorithms. — 1991. — Т. 12, вып. 4. — С. 674—684. — doi:10.1016/0196-6774(91)90040-6.
• D. S. Johnson. Proc. 5th Southeastern Conf. Combinatorics, Graph Theory and Computation. — Winnipeg: Utilitas Mathematica, 1979. — С. 513—527. Как цитировано в Maffray, 2003.
• L. Lovász. Three short proofs in graph theory // Journal of Combinatorial Theory, Series B. — 1975. — Т. 19, вып. 3. — С. 269—271. — doi:10.1016/0095-8956(75)90089-1.
• L. Lovász, M. E. Saks, W. A. Trotter. An on-line graph coloring algorithm with sublinear performance ratio // Discrete Mathematics. — 1989. — Т. 75, вып. 1–3. — С. 319—325. — doi:10.1016/0012-365X(89)90096-4.
• Frédéric Maffray. Recent Advances in Algorithms and Combinatorics / Bruce A. Reed, Sales Cláudia L. — Springer-Verlag, 2003. — Т. 11. — С. 65–84. — (CMS Books in Mathematics). — ISBN 0-387-95434-1. — doi:10.1007/0-387-22444-0_3.
• Matthias Middendorf, Frank Pfeiffer. On the complexity of recognizing perfectly orderable graphs // Discrete Mathematics. — 1990. — Т. 80, вып. 3. — С. 327—333. — doi:10.1016/0012-365X(90)90251-C.
• Maciej M. Sysło. Sequential coloring versus Welsh-Powell bound // Discrete Mathematics. — 1989. — Т. 74, вып. 1—2. — С. 241—243. — doi:10.1016/0012-365X(89)90212-4.
• S. Vishwanathan. Proc. 31st IEEE Symp. Foundations of Computer Science (FOCS '90). — 1990. — Т. 2. — С. 464—469. — ISBN 0-8186-2082-X. — doi:10.1109/FSCS.1990.89567.
• D. J. A. Welsh, M. B. Powell. An upper bound for the chromatic number of a graph and its application to timetabling problems // The Computer Journal. — 1967. — Т. 10, вып. 1. — С. 85—86. — doi:10.1093/comjnl/10.1.85.
• Manouchehr Zaker. Results on the Grundy chromatic number of graphs // Discrete Mathematics. — 2006. — Т. 306, вып. 2—3. — С. 3166—3173. — doi:10.1016/j.disc.2005.06.044.