Раскраска графика - Graph coloring

Правильная раскраска вершин графа Петерсена в 3 цвета, минимально возможное количество.

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

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

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

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

Примечание. Многие термины, используемые в этой статье, определены в Глоссарии теории графов .

История

Первые результаты о раскраске графов касаются почти исключительно плоских графов в форме раскраски карт . Пытаясь раскрасить карту графств Англии, Фрэнсис Гатри выдвинул гипотезу о четырех цветах, отметив, что четырех цветов было достаточно для раскраски карты, так что ни один регион, имеющий общую границу, не получил одного цвета. Брат Гатри передал этот вопрос своему учителю математики Августу де Моргану из Университетского колледжа , который упомянул его в письме Уильяму Гамильтону в 1852 году. Артур Кейли поднял проблему на собрании Лондонского математического общества в 1879 году. В том же году Альфред Кемпе опубликовал статью, в которой утверждалось, что установил результат, и в течение десяти лет проблема четырех цветов считалась решенной. За свои достижения Кемпе был избран членом Королевского общества, а затем президентом Лондонского математического общества.

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

В 1912 годе Биркгоф представил хроматический многочлен для изучения окраски проблемы, которая была обобщена на многочлен Татты по Татте , важными структуры в алгебраической теории графов . Кемпе уже привлек внимание к общему, неплоскому случаю в 1879 году, и многие результаты по обобщению раскраски плоских графов на поверхности более высокого порядка последовали в начале 20 века.

В 1960 году Клод Берже сформулировал другую гипотезу о раскраске графов, сильную гипотезу об идеальном графе , первоначально мотивированную теоретико-информационной концепцией, названной пропускной способностью графа без ошибок, введенной Шенноном . Гипотеза оставалась нерешенной в течение 40 лет, пока не было создана в качестве прославленной сильной теоремы идеального графика по Чудновскому , Робертсон , Сеймура и Томасу в 2002 году.

Раскраска графов изучается как алгоритмическая проблема с начала 1970-х годов: проблема хроматического числа (см. Ниже ) является одной из 21 NP-полных задач Карпа с 1972 года, и примерно в то же время были разработаны различные алгоритмы экспоненциального времени, основанные на отслеживании с возвратом. и о рецидиве делеций-сокращений Зыкова (1949) . Одно из основных применений раскраски графов - распределение регистров в компиляторах - было представлено в 1981 году.

Определение и терминология

Этот график можно раскрасить 12 различными способами.

Раскраска вершин

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

Терминология использования цветов для меток вершин восходит к раскраске карты. Такие метки, как красный и синий , используются только тогда, когда количество цветов невелико, и обычно подразумевается, что метки нарисованы из целых чисел {1, 2, 3, ...}.

Раскраска с использованием не более чем k цветов называется (правильной) k -раскраской . Наименьшее количество цветов, необходимое для раскраски графа G , называется его хроматическим числом и часто обозначается χ ( G ). Иногда используется γ ( G ), поскольку χ ( G ) также используется для обозначения эйлеровой характеристики графа. Граф, которому может быть присвоена (правильная) k- раскраска, является k -раскрашиваемым и является k -хроматическим, если его хроматическое число равно k . Подмножество вершин, которым назначен один и тот же цвет, называется цветовым классом , каждый такой класс образует независимый набор . Таким образом, k- раскраска - это то же самое, что разбиение набора вершин на k независимых множеств, а термины k-partite и k-colorable имеют одинаковое значение.

Хроматический полином

Все неизоморфные графы с 3-мя вершинами и их хроматические многочлены. Пустой граф E ₃ (красный) допускает 1-раскраску; другие признают

В хроматическом полиномиальных подсчитывает количество способов графика может быть окрашен с помощью некоторых из заданного количества цветов. Например, используя три цвета, график на соседнем изображении можно раскрасить 12 способами. Имея только два цвета, его вообще нельзя раскрасить. С четырьмя цветами его можно раскрасить 24 + 4⋅12 = 72 способами: используя все четыре цвета, их четыре! = 24 допустимые раскраски ( каждое присвоение четырех цветов любому 4-вершинному графу является правильной раскраской); и для каждого выбора трех из четырех цветов существует 12 допустимых трехцветных раскрасок. Итак, для графика в примере таблица количества допустимых раскрасок должна начинаться так:

Хроматический полином - это функция, которая подсчитывает количество t- раскрасок . Как видно из названия, для данной функции действительно полином в . Для примера графа , и действительно . ${\ Displaystyle P (G, t)}$${\ displaystyle G}$${\ displaystyle G}$${\ displaystyle t}$${\ Displaystyle Р (Г, т) = т (т-1) ^ {2} (т-2)}$${\ Displaystyle P (G, 4) = 72}$

Хроматический полином включает больше информации о раскрашиваемости G, чем хроматическое число. В самом деле, χ - наименьшее натуральное число, не являющееся нулем хроматического полинома:

${\ Displaystyle \ чи (G) = \ мин \ {к \, \ двоеточие \, P (G, k)> 0 \}.}$

Хроматические полиномы для некоторых графов

Треугольник К 3	${\ Displaystyle т (т-1) (т-2)}$
Полный граф K n	${\ Displaystyle т (т-1) (т-2) \ cdots (т- (п-1))}$
Дерево с n вершинами	${\ Displaystyle т (т-1) ^ {п-1}}$
Цикл C n	${\ Displaystyle (т-1) ^ {п} + (- 1) ^ {п} (т-1)}$
Граф Петерсена	${\ displaystyle t (t-1) (t-2) (t ^ {7} -12t ^ {6} + 67t ^ {5} -230t ^ {4} + 529t ^ {3} -814t ^ {2} + 775т-352)}$

Краска окраски

Край окраски графа является собственно окраска краев , а это означает присвоение цветов к краям так , что ни одна вершина не падает до двух краев одного и того же цвета. Раскраска ребер в k цветов называется k -кратной раскраской и эквивалентна задаче разбиения множества ребер на k паросочетаний . Наименьшее число цветов , необходимых для раскраски ребер графа G является хроматическим индексом или края хроматического числа , χ '( G ). Тэйт краситель представляет собой 3-края окраска кубического графа . Теорема о четырех цветах эквивалентна утверждению, что каждый плоский кубический граф без мостов допускает раскраску Тейта.

Общая окраска

Тотальная раскраска - это разновидность раскраски вершин и ребер графа. При использовании без каких-либо уточнений полная раскраска всегда считается правильной в том смысле, что никаким смежным вершинам, никаким смежным ребрам, никакому ребру и его концевым вершинам не назначается один и тот же цвет. Общее хроматическое число χ ″ ( G ) графа G - это наименьшее количество цветов, необходимое для любой полной раскраски графа G.

Раскраска без надписи

Немеченый раскраски графа является орбитой из окраски под действием группы автоморфизмов графа. Обратите внимание, что цвета остаются помеченными; это граф, который не помечен. Существует аналог хроматического полинома, который подсчитывает количество непомеченных раскрасок графа из заданного конечного набора цветов.

Если мы интерпретируем раскраску графа на вершинах как вектор в , действие автоморфизма - это перестановка коэффициентов в векторе раскраски. ${\ displaystyle d}$${\ Displaystyle \ mathbb {Z} ^ {d}}$

Характеристики

Верхние границы хроматического числа

Назначение разных цветов различным вершинам всегда дает правильную раскраску, поэтому

${\ Displaystyle 1 \ Leq \ чи (G) \ Leq п.}$

Единственные графы, которые могут быть одноцветными, - это графы без ребер . Полный граф из п вершин требуют цветов. В оптимальной раскраске должно быть хотя бы одно из m ребер графа между каждой парой цветовых классов, поэтому ${\ displaystyle K_ {n}}$${\ Displaystyle \ чи (К_ {п}) = п}$

${\ Displaystyle \ чи (G) (\ чи (G) -1) \ leq 2m.}$

Если G содержит клику размера k , то для раскраски этой клики необходимо не менее k цветов; другими словами, хроматическое число - это как минимум кликовое число:

${\ Displaystyle \ чи (G) \ geq \ omega (G).}$

Для совершенных графов эта оценка точная . Поиск клик известен как проблема клик .

В целом семейство графов -ограничен если есть некоторая функция такая , что графы в могут быть окрашены в большинстве цветов, для семьи из совершенных графов реализована эта функция . ${\ Displaystyle {\ mathcal {F}}}$${\ displaystyle \ chi}$${\ displaystyle c}$${\ displaystyle G}$${\ Displaystyle {\ mathcal {F}}}$${\ Displaystyle с (\ омега (G))}$${\ Displaystyle с (\ омега (G)) = \ омега (G)}$

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

