Войти
Две жадные раскраски одного и того же графа короны с использованием разных порядков вершин. Правый пример обобщается на 2-раскрашиваемые графы с n вершинами, где жадный алгоритм расходует n / 2 цветов. При исследовании раскраски графа задач в математике и информатика, жадная раскраска или последовательная раскраска - это раскраска вершин графа, образованного жадный алгоритм, который последовательно рассматривает вершины графа и присваивает каждой вершине свой первый доступный цвет. Жадные раскраски можно найти за линейное время, но они, как правило, не используют минимально возможное количество цветов.
Различный выбор последовательности вершин обычно приводит к разным раскраскам данного графа, поэтому большая часть исследований жадных раскрасок посвящена поиску хорошего упорядочения. Всегда существует порядок, который дает оптимальную раскраску, но, хотя такие порядки можно найти для многих специальных классов графов, их трудно найти в целом. Обычно используемые стратегии для упорядочивания вершин включают размещение вершин с более высокой степенью раньше, чем вершины с более низкой степенью, или выбор вершин с меньшим количеством доступных цветов в пользу вершин с меньшими ограничениями.
Варианты жадной окраски: выберите цвета онлайн, не зная структуры неокрашенной части графика, или выберите цвета, отличные от первого доступного, чтобы уменьшить общее количество цветов. Алгоритмы жадной раскраски применялись к задачам планирования и распределения регистров, анализу комбинаторных игр и доказательствам других математических результатов, включая теорему Брукса о связи между раскраской и степенью. Другие концепции теории графов, полученные из жадных раскрасок, включают число Гранди графа (наибольшее количество цветов, которое можно найти с помощью жадной раскраски) и хорошо раскрашенные графы, графики, для которых все жадные раскраски используют одинаковое количество цветов.
Жадная окраска для данного упорядочение вершин может быть вычислено с помощью алгоритма , который выполняется за линейное время. Алгоритм обрабатывает вершины в заданном порядке, присваивая каждой из них цвет по мере ее обработки. Цвета могут быть представлены числами 
В Python алгоритм может быть выражен как:
def first_available (color_list): "" "Возвращает наименьшее неотрицательное целое число, не входящее в данный список цветов." "" color_set = set (color_list) count = 0 while True: if count not in color_set: return count count + = 1 def greedy_color (G, order): "" "Найдите жадную окраску G в заданном порядке. Представление G предполагается, что это похоже на https://www.python.org/doc/essays/graphs/ в разрешении итерации соседей узла / вершины с помощью "for w in G [node]". Возвращаемое значение - словарь сопоставление вершин с их цветами. "" "color = dict () для узла в порядке: used_neighbour_colors = [цвет [nbr] для nbr в G [узел] если nbr в цвете] цвет [узел] = first_available (used_neighbour_colors) return co lor
Подпрограмма first_availableзанимает время, пропорциональное длине ее списка аргументов, потому что она выполняет два цикла: один по самому списку, а другой по списку счетчиков, имеющий одинаковую длину. Время выполнения общего алгоритма раскраски определяется вызовами этой подпрограммы. Каждое ребро в графе вносит свой вклад только в один из этих вызовов, один для конечной точки ребра, который находится позже в порядке вершин. Следовательно, сумма длин списков аргументов для first_availableи общее время для алгоритма пропорциональны количеству ребер в графе.
Альтернативный алгоритм, производящий одной и той же раскраски, состоит в том, чтобы выбрать наборы вершин каждого цвета, по одному цвету за раз. В этом методе каждый цветовой класс 
Различный порядок отображения вершины графа могут привести к тому, что жадная раскраска будет использовать разное количество цветов, от оптимального количества цветов до, в некоторых случаях, количества цветов, которое пропорционально количеству вершин в графе. Например, коронный граф (граф, образованный двумя непересекающимися наборами из n / 2 вершин {a 1, a 2,...} и {b 1, b 2,...} путем соединения a i с b j всякий раз, когда i ≠ j) может быть особенно плохим случаем для жадной окраски. При порядке вершин a 1, b 1, a 2, b 2,..., жадная раскраска будет использовать n / 2 цвета, по одному цвету для каждой пары (a i, b i). Однако оптимальное количество цветов для этого графа - два: один цвет для вершин a i, а другой - для вершин b i. Также существуют такие графы, в которых с высокой вероятностью случайный порядок вершин приводит к количеству цветов, намного превышающему минимальный. Следовательно, при жадной раскраске важно тщательно выбирать порядок вершин.
Вершины любого графа всегда можно упорядочить таким образом, чтобы жадный алгоритм давал оптимальную раскраску. Ведь при любой оптимальной раскраске можно упорядочить вершины по цвету. Затем, когда с этим порядком используется жадный алгоритм, результирующая окраска автоматически становится оптимальной. Однако, поскольку оптимальная раскраска графа NP-полная, любая подзадача, позволяющая быстро решить эту проблему, включая поиск оптимального порядка для жадной раскраски, является NP-сложной.
In интервальных графов и хордовых графов, если вершины упорядочены в порядке, обратном упорядочению идеального исключения, то более ранние соседи каждой вершины образуют клика. Это свойство заставляет жадную окраску производить оптимальную окраску, потому что она никогда не использует больше цветов, чем требуется для каждой из этих групп. Порядок исключения может быть найден за линейное время, если он существует.
Более того, любой идеальный порядок исключения является наследственно оптимальным, что означает, что он оптимален как для самого графа, так и для всех его индуцированных подграфы. идеально упорядочиваемые графы (которые включают хордовые графы, графы сопоставимости и) определяются как графы с оптимальным по наследству упорядочением. Распознавание идеально упорядочиваемых графов также является NP-полным.
Число цветов, получаемых жадной раскраской для наихудшего упорядочивания данного графа, называется его числом Гранди. Как трудно найти хороший порядок вершин для жадной раскраски, так и найти плохой порядок вершин. NP-полный процесс определения для данного графа G и числа k, существует ли такой порядок вершин графа G, который заставляет жадный алгоритм использовать k или более цветов. В частности, это означает, что трудно найти наихудший порядок для G.
хорошо раскрашенные графики - это графики для при котором все раскраски вершин дают одинаковое количество цветов. Это количество цветов на этих графиках равно как хроматическому числу, так и числу Гранди. Они включают в себя кографы, которые представляют собой именно те графы, в которых все индуцированные подграфы хорошо раскрашены. Тем не менее, это co-NP-Complete, чтобы определить, хорошо ли раскрашен график.
Если случайный граф взят из Erdős– Модель Реньи с постоянной вероятностью включения каждого ребра, то любой порядок вершин, выбранный независимо от ребер графа, приводит к раскраске, количество цветов которой близко к удвоенному оптимальному значению, с высокой вероятностью. Остается неизвестным, существует ли какой-либо метод полиномиального времени для нахождения значительно лучших раскраски этих графов.
Треугольная призма и квадратная антипризма, графы, чьи жадные раскраски с использованием упорядочения вырождения дают больше, чем оптимальное количество цветов Поскольку трудно найти оптимальный порядок вершин, использовались эвристики, которые пытаются уменьшить количество цветов, не гарантируя при этом оптимальное количество цветов. Обычно для жадной раскраски используется порядок выбора вершины v с минимальной степенью, рекурсивно упорядочить подграф с удаленным v , а затем поместить v последним в порядке. Наибольшая степень удаленной вершины, с которой сталкивается этот алгоритм, называется вырожденностью графа и обозначается d. В контексте жадной окраски та же стратегия упорядочивания также называется наименьшим последним упорядочением. Этот порядок вершин и вырождение можно вычислить за линейное время. Его можно рассматривать как улучшенную версию более раннего метода упорядочения вершин, наибольшего первого порядка, который сортирует вершины в порядке убывания по их степеням.
При упорядочении вырожденности жадная раскраска будет использовать не более d + 1 цвета. Это связано с тем, что при раскрашивании каждая вершина будет иметь не более d уже окрашенных соседей, поэтому один из первых d + 1 цветов будет свободен для использования. Жадная раскраска с упорядочением вырождения может найти оптимальную раскраску для определенных классов графов, включая деревья, псевдолеса и графы кроны. Маркосян, Гаспарян и Рид (1996) определяют граф 
Brélaz (1979) предлагает стратегию, называемую DSatur, для упорядочивания вершин в жадной раскраске, которая чередует построение упорядочения с процессом раскраски. В его версии алгоритма жадной раскраски следующая вершина, которую нужно раскрасить на каждом шаге, выбирается как вершина с наибольшим количеством различных цветов в ее окрестности. В случае ничьей из связанных вершин выбирается вершина максимальной степени в подграфе неокрашенных вершин. Отслеживая наборы соседних цветов и их мощности на каждом шаге, можно реализовать этот метод за линейное время.
Этот метод может найти оптимальные цвета для двудольные графы, все кактусовые графы, все колесные графы, все графы не более чем с шестью вершинами и почти каждые 
Можно определить варианты алгоритма жадной раскраски, в которых вершины данного графа раскрашиваются в заданной последовательности, но в котором цвет, выбранный для каждой вершины, не обязательно является первым доступным цветом. К ним относятся методы, в которых неокрашенная часть графа неизвестна алгоритму или в которых алгоритму дается некоторая свобода выбора лучшей окраски, чем это сделал бы базовый жадный алгоритм.
Альтернативные стратегии выбора цвета были изучены в рамках онлайн-алгоритмов. В задаче онлайн-раскраски графа вершины графа представлены алгоритму раскраски по одной в произвольном порядке; алгоритм должен выбрать цвет для каждой вершины, основываясь только на цветах и смежности между уже обработанными вершинами. В этом контексте качество стратегии выбора цвета оценивается по ее коэффициенту конкуренции, соотношению между количеством используемых цветов и оптимальным количеством цветов для данного графика.
Если не заданы дополнительные ограничения на графике, оптимальное соотношение конкуренции лишь слегка сублинейно. Однако для интервальных графов возможно постоянное конкурентное отношение, тогда как для двудольных графов и разреженных графов может быть достигнуто логарифмическое отношение. Действительно, для разреженных графов стандартная стратегия жадной окраски с выбором первого доступного цвета обеспечивает это конкурентное соотношение, и можно доказать соответствие нижней границы конкурентного отношения любого онлайн-алгоритма окраски.
Экономная раскраска для данного графа и порядка вершин была определена как раскраска, производимая жадным алгоритмом, который окрашивает вершины в данном порядке и вводит новый цвет только тогда, когда все предыдущие цвета являются рядом с данной вершиной, но может выбрать, какой цвет использовать (вместо того, чтобы всегда выбирать наименьший), когда он может повторно использовать существующий цвет. Упорядоченное хроматическое число - это наименьшее количество цветов, которое может быть получено для данного порядка таким образом, а охроматическое число - это наибольшее упорядоченное хроматическое число среди всех раскраски вершин данного графа. Несмотря на различное определение, охроматическое число всегда равно числу Гранди.
Поскольку это быстро и во многих случаях может использовать мало цветов, жадное окрашивание можно использовать в приложениях, где хорошо но не нужна оптимальная раскраска графа. Одним из первых применений жадного алгоритма было решение таких проблем, как планирование курса, в котором набор задач должен быть назначен заданному набору временных интервалов, чтобы избежать назначения несовместимых задач на один и тот же временной интервал. Его также можно использовать в компиляторах для распределения регистров, применяя его к графу, вершины которого представляют значения, которые должны быть присвоены регистрам, и чьи края представляют конфликты между двумя значениями, которые не могут быть присвоены в тот же регистр. Во многих случаях эти интерференционные графы представляют собой хордовые графы, позволяющие жадной раскраской производить оптимальное назначение регистров.
В комбинаторной теории игр для беспристрастной игра, заданная в явной форме как направленный ациклический граф, вершины которого представляют игровые позиции, а ребра представляют собой допустимые переходы из одной позиции в другую, алгоритм жадной раскраски (с использованием обратной топологической упорядочение графика) вычисляет ним-значение каждой позиции. Эти значения могут использоваться для определения оптимальной игры в любой отдельной игре или любой дизъюнктивной суммы игр.
Для графика максимальной степени Δ любая жадная раскраска будет использовать не более Δ + 1 цвета. Теорема Брукса утверждает, что за двумя исключениями (клики и нечетные циклы ) необходимо не более Δ цветов. Одно из доказательств теоремы Брукса включает нахождение порядка вершин, при котором первые две вершины смежны с последней вершиной, но не смежны друг с другом, и каждая вершина, кроме последней, имеет по крайней мере одного более позднего соседа. Для упорядочивания с этим свойством алгоритм жадной раскраски использует не более Δ цветов.
