Жадная раскраска - Greedy coloring

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

При изучении раскраска графика проблемы в математика и Информатика, а жадная окраска или же последовательная окраска^[1] это раскраска вершины из график сформированный жадный алгоритм который последовательно рассматривает вершины графа и назначает каждой вершине свой первый доступный цвет. Жадные раскраски можно найти за линейное время, но они, как правило, не используют минимально возможное количество цветов.

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

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

Алгоритм

Жадную раскраску для данного порядка вершин можно вычислить с помощью алгоритм что работает в линейное время. Алгоритм обрабатывает вершины в заданном порядке, присваивая каждой из них цвет по мере ее обработки. Цвета могут быть представлены числами ${displaystyle 0,1,2, dots}$ и каждой вершине дается цвет с наименьшее число, которое еще не использовалось одним из его соседей. Чтобы найти наименьший доступный цвет, можно использовать массив для подсчета количества соседей каждого цвета (или, альтернативно, для представления набора цветов соседей), а затем сканировать массив, чтобы найти индекс своего первого нуля.^[2]

В Python, алгоритм можно выразить как:

def first_available(color_list):    "" "Вернуть наименьшее неотрицательное целое число, не входящее в указанный список цветов." ""    color_set = набор(color_list)    считать = 0    пока Истинный:        если считать нет в color_set:            возвращаться считать        считать += 1        def greedy_color(грамм, порядок):    "" "Найдите жадную раскраску G в указанном порядке.    Предполагается, что представление G похоже на https://www.python.org/doc/essays/graphs/    в разрешении перебора соседей узла / вершины с помощью «for w in G [node]».    Возвращаемое значение - словарь, отображающий вершины в их цвета. "" "    цвет = диктовать()    за узел в порядок:        used_neighbour_colors = [цвет[номер] за номер в грамм[узел]                                 если номер в цвет]        цвет[узел] = first_available(used_neighbour_colors)    возвращаться цвет

В first_available подпрограмма занимает время, пропорциональное длине ее списка аргументов, потому что она выполняет два цикла: один по самому списку, а другой по списку счетчиков одинаковой длины. Время выполнения общего алгоритма раскраски определяется вызовами этой подпрограммы. Каждое ребро в графе вносит свой вклад только в один из этих вызовов, один для конечной точки ребра, который находится позже в порядке вершин. Следовательно, сумма длин аргументов приводит к first_available, и общее время алгоритма пропорциональны количеству ребер в графе.^[2]

Альтернативный алгоритм, производящий такую ​​же окраску,^[3] состоит в том, чтобы выбрать наборы вершин каждого цвета, по одному цвету за раз. В этом методе каждый цветовой класс ${displaystyle C}$ выбирается сканированием вершин в заданном порядке. Когда это сканирование обнаруживает неокрашенную вершину ${displaystyle v}$ у которого нет соседа ${displaystyle C}$, он добавляет ${displaystyle v}$ к ${displaystyle C}$. Таким образом, ${displaystyle C}$ становится максимальное независимое множество среди вершин, которым еще не были присвоены меньшие цвета. Таким образом алгоритм неоднократно находит классы цветов, пока не будут окрашены все вершины. Однако он включает в себя несколько сканирований графика, по одному сканированию для каждого цветового класса, вместо описанного выше метода, который использует только одно сканирование.^[4]

Выбор заказа

Различный порядок вершин графа может привести к тому, что жадная раскраска будет использовать разное количество цветов, от оптимального количества цветов до, в некоторых случаях, количества цветов, которое пропорционально количеству вершин в графе. например, граф короны (граф, составленный из двух непересекающиеся множества из п/2 вершины {а₁, а₂, ...} и {б₁, б₂, ...} путем подключения а_я к б_j в любое время я ≠ j) может быть особенно плохим случаем для жадной окраски. С порядком вершин а₁, б₁, а₂, б₂, ..., жадная раскраска будет использовать п/2 цвета, по одному цвету для каждой пары (а_я, б_я). Однако оптимальное количество цветов для этого графа - два, один цвет для вершин а_я и еще один для вершин б_я.^[5] Также существуют графы, в которых с большой вероятностью случайный порядок вершин приводит к количеству цветов, намного превышающему минимальный.^[6] Следовательно, при жадной раскраске важно тщательно выбирать порядок вершин.

Хорошие заказы

