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

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

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

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

Алгоритм

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

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

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

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

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

Выбор заказа

Разный порядок вершин графа может привести к тому, что при жадной раскраске будет использоваться разное количество цветов: от оптимального количества цветов до, в некоторых случаях, количества цветов, пропорционального количеству вершин в графе. Например, коронный граф (граф, образованный из двух непересекающихся наборов из $n /2$ вершин ${a 1, a 2, ...$ } и ${b 1, b 2, ...$ } путем соединения $a i$ с $b j$ всякий раз, когда $i \neq j$ ) может быть особенно плохим случаем жадной раскраски. При порядке вершин $a 1, b 1, a 2, b 2, ...$ жадная раскраска будет использовать $n /2$ цветов, по одному цвету для каждой пары $(a i, b i)$ . Однако оптимальное количество цветов для этого графа — два: один цвет для вершин $a i$ , а другой — для вершин $b i$ . ^[5] Также существуют графы, в которых случайно выбранный порядок вершин с большой вероятностью приводит к количеству цветов, значительно превышающему минимальное. ^[6] Поэтому при жадной раскраске очень важно тщательно выбирать порядок вершин.

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

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

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

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

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

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

Графы, для которых порядок не имеет значения

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

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

Вырождение

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

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

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

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

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

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

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

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

Онлайн подбор

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

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

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

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

Приложения

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

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

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

Примечания

^ Митчем (1976).
^ Аб Хоанг и Шритаран (2016), теорема 28.33, стр. 738; Хусфельдт (2015), Алгоритм G
^ ab Frieze & McDiarmid (1997).
^ ab Welsh & Powell (1967).
^ Джонсон (1974); Хусфельдт (2015).
^ Кучера (1991); Хусфельдт (2015).
^ Хусфельдт (2015).
^ Маффрей (2003).
^ Роуз, Люкер и Тарьян (1976).
^ Хватал (1984); Хусфельдт (2015).
^ Миддендорф и Пфайффер (1990).
^ abcd Закер (2006).
^ Кристен и Селков (1979).
^ Митчем (1976); Хусфельдт (2015).
^ Матула и Бек (1983).
^ Уэлш и Пауэлл (1967); Хусфельдт (2015).
^ Матула (1968); Секерес и Уильф (1968).
^ Аб Косовский и Манушевский (2004).
^ Маркосян, Гаспарян и Рид (1996); Маффрэй (2003).
^ Маркосян, Гаспарян и Рид (1996).
^ Греф, Штумпф и Вайсенфельс (1998).
^ Брелаз (1979); Левек и Мафре (2005).
^ Брелаз (1979).
^ Янчевский и др. (2001).
^ Левек и Мафре (2005).
^ аб Ирани (1994).
^ Ловас, Сакс и Троттер (1989); Вишванатан (1992).
^ Кирстед и Троттер (1981).
^ Симмонс (1982); Эрдеш и др. (1987).
^ Полетто и Саркар (1999). Хотя Полетто и Саркар описывают свой метод распределения регистров как не основанный на раскраске графа, он похож на жадную раскраску.
^ Перейра и Палсберг (2005).
^ Например, см. раздел 1.1 Ниваша (2006).
^ Ловас (1975).