Jump to content

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

Это хорошая статья. Нажмите здесь для получения дополнительной информации.

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

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

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

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

Алгоритм

[ редактировать ]

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

В 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и общее время работы алгоритма пропорциональны количеству ребер в графе. [2]

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

Выбор заказа

[ редактировать ]

Разный порядок вершин графа может привести к тому, что при жадной раскраске будет использоваться разное количество цветов: от оптимального количества цветов до, в некоторых случаях, количества цветов, пропорционального количеству вершин в графе. Например, коронный граф (граф, образованный из двух непересекающихся наборов из 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 . [5] Существуют также графы, в которых случайно выбранный порядок вершин с большой вероятностью приводит к количеству цветов, значительно превышающему минимальное. [6] Поэтому при жадной раскраске очень важно тщательно выбирать порядок вершин.

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

[ редактировать ]

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

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

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

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

[ редактировать ]

Количество цветов, полученных в результате жадной раскраски для наихудшего порядка данного графа, называется его числом Гранди . [12] Точно так же, как сложно найти хороший порядок вершин для жадной раскраски, так же сложно найти плохой порядок вершин. NP-полно определить Для данного графа G и числа k , существует ли такой порядок вершин 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]

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

[ редактировать ]

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

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

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

[ редактировать ]

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

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

[ редактировать ]

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

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

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

[ редактировать ]

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

Приложения

[ редактировать ]

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

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

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

Примечания

[ редактировать ]
  1. ^ Митчем (1976) .
  2. Перейти обратно: Перейти обратно: а б Хоанг и Сритаран (2016) , теорема 28.33, стр. 738 ; Хусфельдт (2015) , Алгоритм G
  3. Перейти обратно: Перейти обратно: а б Фриз и МакДиармид (1997) .
  4. Перейти обратно: Перейти обратно: а б Уэлш и Пауэлл (1967) .
  5. ^ Джонсон (1974) ; Хусфельдт (2015) .
  6. ^ Керл (1991) ; Хусфельдт (2015) .
  7. ^ Хусфельдт (2015) .
  8. ^ Маффрей (2003) .
  9. ^ Роуз, Люкер и Тарьян (1976) .
  10. ^ Схватил (1984) ; Хусфельдт (2015) .
  11. ^ Миддендорф и Пфайффер (1990) .
  12. Перейти обратно: Перейти обратно: а б с д Закер (2006) .
  13. ^ Кристен и Селков (1979) .
  14. ^ Митчем (1976) ; Хусфельдт (2015) .
  15. ^ Матула и Бек (1983) .
  16. ^ Уэлш и Пауэлл (1967) ; Хусфельдт (2015) .
  17. ^ Матула (1968) ; Секерес и Уильф (1968) .
  18. Перейти обратно: Перейти обратно: а б Косовский и Манушевский (2004) .
  19. ^ Маркосян, Гаспарян и Рид (1996) ; Маффрэй (2003) .
  20. ^ Маркосян, Гаспарян и Рид (1996) .
  21. ^ Греф, Штумпф и Вайсенфельс (1998) .
  22. ^ Брелаз (1979) ; Левек и Мафре (2005) .
  23. ^ Брелаз (1979) .
  24. ^ Янчевский и др. (2001) .
  25. ^ Левек и Мафре (2005) .
  26. Перейти обратно: Перейти обратно: а б Ирани (1994) .
  27. ^ Ловас, Сакс и Троттер (1989) ; Вишванатан (1992) .
  28. ^ Кирстед и Троттер (1981) .
  29. ^ Симмонс (1982) ; Эрдеш и др. (1987) .
  30. ^ Полетто и Саркар (1999) . Хотя Полетто и Саркар описывают свой метод распределения регистров как не основанный на раскраске графа, он похож на жадную раскраску.
  31. ^ Перейра и Палсберг (2005) .
  32. ^ Например, см. раздел 1.1 Ниваша (2006) .
  33. ^ Райдер (1975) .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: e73dac2fd98b617a60e9f7700b2bc343__1715659800
URL1:https://arc.ask3.ru/arc/aa/e7/43/e73dac2fd98b617a60e9f7700b2bc343.html
Заголовок, (Title) документа по адресу, URL1:
Greedy coloring - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)