Жадная раскраска

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

• Шаблон:Книга Как цитировано в Шаблон:Harvnb.
• Шаблон:Статья
• Шаблон:Статья Как цитировано в Шаблон:Harvnb.
• Шаблон:Статья
• Шаблон:Статья Как цитировано в Шаблон:Harvnb.
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья