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

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

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

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

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

Алгоритм

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

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

def first_available(colors):
    """Return smallest non-negative integer not in the given set of colors.
    """
    color = 0
    while color in colors:
        color += 1
    return color

def greedy_coloring(G, order):
    """Find the greedy coloring of G in the given order.

    The representation of G is assumed to be like https://www.python.org/doc/essays/graphs/
    in allowing neighbors of a node/vertex to be iterated over by "for w in G[node]".
    The return value is a dictionary mapping vertices to their colors.
    """
    coloring = dict()
    for node in order:
        used_neighbour_colors = {coloring[nbr]
                                 for nbr in G[node]
                                 if nbr in coloring}
        coloring[node] = first_available(used_neighbour_colors)
    return coloring

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

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

Выбор заказа

Разный порядок вершин графа может привести к тому, что при жадной раскраске будет использоваться разное количество цветов: от оптимального количества цветов до, в некоторых случаях, количества цветов, пропорционального количеству вершин в графе. Например, коронный граф (граф, образованный из двух непересекающихся наборов из n /2 вершин { a ₁ , a ₂ , ... } и { b ₁ , b ₂ , ... } путем соединения a _i с b _j всякий раз, когда i ≠ j ) может быть особенно плохим случаем жадной раскраски. Если вершины упорядочены a ₁ , b ₁ , a ₂ , b ₂ , ... , жадная раскраска будет использовать n /2 цветов, по одному цвету для каждой пары ( a _i , b _i ) . Однако оптимальное количество цветов для этого графа — два: один цвет для вершин a _i , а другой — для вершин b _i . Существуют также графы, в которых случайно выбранный порядок вершин с большой вероятностью приводит к количеству цветов, значительно превышающему минимальное. Поэтому при жадной раскраске очень важно тщательно выбирать порядок вершин.

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

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

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

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

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

Основная статья: Число Гранди

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

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

Основная статья: Ярко окрашенный график

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

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

Вырождение

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

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

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

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

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

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

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

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

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

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

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

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

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

Приложения

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

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

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

Ссылки