А жадные окрашивающие показывает , что каждый граф может быть цветными с более одного цвета , чем максимальная вершина степени ,

${\ Displaystyle \ чи (G) \ leq \ Delta (G) +1.}$

Полные графы имеют и , а нечетные циклы имеют и , поэтому для этих графов эта оценка является наилучшей. Во всех остальных случаях оценка может быть немного улучшена; Теорема Брукса утверждает, что ${\ Displaystyle \ чи (G) = п}$${\ Displaystyle \ Delta (G) = п-1}$${\ Displaystyle \ чи (G) = 3}$${\ Displaystyle \ Delta (G) = 2}$

Теорема Брукса : для связного простого графа G , если G не является полным графом или нечетным циклом.${\ Displaystyle \ чи (G) \ leq \ Delta (G)}$

Нижние оценки хроматического числа

За прошедшие годы было обнаружено несколько нижних оценок хроматических границ:

Граница Хоффмана: Позвольте быть реальной симметричной матрицы, такой что всякий раз , когда не является ребром в . Определите , где находятся наибольшее и наименьшее собственные значения . Определите , как указано выше. Потом: ${\ displaystyle W}$${\ Displaystyle W_ {я, j} = 0}$${\ displaystyle (я, j)}$${\ displaystyle G}$${\ displaystyle \ chi _ {W} (G) = 1 - {\ tfrac {\ lambda _ {\ max} (W)} {\ lambda _ {\ min} (W)}}}$${\ displaystyle \ lambda _ {\ max} (W), \ lambda _ {\ min} (W)}$${\ displaystyle W}$${\ textstyle \ chi _ {H} (G) = \ max _ {W} \ chi _ {W} (G)}$${\ displaystyle W}$

${\ displaystyle \ chi _ {H} (G) \ leq \ chi (G).}$

Векторное хроматическое число :Позвольтебыть положительной полуопределенной матрицей, такой чтовсякий раз,когдаявляется ребром в. Определимнаименьшее k, для которого существует такая матрица. потом ${\ displaystyle W}$${\ Displaystyle W_ {я, j} \ leq - {\ tfrac {1} {k-1}}}$${\ displaystyle (я, j)}$${\ displaystyle G}$${\ Displaystyle \ чи _ {V} (G)}$${\ displaystyle W}$

${\ displaystyle \ chi _ {V} (G) \ leq \ chi (G).}$

Число Ловаса : число Ловаса дополнительного графа также является нижней границей хроматического числа:

${\ displaystyle \ vartheta ({\ bar {G}}) \ leq \ chi (G).}$

Дробное хроматическое число : Дробное хроматическое число графа также является нижней границей хроматического числа:

${\ Displaystyle \ чи _ {е} (G) \ leq \ чи (G).}$

Эти границы упорядочены следующим образом:

${\ displaystyle \ chi _ {H} (G) \ leq \ chi _ {V} (G) \ leq \ vartheta ({\ bar {G}}) \ leq \ chi _ {f} (G) \ leq \ чи (G).}$

Графики с высоким хроматическим числом

Графы с большими кликами имеют высокое хроматическое число, но обратное неверно. Граф Грёча является примером 4-хроматического графа без треугольника, и этот пример можно обобщить на Mycielskians .

Теорема ( Уильям Т. Тутт,  1947 , Александр Зыков,  1949 , Ян Мыцельски,  1955 ): существуют графы без треугольников с произвольно высоким хроматическим числом.

Чтобы доказать это, и Микельски, и Зыков дали конструкцию индуктивно определенного семейства графов без треугольников, но со сколь угодно большим хроматическим числом. Берлинг (1965) построил прямоугольники с выравниванием по осям, в которых граф пересечений не содержит треугольников и требует произвольного количества цветов для правильной раскраски. Это семейство графов называется графами Берлинга. Тот же класс графов используется для построения семейства отрезков прямых на плоскости без треугольников, данного Павликом и др. al. (2014). Это показывает, что хроматическое число его графа пересечений также сколь угодно велико. Следовательно, это означает, что прямоугольники, выровненные по осям, а также отрезки прямых в не χ-ограничены . ${\ Displaystyle \ mathbb {R} ^ {3}}$${\ Displaystyle \ mathbb {R} ^ {3}}$${\ Displaystyle \ mathbb {R} ^ {2}}$

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

