|
Жадная раскраска Жадная раскраска в теории графов — раскраска вершин неориентированного графа, созданная жадным алгоритмом, который проходит вершины графа в некоторой предопределённой последовательности и назначает каждой вершине первый доступный цвет. Жадные алгоритмы, в общем случае, не дают минимально возможное число цветов, однако они используются в математике в качестве техники доказательств других результатов, относящихся к раскраске, а также в компьютерных программах для получения раскраски с небольшим числом цветов. Жадные алгоритмы не всегда хорошиКорона (полный двудольный граф Kn,n с удалёнными рёбрами совершенного паросочетания) является особенно плохим случаем для жадного алгоритма — если в последовательности вершин поместить подряд две вершины, принадлежащие удалённому ребру из паросочетания, жадный алгоритм использует n цветов, в то время, как оптимальным числом для такого графа является два цвета. Существуют также графы, для которых с большой вероятностью случайно выбранная последовательность вершин приведёт к использованию числа цветов, существенно большему минимально необходимого[1]. Таким образом, очень важно осторожно выбирать последовательность, в которой вершины проходятся жадным алгоритмом. Для заданного графа G и числа k, определение, существует ли порядок вершин графа G, который приводит к использованию жадным алгоритмом k и более цветов, является NP-полной задачей. Это, в частности, означает, что трудно найти наихудший случай для графа G[2]. Оптимальное упорядочиваниеВершины любого графа всегда можно упорядочить таким образом, что жадный алгоритм даст оптимальную раскраску. Так, для любой оптимальной раскраски, перенумеруем сначала (в убывающем порядке) вершины из наименьшего по размеру множества одинаково выкрашенных вершин. Затем перенумеруем второе по размеру множество, и так далее. Если теперь применить жадный алгоритм с таким порядком вершин, полученная раскраска будет оптимальной. Более строго, для графов, обладающих совершенным порядком (в это семейство входят хордальные графы, графы сравнимости и дистанционно-наследуемые графы) существует порядок, который оптимален как для самого графа, так и для всех его порождённых подграфов[3]. Однако нахождение этого оптимального порядка для произвольного графа является NP-полной задачей (хотя бы потому, что её решение можно использовать для получения оптимальной раскраски графа, то есть решения NP-полной задачи), и определение, существует ли в графе совершенное упорядочение вершин, тоже является NP-полной задачей[4]. По этой причине для раскрашивания графа с целью уменьшения числа цветов используются эвристические алгоритмы, хотя они и не дают оптимального числа цветов. Эвристические стратегии упорядоченияОбычно для упорядочения вершин для жадного алгоритма выбирают вершину v с минимальной степенью, упорядочивают остальные вершины, а v помещают в конец списка. Если любой подграф графа G содержит вершины со степенью, не превосходящей d, то алгоритм жадной раскраски для такого порядка вершин использует максимум d + 1 цветов[5]. Наименьшее из d обычно называется вырожденностью графа. Для графа с максимальной степенью Δ любой жадный алгоритм использует максимум Δ + 1 цветов. Теорема Брукса утверждает, что за исключением двух исключений (клики и нечётные циклы) для раскраски необходимо не более Δ цветов. Одно из доказательств теоремы Брукса использует упорядочение вершин, при котором первые две вершины смежны конечной вершине, но не смежны между собой. Такая последовательность имеет для каждой вершины по меньшей мере одну предшествующую вершину, принадлежащую окрестности. Для последовательности вершин с такими свойствами жадный алгоритм использует максимум Δ цветов[6]. Альтернативные схемы выбора цветовМожно построить жадный алгоритм, в котором вершины заданного графа раскрашиваются в предопределённой последовательности, но в котором цвет выбирается не обязательно первый попавшийся из свободных цветов. В качестве альтернативной стратегии выбора цвета изучались подходы с онлайновыми алгоритмами[англ.]. В задаче онлайновой раскраски графа вершины графа подаются алгоритму раскраски последовательно по одной в произвольном порядке. Алгоритм должен выбрать цвет каждой вершины, опираясь только на цвета и смежность уже обработанных вершин. В этом контексте качество стратегии выбора цветов измеряется конкурентным отношением[англ.], отношением числа использованных цветов к оптимальному числу цветов раскраски графа. Если не задано никаких других ограничений на графе, оптимальное конкурентное отношение лишь слегка сублинейно[7]. Однако для интервальных графов в качестве конкурентного отношения возможна константа[8], в то время как для двудольных и разреженных графов можно получить логарифмическое отношение[9]. Более того, для разреженных графов обычная стратегия выбора первого доступного цвета даёт эту оценку и можно показать, что эта оценка является нижней для конкурентного отношения любого онлайнового алгоритма раскраски[9]. ПримечанияЛитература
|