• Брелаз, Даниэль (апрель 1979 г.), «Новые методы раскраски вершин графа», Communications of ACM , 22 (4): 251–256, doi : 10.1145/359094.359101 , S2CID   14838769
• Кристен, Клод А.; Селков, Стэнли М. (1979), «Некоторые идеальные свойства раскраски графов», Журнал комбинаторной теории , серия B, 27 (1): 49–59, doi : 10.1016/0095-8956(79)90067-4 , MR   0539075
• Хватал, Вацлав (1984), «Идеально упорядочиваемые графы», Берже, Клод ; Хватал, Вацлав (ред.), Темы в совершенных графах , Анналы дискретной математики, том. 21, Амстердам: Северная Голландия, стр. 63–68 . Цитируется Маффреем (2003) .
• Эрдеш, П .; Заяц, WR; Хедетниеми, СТ; Ласкар, Р. (1987), «О равенстве чисел Гранди и охроматического числа графа» (PDF) , Journal of Graph Theory , 11 (2): 157–159, doi : 10.1002/jgt.3190110205 , MR   0889347 .
• Фриз, Алан ; МакДиармид, Колин (1997), «Алгоритмическая теория случайных графов», Случайные структуры и алгоритмы , 10 (1–2): 5–42, doi : 10.1002/(SICI)1098-2418(199701/03)10:1/ 2<5::AID-RSA2>3.3.CO;2-6 , MR   1611517 .
• Греф, А.; Стамп, М.; Вайсенфельс, Г. (1998), «О раскраске дисковых графов единиц», Algorithmica , 20 (3): 277–293, doi : 10.1007/PL00009196 , MR   1489033 , S2CID   36161020 .
• Хоанг, Чинь Т.; Шритаран, Р. (2016), «Глава 28. Совершенные графы», в Туласирамане, Кришнайян; Арумугам, Субраманиан; Брандштедт, Андреас; Нишизеки, Такао (ред.), Справочник по теории графов, комбинаторной оптимизации и алгоритмам , Chapman & Hall/CRC Computer and Information Science Series, vol. 34, CRC Press, стр. 707–750, ISBN.  9781420011074 .
• Хусфельдт, Тор (2015), «Алгоритмы раскраски графов», в Бейнеке, Лоуэлл В.; Уилсон, Робин Дж. (ред.), Темы теории хроматических графов , Энциклопедия математики и ее приложений, том. 156, Cambridge University Press, стр. 277–303, arXiv : 1505.05825 , MR   3380176.
• Ирани, Сэнди (1994), «Раскраска индуктивных графов в режиме онлайн», Algorithmica , 11 (1): 53–72, doi : 10.1007/BF01294263 , MR   1247988 , S2CID   181800 .
• Янчевский Р.; Кубале, М.; Манушевский, К.; Пиваковски, К. (2001), «Наименьший трудно раскрашиваемый граф для алгоритма DSATUR», Discrete Mathematics , 236 (1–3): 151–165, doi : 10.1016/S0012-365X(00)00439-8 , МР   1830607 .
• Кирстед, штат ХА; Троттер, В.Т. (1981), «Экстремальная задача в рекурсивной комбинаторике», Труды двенадцатой Юго-восточной конференции по комбинаторике, теории графов и вычислениям, Vol. II (Батон-Руж, Луизиана, 1981), Congressus Numerantium , 33 : 143–153, MR   0681909 . Цитируется Ирани (1994) .
• Косовский, Адриан; Манушевский, Кшиштоф (2004), «Классическая раскраска графов», в Кубале, Марек (ред.), Раскраски графов , Современная математика, том. 352, Провиденс, Род-Айленд: Американское математическое общество, стр. 1–19, doi : 10.1090/conm/352/06369 , ISBN.  978-0-8218-3458-9 , МР   2076987
• Кучера, Людек (1991), «Жадная раскраска — плохой вероятностный алгоритм», Journal of Algorithms , 12 (4): 674–684, doi : 10.1016/0196-6774(91)90040-6 , MR   1130323 .
• Джонсон, Дэвид С. (1974), «Поведение алгоритмов раскраски графов в наихудшем случае», Труды Пятой юго-восточной конференции по комбинаторике, теории графов и вычислениям (Флоридский Атлантический университет, Бока-Ратон, Флорида, 1974) , Congressus Numerantium, том. X, Виннипег, Манитоба: Utilitas Math., стр. 513–527, MR   0389644 .
• Левек, Бенджамин; Маффрэ, Фредерик (октябрь 2005 г.), «Раскраска графов Мейнеля в линейное время» (PDF) , в Распо, Андре; Дельмас, Оливье (ред.), 7-й Международный коллоквиум по теории графов (ICGT '05), 12–16 сентября 2005 г., Йер, Франция , Электронные заметки по дискретной математике, том. 22, Elsevier, стр. 25–28, arXiv : cs/0405059 , doi : 10.1016/j.endm.2005.06.005 , S2CID   6262680 . См. также Левек, Бенджамин; Маффрэ, Фредерик (9 января 2006 г.), Ошибка: MCColor не оптимален для графиков Мейниэля , arXiv : cs/0405059 .
• Ловас, Л. (1975), «Три коротких доказательства в теории графов», Журнал комбинаторной теории , серия B, 19 (3): 269–271, doi : 10.1016/0095-8956(75)90089-1 , MR   0396344 .
• Ловас, Л. ; Сакс, Мэн ; Троттер, В.Т. (1989), «Алгоритм онлайн-раскраски графов с сублинейным коэффициентом производительности», Discrete Mathematics , 75 (1–3): 319–325, doi : 10.1016/0012-365X(89)90096-4 , MR   1001404 .
• Маффрэ, Фредерик (2003), «О раскраске идеальных графов», Рид, Брюс А .; Продажи, Клаудия Л. (ред.), «Последние достижения в области алгоритмов и комбинаторики» , Книги CMS по математике, том. 11, Springer-Verlag, стр. 65–84, номер документа : 10.1007/0-387-22444-0_3 , ISBN.  0-387-95434-1 , МР   1952983 .
• Маркосян, С.Э.; Гаспарян, Г.С.; Рид, Б.А. (1996), «β-совершенные графы», Журнал комбинаторной теории , серия B, 67 (1): 1–11, doi : 10.1006/jctb.1996.0030 , MR   1385380 .
• Матула, Дэвид В. (1968), «Теорема о мин-максе для графов с применением к раскраске графов», Национальное собрание SIAM 1968 года, SIAM Review , 10 (4): 481–482, doi : 10.1137/1010115 .
• Матула, Дэвид В .; Бек, Л.Л. (1983), «Алгоритмы упорядочения, кластеризации и раскраски графов наименьшего последнего», Журнал ACM , 30 (3): 417–427, doi : 10.1145/2402.322385 , MR   0709826 .
• Миддендорф, Матиас; Пфайффер, Франк (1990), «О сложности распознавания идеально упорядочиваемых графов», Discrete Mathematics , 80 (3): 327–333, doi : 10.1016/0012-365X(90)90251-C , MR   1049253 .
• Митчем, Джон (1976), «О различных алгоритмах оценки хроматического числа графа», The Computer Journal , 19 (2): 182–183, doi : 10.1093/comjnl/19.2.182 , MR   0437376 .
• Ниваш, Габриэль (2006), «Функция Спрага – Гранди игры Евклида», Discrete Mathematics , 306 (21): 2798–2800, doi : 10.1016/j.disc.2006.04.020 , MR   2264378 .
• Перейра, Фернандо Великий; Палсберг, Йенс (2005), «Распределение регистров посредством раскраски хордальных графов», в Proceedings of Yi, Kwangkeun (ed.), Языки программирования и системы: Третий азиатский симпозиум, APLAS 2005, Цукуба, Япония, 2–5 ноября , 2005 , Конспект лекций по информатике, вып. 3780, Спрингер, с. 315–329, номер домена : 10.1007/11575467_21 , ISBN.  978-3-540-29735-2
• Полетто, Массимилиано; Саркар, Вивек (сентябрь 1999 г.), «Распределение регистров линейного сканирования», Транзакции ACM в языках и системах программирования , 21 (5): 895–913, doi : 10.1145/330249.330250 , S2CID   18180752 .
• Роуз, Д.; Люкер, Джордж; Тарьян, Роберт Э. (1976), «Алгоритмические аспекты исключения вершин на графах», SIAM Journal on Computing , 5 (2): 266–283, doi : 10.1137/0205021 , MR   0408312 .
• Симмонс, Густав Дж. (1982), «Упорядоченное хроматическое число плоских карт», Труды тринадцатой Юго-восточной конференции по комбинаторике, теории графов и вычислениям (Бока-Ратон, Флорида, 1982), Congressus Numerantium , 36 : 59–67 , МР   0726050
• Сысло, Мацей М. (1989), «Последовательная раскраска в сравнении с границей Уэлша – Пауэлла», Discrete Mathematics , 74 (1–2): 241–243, doi : 10.1016/0012-365X(89)90212-4 , MR   0989136 .
• Секерес, Джордж ; Уилф, Герберт С. (1968), «Неравенство для хроматического числа графа», Журнал комбинаторной теории , 4 : 1–3, doi : 10.1016/S0021-9800(68)80081-X .
• Вишванатан, Сундар (1992), «Рандомизированная онлайн-раскраска графов», Journal of Algorithms , 13 (4): 657–669, doi : 10.1016/0196-6774(92)90061-G , MR   1187207 .
• Валлийский, DJA ; Пауэлл, МБ (1967), «Верхняя граница хроматического числа графа и ее применение к задачам составления расписания», The Computer Journal , 10 (1): 85–86, doi : 10.1093/comjnl/10.1.85 .
• Закер, Манучехр (2006), «Результаты по хроматическому числу графов Гранди», Discrete Mathematics , 306 (2–3): 3166–3173, doi : 10.1016/j.disc.2005.06.044 , MR   2273147 .