Вершины любого графа всегда можно упорядочить так, чтобы жадный алгоритм давал оптимальную раскраску. Ведь при любой оптимальной раскраске можно упорядочить вершины по цвету. Затем, когда кто-то использует жадный алгоритм с этим порядком, результирующая окраска автоматически становится оптимальной.^[7] Однако, поскольку оптимальная раскраска графа НП-полный, любая подзадача, которая позволила бы быстро решить эту проблему, включая поиск оптимального порядка для жадной окраски, является NP-жесткий.^[8]

В интервальные графики и хордовые графы, если вершины упорядочены в обратном порядке идеальный порядок исключения, то более ранние соседи каждой вершины образуют клика. Это свойство заставляет жадную окраску производить оптимальную окраску, потому что она никогда не использует больше цветов, чем требуется для каждой из этих групп. Порядок исключения можно найти в линейном времени, если он существует.^[9]

Более того, любой идеальный порядок исключения наследственно оптимальный, что означает, что он оптимален как для самого графа, так и для всех его индуцированные подграфы. В идеально упорядочиваемые графики (который включает в себя хордовые графы, графики сопоставимости, и дистанционно-наследственные графы ) определяются как графы, имеющие наследственно оптимальный порядок.^[10] Распознавание идеально упорядочиваемых графов также является NP-полным.^[11]

Плохие заказы

Количество цветов, полученных в результате жадной раскраски для наихудшего порядка данного графа, называется его Гранди номер.^[12]Как трудно найти хороший порядок вершин для жадной раскраски, так и найти плохой порядок вершин. Это NP-полное определение для данного графа грамм и номер k, существует ли упорядоченность вершин грамм что заставляет жадный алгоритм использовать k или больше цветов. В частности, это означает, что трудно найти худший заказ для грамм.^[12]

Графики, для которых порядок не важен

В хорошо раскрашенные графики - графы, для которых все раскраски вершин дают одинаковое количество цветов. Это количество цветов на этих графиках равно как хроматическому числу, так и числу Гранди.^[12] Они включают кографы, а именно графы, в которых все индуцированные подграфы хорошо окрашены.^[13] Однако это совместно NP-полный чтобы определить, хорошо ли раскрашен график.^[12]

Если случайный граф взят из Модель Эрдеша – Реньи с постоянной вероятностью включения каждого ребра, то любой порядок вершин, выбранный независимо от ребер графа, приводит к раскраске, количество цветов которой близко к удвоенному оптимальному значению, с большой вероятностью Остается неизвестным, существует ли какой-либо метод полиномиального времени для нахождения значительно лучших раскраски этих графов.^[3]

Вырождение

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

Поскольку трудно найти оптимальный порядок вершин, использовались эвристики, которые пытаются уменьшить количество цветов, не гарантируя при этом оптимальное количество цветов. Обычно для жадной раскраски используется порядок выбора вершины v минимум степень, закажите подграф с v удаленный рекурсивно, а затем поместите v последний в заказе. Наибольшая степень удаленной вершины, с которой сталкивается этот алгоритм, называется вырождение графа, обозначенный d. В контексте жадной раскраски та же самая стратегия упорядочивания также называется наименьшим последним упорядочением.^[14] Этот порядок вершин и вырождение можно вычислить за линейное время.^[15]Его можно рассматривать как улучшенную версию более раннего метода упорядочения вершин, упорядочения по наибольшему первому, который сортирует вершины в порядке убывания их степеней.^[16]

С упорядочиванием вырождения жадная раскраска будет использовать не более d + 1 цвета. Это потому, что при раскрашивании каждая вершина будет иметь не более d уже окрашенные соседи, поэтому одни из первых d + 1 цвета будут бесплатными для его использования.^[17] Жадная раскраска с упорядочением вырождения позволяет находить оптимальные раскраски для определенных классов графов, включая деревья, псевдолеса, и графы короны.^[18] Маркосян, Гаспарян и Рид (1996) определить график ${displaystyle G}$ быть ${displaystyle eta}$-совершенно, если для ${displaystyle G}$ и каждый индуцированный подграф из ${displaystyle G}$, хроматическое число равно вырождению плюс один. Для этих графов всегда оптимален жадный алгоритм с упорядочением по вырождению.^[19]Каждый ${displaystyle eta}$-совершенный граф должен быть граф без четных дырок, поскольку четные циклы имеют хроматическое число два и вырождение два, что не соответствует равенству в определении ${displaystyle eta}$-совершенные графики. Если граф и его дополнительный граф оба без четных отверстий, они оба ${displaystyle eta}$-идеально. Графики, которые являются идеальные графики и ${displaystyle eta}$-совершенные графы - это в точности хордовые графы. В более общем случае на графах без четных дырок упорядочение по вырожденности приближает оптимальную раскраску с точностью не более чем вдвое большего оптимального числа цветов; то есть его коэффициент аппроксимации равно 2.^[20] На графы единичного диска его коэффициент аппроксимации равен 3.^[21] В треугольная призма - наименьший граф, для которого один из порядков вырождения приводит к неоптимальной раскраске, а квадратная антипризма - наименьший граф, который нельзя оптимально раскрасить с помощью любого из его порядков вырождения.^[18]