Теорема ( Эрдеш ): существуют графы сколь угодно большого обхвата и хроматического числа.

Границы хроматического индекса

Раскраска ребер графа G - это раскраска вершин его линейного графа , и наоборот. Таким образом, ${\ Displaystyle L (G)}$

${\ Displaystyle \ чи '(G) = \ чи (L (G)).}$

Существует сильная взаимосвязь между раскрашиваемостью ребер и максимальной степенью графа . Поскольку все ребра, инцидентные одной вершине, должны иметь свой цвет, мы имеем ${\ Displaystyle \ Delta (G)}$

${\ Displaystyle \ чи '(G) \ geq \ Delta (G).}$

Кроме того,

Теорема Кёнига : если G двудольна.${\ Displaystyle \ чи '(G) = \ Delta (G)}$

В общем, связь даже сильнее, чем то, что дает теорема Брукса для раскраски вершин:

Теорема Визинга: граф максимальной степениимеет краево-хроматическое числоили.${\ displaystyle \ Delta}$${\ displaystyle \ Delta}$${\ displaystyle \ Delta +1}$

Прочие свойства

Граф имеет k- раскраску тогда и только тогда, когда он имеет ациклическую ориентацию, для которой самый длинный путь имеет длину не больше k ; это теорема Галлаи – Хассе – Роя – Витавера ( Nešetřil & Ossona de Mendez 2012 ).

Для плоских графов раскраски вершин по существу двойственны потокам нигде-нулю .

О бесконечных графах известно гораздо меньше. Ниже приведены два из немногих результатов о раскраске бесконечного графа:

• Если все конечные подграфы с бесконечным графом G являются к -раскрашиваемому, то и G , при предположении аксиомы выбора . Это де Брейна-Erdős теорема о де Брейна и Эрдёша (1951) .
• Если граф допускает полную n- раскраску для любого n ≥ n ₀ , он допускает бесконечную полную раскраску ( Fawcett 1978 ).

Открытые проблемы

Как указано выше, гипотеза Рида от 1998 г. заключается в том, что значение существенно ближе к нижней границе, ${\ Displaystyle \ омега (G) \ leq \ чи (G) \ leq \ Delta (G) +1.}$${\ displaystyle \ chi (G) \ leq \ left \ lceil {\ frac {\ omega (G) + \ Delta (G) +1} {2}} \ right \ rceil.}$

Хроматическим числом плоскости , где две точки смежны , если они имеют единичную расстояние, неизвестно, хотя это один из 5, 6 или 7. Другие открытые проблемы , касающиеся хроматического числа графов включают гипотезу хадвигеровского о том , что каждый граф с хроматическим числом k имеет полный граф с k вершинами в качестве минора , гипотеза Эрдеша – Фабера – Ловаса, ограничивающая хроматическое число объединений полных графов, имеющих не более одной общей вершины для каждой пары, и гипотеза Альбертсона о том, что среди k -хроматические графы: полные графы - это графы с наименьшим числом пересечений .

Когда Биркгоф и Льюис ввели хроматический полином в своей атаке на теорему о четырех цветах, они предположили, что для плоских графов G полином не имеет нулей в области . Хотя известно, что такой хроматический многочлен не имеет нулей в этой области и что их гипотеза до сих пор не решена. Также остается нерешенной проблема характеризовать графы, которые имеют один и тот же хроматический многочлен, и определять, какие многочлены являются хроматическими. ${\ Displaystyle P (G, t)}$${\ displaystyle [4, \ infty)}$${\ displaystyle [5, \ infty)}$${\ Displaystyle P (G, 4) \ neq 0}$

Алгоритмы

Раскраска графика
Решение
Имя	Раскраска графов, раскраска вершин, k -раскраска
Вход	Граф G с n вершинами. Целое число k
Выход	Допускает ли G правильную раскраску вершин в k цветов?
Продолжительность	О (2 п п )
Сложность	НП-полный
Снижение с	3-Удовлетворенность
Гэри-Джонсон	GT4
Оптимизация
Имя	Хроматическое число
Вход	Граф G с n вершинами.
Выход	χ ( G )
Сложность	NP-жесткий
Аппроксимируемость	O ( п  (журнал п ) −3 (журнал журнал п ) 2 )
Неприблизимость	O ( n 1 − ε ), если P = NP
Проблема подсчета
Имя	Хроматический полином
Вход	Граф G с n вершинами. Целое число k
Выход	Число P  ( G , k ) собственных k- раскрасок группы G
Продолжительность	О (2 п п )
Сложность	# P-complete
Аппроксимируемость	FPRAS для ограниченных случаев
Неприблизимость	Нет PTAS, если P = NP

Полиномиальное время

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

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

Точные алгоритмы

Поиск перебора для K -раскраски рассматривает каждый из заданий K цветов к п вершинам и проверкам для каждого , если он является законным. Чтобы вычислить хроматическое число и хроматический полином, эта процедура используется для каждого , что непрактично для всех входных графов, кроме самых маленьких. ${\ Displaystyle к ^ {п}}$${\ Displaystyle к = 1, \ ldots, п-1}$

Используя динамическое программирование и ограничение числа максимальных независимых множеств , k- раскрашиваемость может быть определена во времени и пространстве . Используя принцип включения-исключения и алгоритм Йейтса для быстрого дзета-преобразования, k- раскрашиваемость может быть определена во времени для любого k . Известны более быстрые алгоритмы с возможностью трех- и четырехкратной раскраски, которую можно решить со временем и соответственно. ${\ displaystyle O (2.4423 ^ {n})}$${\ Displaystyle О (2 ^ {п} п)}$${\ displaystyle O (1,3289 ^ {n})}$${\ displaystyle O (1,7272 ^ {n})}$

Сокращение

Сжатия графа G представляет собой график , полученный путем идентификации вершин U и V , а также удаление любых кромок между ними. Остальные ребра, изначально инцидентные u или v , теперь инцидентны их идентификации. Эта операция играет важную роль при анализе раскраски графов. ${\ displaystyle G / uv}$

Хроматическое число удовлетворяет рекуррентному соотношению :

${\ Displaystyle \ чи (г) = {\ текст {мин}} \ {\ чи (г + уф), \ чи (г / уф) \}}$

в связи с Зыков (1949) , где U и V являются несмежные вершины, и является граф с ребром уф добавленной. Несколько алгоритмов основаны на оценке этой повторяемости, и результирующее дерево вычислений иногда называют деревом Зыкова. Время работы основано на эвристике выбора вершин u и v . ${\ displaystyle G + uv}$

Хроматический полином удовлетворяет следующему рекуррентному соотношению

${\ Displaystyle Р (G-УФ, К) = Р (Г / УФ, К) + Р (G, К)}$

где u и v - смежные вершины, а - граф с удаленным ребром uv . представляет собой количество возможных правильных раскрасок графа, где вершины могут иметь одинаковый или разные цвета. Тогда правильные раскраски возникают из двух разных графов. Чтобы объяснить, что если вершины u и v имеют разные цвета, мы могли бы также рассмотреть граф, в котором u и v смежны. Если u и v имеют одинаковые цвета, мы могли бы также рассмотреть граф, в котором u и v сжаты. Любопытство Тутте по поводу того, какие другие свойства графа удовлетворяют эту повторяемость, привело его к открытию двумерного обобщения хроматического полинома, полинома Тутте . ${\ displaystyle G-uv}$${\ Displaystyle P (G-uv, k)}$

Эти выражения приводят к рекурсивной процедуре, называемой алгоритмом удаления-сжатия , которая составляет основу многих алгоритмов раскраски графов. Время выполнения удовлетворяет тому же рекуррентному соотношению, что и числа Фибоначчи , поэтому в худшем случае алгоритм работает во времени с полиномиальным множителем для n вершин и m ребер. Анализ может быть улучшена с точностью до полиномиального множителя числа из остовных деревьев входного графа. На практике используются стратегии ветвей и границ и отказ от изоморфизма графов , чтобы избежать некоторых рекурсивных вызовов. Время выполнения зависит от эвристики, используемой для выбора пары вершин. ${\ displaystyle \ left ({\ tfrac {1 + {\ sqrt {5}}} {2}} \ right) ^ {n + m} = O (1.6180 ^ {n + m})}$${\ Displaystyle т (G)}$

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

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

Жадный алгоритм рассматривает вершины в определенном порядке , ..., и правопреемники к наималейшему доступному цвету не используется соседями «S среди ..., , добавив свежий цвет , если это необходимо. Качество полученной окраски зависит от выбранной вами расцветки. Существует упорядочивание, которое приводит к жадной раскраске с оптимальным количеством цветов. С другой стороны, жадные раскраски могут быть сколь угодно плохими; например, граф короны на n вершинах может быть двухцветным, но имеет порядок, который приводит к жадной раскраске в цвета. ${\ displaystyle v_ {1}}$${\ displaystyle v_ {n}}$${\ displaystyle v_ {i}}$${\ displaystyle v_ {i}}$${\ displaystyle v_ {1}}$${\ displaystyle v_ {i-1}}$${\ Displaystyle \ чи (G)}$${\ displaystyle n / 2}$

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

Если вершины упорядочены в соответствии с их степенями , в результирующей жадной раскраске используется не больше цветов, максимум на один больше, чем максимальная степень графа. Эту эвристику иногда называют алгоритмом Уэлша – Пауэлла. Другая эвристика, разработанная Brélaz, устанавливает порядок динамически, пока алгоритм продолжает работу, выбирая следующую вершину, смежную с наибольшим количеством разных цветов. Многие другие эвристики раскраски графов аналогичным образом основаны на жадной раскраске для конкретной статической или динамической стратегии упорядочивания вершин, эти алгоритмы иногда называют алгоритмами последовательной раскраски . ${\ displaystyle {\ text {max}} _ {i} {\ text {min}} \ {d (x_ {i}) + 1, i \}}$

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

Параллельные и распределенные алгоритмы

В области распределенных алгоритмов раскраска графов тесно связана с проблемой нарушения симметрии . Современные рандомизированные алгоритмы быстрее при достаточно большой максимальной степени Δ, чем детерминированные алгоритмы. Самые быстрые рандомизированные алгоритмы используют технику множественных испытаний Schneider et al.

В симметричном графе , A детерминированный распределенный алгоритм не может найти подходящую вершину окраски. Некоторая вспомогательная информация необходима, чтобы нарушить симметрию. Стандартное предположение состоит в том, что изначально каждый узел имеет уникальный идентификатор , например, из набора {1, 2, ..., n }. Иначе говоря, мы предполагаем, что нам дана n- раскраска. Задача состоит в том, чтобы уменьшить количество цветов с n , например, до Δ + 1. Чем больше цветов используется, например, O (Δ) вместо Δ + 1, тем меньше циклов связи требуется.

Прямая распределенная версия жадного алгоритма (Δ + 1) -раскрашивания требует Θ ( n ) раундов связи в худшем случае - может потребоваться распространение информации с одной стороны сети на другую.

Простейший интересный случай представляет собой п - цикл . Ричард Коул и Узи Вишкин показывают, что существует распределенный алгоритм, который уменьшает количество цветов с n до O (log  n ) за один синхронный шаг связи. Повторяя ту же процедуру, можно получить 3-цветную раскраску n -цикла за O ( log *  n ) шагов связи (при условии, что у нас есть уникальные идентификаторы узлов).

Функция log * , повторный логарифм , является чрезвычайно медленно растущей функцией, «почти постоянной». Следовательно, результат Коула и Вишкина поднял вопрос о том, существует ли распределенный алгоритм с постоянным временем для 3-раскраски n -цикла. Linial (1992) показал, что это невозможно: любой детерминированный распределенный алгоритм требует Ω ( log *  n ) коммуникационных шагов, чтобы свести n- раскраску к 3-раскраске в n -цикле.

Технику Коула и Вишкина можно применять и к произвольным графам ограниченной степени; время работы - poly (Δ) + O ( log *  n ). Этот метод был распространен на графы единичных дисков Шнайдером и др. Самые быстрые детерминированные алгоритмы (Δ + 1) -раскрашивания для малых Δ принадлежат Леониду Баренбойму, Майклу Элькину и Фабиану Куну. Алгоритм Баренбойма и др. выполняется за время O (Δ) +  log * ( n ) / 2, что является оптимальным с точки зрения n, поскольку постоянный множитель 1/2 не может быть улучшен из-за нижней границы Линиала. Панконези и Сринивасан (1996) используют разложение сети для вычисления раскраски Δ + 1 во времени . ${\ displaystyle 2 ^ {O \ left ({\ sqrt {\ log n}} \ right)}}$

Проблема раскраски ребер также изучалась в распределенной модели. Panconesi и Rizzi (2001) достигли (2Δ - 1) -раскрашивания за время O (Δ +  log *  n ) в этой модели. Нижняя оценка распределенной раскраски вершин, полученная Линиалом (1992), также применима к проблеме распределенной раскраски ребер.

Децентрализованные алгоритмы

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

Вычислительная сложность

Раскраска графов сложна в вычислительном отношении. Это NP-полной , чтобы решить , если данный граф допускает K -раскраска для данного к за исключением случаев , к ∈ {0,1,2}. В частности, вычислить хроматическое число NP-сложно. Проблема 3-раскраски остается NP-полной даже на 4-регулярных планарных графах . Однако для любого k > 3 существует k -раскраска плоского графа по теореме о четырех цветах , и можно найти такую ​​раскраску за полиномиальное время.

Самый известный алгоритм аппроксимации вычисляет раскраску размером не более чем в пределах множителя O ( n (log log  n ) ² (log n) ⁻³ ) от хроматического числа. Для всех х  > 0, аппроксимирующех хроматическое числа в пределах п ^{1- е} является NP-трудным .

Также NP-сложно раскрасить 3-раскрашиваемый граф 4-мя цветами и k- раскрашиваемый граф k ^{(log k  ) / 25} цветов для достаточно большой постоянной k .

Вычисление коэффициентов хроматического полинома является # P-трудным . Фактически, даже вычисление значения является # P-сложным в любой рациональной точке k, кроме k  = 1 и k  = 2. Не существует FPRAS для вычисления хроматического полинома в любой рациональной точке k  ≥ 1,5, за исключением k  = 2, если только NP  =  RP . ${\ Displaystyle \ чи (г, к)}$

Для раскраски краев доказательство результата Визинга дает алгоритм, который использует не более Δ + 1 цветов. Однако выбор между двумя значениями-кандидатами для краевого хроматического числа является NP-полным. Что касается алгоритмов аппроксимации, алгоритм Визинга показывает, что хроматическое число края можно аппроксимировать с точностью до 4/3, а результат жесткости показывает, что (4/3 -  ε  ) -алгоритм не существует для любого ε> 0, если P = NP . Это одни из самых старых результатов в литературе по аппроксимационным алгоритмам, хотя ни в одной из статей это понятие явно не используется.

Приложения

Планирование

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

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

Распределение регистров

Компилятор представляет собой компьютерную программу , которая переводит один компьютерный язык в другой. Чтобы сократить время выполнения результирующего кода, одним из методов оптимизации компилятора является выделение регистров , при котором наиболее часто используемые значения скомпилированной программы хранятся в регистрах быстрого процессора . В идеале значения назначаются регистрам, чтобы все они могли находиться в регистрах, когда они используются.

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

Другие приложения

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

Другие раскраски

Теория Рамсея

Важный класс проблем несобственной раскраски изучается в теории Рамсея , где ребрам графа присвоены цвета и нет ограничений на цвета инцидентных ребер. Простым примером является теорема о дружбе , которая утверждает, что в любой раскраске ребер полного графа из шести вершин будет одноцветный треугольник; часто иллюстрируется высказыванием, что в любой группе из шести человек есть либо три общих незнакомца, либо три общих знакомых. Теория Рамсея занимается обобщением этой идеи для поиска регулярности среди беспорядка, поиска общих условий существования монохроматических подграфов с заданной структурой. ${\ displaystyle K_ {6}}$

Другие раскраски

Раскраска также может быть рассмотрена для графиков со знаком и графиков усиления .

Смотрите также

• Критический график
• Гомоморфизм графов
• Строительство Hajós
• Математика судоку
• Многостраничный граф
• Уникально раскрашиваемый график
• Игра-раскраска из графиков

Примечания

использованная литература

внешние ссылки

• Высокопроизводительные алгоритмы раскраски графов Набор из 8 различных алгоритмов (реализованных на C ++), используемых в книге «Руководство по раскраске графов: алгоритмы и приложения» (Springer International Publishers, 2015).
• Graph Coloring Page от Джозефа Калберсона (программы раскраски графиков)
• CoLoRaTiOn Джима Эндрюса и Майка Феллоуза - это головоломка с раскраской графиков.
• Ссылки на исходные коды Graph Coloring
• Код для эффективного вычисления Тутте, Хроматических полиномов и Полиномов потока от Гэри Хаггарда, Дэвида Дж. Пирса и Гордона Ройла
• Веб-приложение для раскраски графов от Хосе Антонио Мартина Х.