Адаптивные заказы

Brélaz (1979) предлагает стратегию, называемую DSatur, для упорядочивания вершин в жадной раскраске, которая чередует построение упорядочения с процессом раскраски. В его версии алгоритма жадной раскраски следующая вершина, которую нужно раскрасить на каждом шаге, выбирается как вершина с наибольшим количеством различных цветов в ее район. В случае ничьей из связанных вершин выбирается вершина максимальной степени в подграфе неокрашенных вершин. Отслеживая наборы соседних цветов и их мощности на каждом шаге можно реализовать этот метод за линейное время.^[22]

Этим методом можно подобрать оптимальные раскраски для двудольные графы,^[23] все кактус графики, все колесные графики, все графы не более чем на шести вершинах, и почти каждый ${displaystyle k}$-раскрашиваемый граф.^[24] Несмотря на то что Левек и Маффре (2005) изначально утверждалось, что этот метод находит оптимальные цвета для Графики Мейниеля, позже они нашли контрпример этому утверждению.^[25]

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

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

Выбор онлайн

Альтернативные стратегии выбора цвета изучались в рамках онлайн-алгоритмы. В задаче онлайн-раскраски графа вершины графа предоставляются алгоритму раскраски по одной в произвольном порядке; алгоритм должен выбрать цвет для каждой вершины, основываясь только на цветах и ​​смежности между уже обработанными вершинами. В этом контексте качество стратегии выбора цвета оценивается по конкурентное соотношение, соотношение между количеством используемых цветов и оптимальным количеством цветов для данного графика.^[26]

Если не заданы дополнительные ограничения на графике, оптимальное соотношение конкуренции лишь слегка сублинейно.^[27] Однако для интервальные графики, возможно постоянное конкурентное соотношение,^[28] в то время как для двудольные графы и разреженные графики может быть достигнуто логарифмическое соотношение. В самом деле, для разреженных графов стандартная стратегия жадного раскраски, заключающаяся в выборе первого доступного цвета, обеспечивает это конкурентное соотношение, и можно доказать соответствие нижней границы конкурентного отношения любого онлайн-алгоритма раскраски.^[26]

Экономная окраска

А экономная окраскадля данного графа и порядка вершин определено как раскраска, производимая жадным алгоритмом, который раскрашивает вершины в заданном порядке и вводит новый цвет только тогда, когда все предыдущие цвета смежны с данной вершиной, но могут выбирать какой цвет использовать (вместо того, чтобы всегда выбирать самый маленький), когда можно повторно использовать существующий цвет. В заказанный хроматический номер - наименьшее количество цветов, которое может быть получено таким способом для данного порядка, а охроматическое число - наибольшее упорядоченное хроматическое число среди всех раскраски вершин данного графа. Несмотря на различное определение, охроматическое число всегда равно числу Гранди.^[29]

Приложения

Поскольку это быстро и во многих случаях может использоваться мало цветов, жадная окраска может использоваться в приложениях, где требуется хорошая, но не оптимальная окраска графа. Одним из первых применений жадного алгоритма было решение таких проблем, как планирование курса, в котором набор задач должен быть назначен заданному набору временных интервалов, чтобы избежать назначения несовместимых задач на один и тот же временной интервал.^[4]Его также можно использовать в компиляторы за распределение регистров, применяя его к графу, вершины которого представляют значения, которые должны быть присвоены регистрам, и чьи ребра представляют конфликты между двумя значениями, которые не могут быть присвоены одному и тому же регистру.^[30] Во многих случаях эти интерференционные графики хордовые графы, позволяя жадной раскраске производить оптимальное назначение регистров.^[31]

В комбинаторная теория игр, для беспристрастная игра дано в явном виде как ориентированный ациклический граф чьи вершины представляют игровые позиции, а чьи края представляют собой допустимые переходы из одной позиции в другую, алгоритм жадной раскраски (с использованием обратной стороны топологический порядок графика) вычисляет ним-стоимость каждой позиции. Эти значения могут использоваться для определения оптимальной игры в любой отдельной игре или в любом дизъюнктивная сумма игр.^[32]

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

Примечания

Рекомендации