В теории графов , раскраски графа является частным случаем маркировки графа ; это присвоение меток, традиционно называемых «цветами», элементам графа с учетом определенных ограничений. В простейшей форме это способ раскраски вершин графа таким образом, чтобы никакие две соседние вершины не были одного цвета; это называется раскраской вершины . Аналогичным образом , край окраски присваивает цвет каждому краю , так что никакие два смежных ребра не имеют одинаковый цвет, а лицо окраски о наличии планарного графа присваивает цвет каждой грани или области , так что никакие два лица , которые разделяют границей не имеют такого же цвета.
Раскраска вершин обычно используется для введения задач раскраски графов, поскольку другие задачи раскраски могут быть преобразованы в экземпляр раскраски вершин. Например, раскраска ребер графа - это просто раскраска вершин его линейного графа , а раскраска граней плоского графа - это просто раскраска вершин его двойственного графа . Однако проблемы не вершинной раскраски часто формулируются и изучаются как есть. Это отчасти педагогическое , а отчасти потому, что некоторые задачи лучше всего изучать в не вершинной форме, как в случае раскраски ребер.
Условие использования цветов происходит от раскрашивания стран на карте , где буквально окрашено каждое лицо. Это было обобщено для раскраски граней графа, вложенного в плоскость. Благодаря плоской двойственности он стал раскрашиванием вершин и в этой форме распространяется на все графы. В математических и компьютерных представлениях обычно используются первые несколько положительных или неотрицательных целых чисел в качестве «цветов». В общем, в качестве «цветового набора» можно использовать любой конечный набор . Характер проблемы с окраской зависит от количества цветов, а не от того, какие они есть.
Раскраска графов имеет множество практических приложений, а также решает теоретические задачи. Помимо классических типов задач, различные ограничения также могут быть установлены на графике, или на способ назначения цвета, или даже на сам цвет. Он даже стал популярным среди широкой публики в виде популярной головоломки судоку с числами . Раскраска графиков по-прежнему является очень активной областью исследований.
Примечание. Многие термины, используемые в этой статье, определены в Глоссарии теории графов .
История
Первые результаты о раскраске графов касаются почти исключительно плоских графов в форме раскраски карт . Пытаясь раскрасить карту графств Англии, Фрэнсис Гатри выдвинул гипотезу о четырех цветах, отметив, что четырех цветов было достаточно для раскраски карты, так что ни один регион, имеющий общую границу, не получил одного цвета. Брат Гатри передал этот вопрос своему учителю математики Августу де Моргану из Университетского колледжа , который упомянул его в письме Уильяму Гамильтону в 1852 году. Артур Кейли поднял проблему на собрании Лондонского математического общества в 1879 году. В том же году Альфред Кемпе опубликовал статью, в которой утверждалось, что установил результат, и в течение десяти лет проблема четырех цветов считалась решенной. За свои достижения Кемпе был избран членом Королевского общества, а затем президентом Лондонского математического общества. [1]
В 1890 году Хивуд указал, что аргумент Кемпе ошибочен. Однако в этой статье он доказал теорему о пяти цветах , заявив, что каждую планарную карту можно раскрасить не более чем в пять цветов, используя идеи Кемпе. В следующем столетии было разработано огромное количество работ и теорий, чтобы сократить количество цветов до четырех, пока теорема о четырех цветах не была окончательно доказана в 1976 году Кеннетом Аппелем и Вольфгангом Хакеном . Доказательство восходит к идеям Хивуда и Кемпе и в значительной степени игнорирует промежуточные разработки. [2] Доказательство теоремы о четырех цветах также заслуживает внимания как первое крупное компьютерное доказательство.
В 1912 годе Биркгоф представил хроматический многочлен для изучения окраски проблемы, которая была обобщена на многочлен Татты по Татте , важными структуры в алгебраической теории графов . Кемпе уже привлекал внимание к общему, неплоскому случаю в 1879 г. [3], и многие результаты об обобщении раскраски плоских графов на поверхности более высокого порядка последовали в начале 20-го века.
В 1960 году Клод Берже сформулировал еще одну гипотезу о раскраске графов, сильную гипотезу об идеальном графе , первоначально мотивированную теоретико-информационной концепцией, названной пропускной способностью графа без ошибок, введенной Шенноном . Гипотеза оставалась нерешенной в течение 40 лет, пока не было создана в качестве прославленной сильной теоремы идеального графика по Чудновскому , Робертсон , Сеймура и Томасу в 2002 году.
Раскраска графов изучается как алгоритмическая проблема с начала 1970-х годов: проблема хроматических чисел является одной из 21 NP-полных задач Карпа с 1972 года, и примерно в то же время были разработаны различные алгоритмы экспоненциального времени, основанные на отслеживании с возвратом и удалении. -сокращающая повторяемость Зыкова (1949) . Одно из основных применений раскраски графов - распределение регистров в компиляторах - было представлено в 1981 году.
Определение и терминология
Раскраска вершин
При использовании без каких-либо уточнений раскраска графа почти всегда является правильной раскраской вершин , а именно маркировкой вершин графа такими цветами, что никакие две вершины, имеющие одно и то же ребро, не имеют одинаковый цвет. Поскольку вершина с петлей (то есть соединение непосредственно с собой) никогда не может быть правильно окрашена, понятно, что графы в этом контексте не имеют петель.
Терминология использования цветов для меток вершин восходит к раскраске карты. Такие метки, как красный и синий , используются только тогда, когда количество цветов невелико, и обычно подразумевается, что метки нарисованы из целых чисел {1, 2, 3, ...}.
Раскраска с использованием не более чем k цветов называется (правильной) k -раскраской . Наименьшее количество цветов, необходимое для раскраски графа G , называется его хроматическим числом и часто обозначается χ ( G ). Иногда используется γ ( G ), поскольку χ ( G ) также используется для обозначения эйлеровой характеристики графа. Граф, которому может быть присвоена (правильная) k- раскраска, является k -раскрашиваемым и является k -хроматическим, если его хроматическое число равно k . Подмножество вершин, которым назначен один и тот же цвет, называется цветовым классом , каждый такой класс образует независимый набор . Таким образом, k- раскраска - это то же самое, что разбиение набора вершин на k независимых множеств, а термины k-partite и k-colorable имеют одинаковое значение.
Хроматический полином
В хроматическом полиномиальных подсчитывает количество способов графика может быть окрашен с помощью некоторых из заданного количества цветов. Например, используя три цвета, график на соседнем изображении можно раскрасить 12 способами. Имея только два цвета, его вообще нельзя раскрасить. С четырьмя цветами его можно раскрасить 24 + 4⋅12 = 72 способами: используя все четыре цвета, их четыре! = 24 допустимые раскраски ( каждое присвоение четырех цветов любому 4-вершинному графу является правильной раскраской); и для каждого выбора трех из четырех цветов существует 12 допустимых трехцветных раскрасок. Итак, для графика в примере таблица количества допустимых раскрасок должна начинаться так:
Доступные цвета | 1 | 2 | 3 | 4 | … |
Кол-во раскрасок | 0 | 0 | 12 | 72 | … |
Хроматический полином - это функция который подсчитывает количество t- раскрасок. Как видно из названия, для данногофункция действительно является многочленом в. Для примера графика, и действительно .
Хроматический полином включает больше информации о раскрашиваемости G, чем хроматическое число. В самом деле, χ - наименьшее натуральное число, не являющееся нулем хроматического полинома:
Треугольник К 3 | |
Полный граф K n | |
Дерево с n вершинами | |
Цикл C n | |
Граф Петерсена |
Раскраска края
Край окраски графа является собственно окраска краев , а это означает присвоение цветов к краям так , что ни одна вершина не падает до двух краев одного и того же цвета. Раскраска ребер в k цветов называется k -кратной раскраской и эквивалентна задаче разбиения множества ребер на k паросочетаний . Наименьшее число цветов , необходимых для раскраски ребер графа G является хроматическим индексом или края хроматического числа , χ '( G ). Тэйт краситель представляет собой 3-края окраска кубического графа . Теорема о четырех цветах эквивалентна утверждению, что каждый плоский кубический граф без мостов допускает раскраску Тейта.
Общая окраска
Тотальная раскраска - это разновидность раскраски вершин и ребер графа. При использовании без каких-либо уточнений полная раскраска всегда считается правильной в том смысле, что никаким смежным вершинам, никаким смежным ребрам, никакому ребру и его конечным вершинам не назначается один и тот же цвет. Общее хроматическое число χ ″ (G) графа G - это наименьшее количество цветов, необходимое для любой полной раскраски графа G.
Раскраска без надписи
Немеченый раскраски графа является орбитой из окраски под действием группы автоморфизмов графа. Обратите внимание, что цвета остаются помеченными; это граф, который не помечен. Существует аналог хроматического полинома, который подсчитывает количество непомеченных раскрасок графа из заданного конечного набора цветов.
Если интерпретировать раскраску графа на вершины как вектор в , действие автоморфизма - это перестановка коэффициентов в векторе раскраски.
Характеристики
Верхние границы хроматического числа
Назначение разных цветов различным вершинам всегда дает правильную раскраску, поэтому
Единственными графами, которые могут быть одноцветными, являются графы без ребер . Полный граф из n вершин требуетсяцвета. В оптимальной раскраске должно быть хотя бы одно из m ребер графа между каждой парой цветовых классов, поэтому
Если G содержит клику размера k , то для раскраски этой клики необходимо не менее k цветов; другими словами, хроматическое число - это как минимум кликовое число:
Для совершенных графов эта оценка точная . Поиск клик известен как проблема клик .
В целом семья графиков χ {\ displaystyle \ chi} -ограничен, если есть какая-то функция такие, что графики в можно раскрасить не более чем цветов, для семейства идеальных графов эта функция .
Двухцветные графы - это в точности двудольные графы , включая деревья и леса. По теореме о четырех цветах любой плоский граф может быть четырехцветным.
А жадные окрашивающие показывает , что каждый граф может быть цветными с более одного цвета , чем максимальная вершина степени ,
Полные графики имеют а также , а нечетные циклы имеют а также , поэтому для этих графов эта оценка является наилучшей. Во всех остальных случаях оценка может быть немного улучшена; Теорема Брукса [4] утверждает, что
- Теорема Брукса :для связного простого графа G , если G не является полным графом или нечетным циклом.
Нижние оценки хроматического числа
За прошедшие годы было обнаружено несколько нижних оценок хроматических границ:
Граница Хоффмана: Пусть - вещественная симметричная матрица такая, что в любое время не край в . Определять, где - наибольшее и наименьшее собственные значения . Определять, с участием как указано выше. Потом:
- .
Векторное хроматическое число :Пусть - положительная полуопределенная матрица такая, что в любое время это край в . Определять быть наименьшим k, для которого такая матрица существуют. потом
Число Ловаса : число Ловаса дополнительного графа также является нижней границей хроматического числа:
Дробное хроматическое число : Дробное хроматическое число графа также является нижней границей хроматического числа:
Эти границы упорядочены следующим образом:
Графики с высоким хроматическим числом
Графы с большими кликами имеют высокое хроматическое число, но обратное неверно. Граф Грёча является примером 4-хроматического графа без треугольника, и этот пример можно обобщить на Mycielskians .
- Теорема ( Уильям Т. Тутт, 1947 , [5] Александр Зыков, 1949 , Ян Мыцельски, 1955 ): существуют графы без треугольников с произвольно высоким хроматическим числом.
Чтобы доказать это, и Микельски, и Зыков дали конструкцию индуктивно определенного семейства графов без треугольников, но со сколь угодно большим хроматическим числом. [6] Берлинг (1965) [7] сконструировал выровненные по оси коробки вграф пересечений которого не содержит треугольников и для правильной раскраски требуется сколь угодно много цветов. Это семейство графов называется графами Берлинга. Тот же класс графов используется для построения семейства отрезков прямых на плоскости без треугольников, данного Павликом и др. al. (2014). [8] Это показывает, что хроматическое число его графа пересечений также произвольно велико. Следовательно, это означает, что выровненные по оси прямоугольники в а также отрезки в не χ-ограничены . [8]
Согласно теореме Брукса графы с высоким хроматическим числом должны иметь высокую максимальную степень. Но раскрашиваемость не является полностью локальным явлением: граф с большим обхватом выглядит локально как дерево, потому что все циклы длинные, но его хроматическое число не обязательно равно 2:
- Теорема ( Эрдеш ): существуют графы сколь угодно большого обхвата и хроматического числа. [9]
Границы хроматического индекса
Раскраска ребер графа G - это раскраска вершин его линейного графа , и наоборот. Таким образом,
Существует сильная взаимосвязь между раскрашиваемостью ребер и максимальной степенью графа. . Поскольку все ребра, инцидентные одной вершине, должны иметь свой цвет, мы имеем
Более того,
- Теорема Кёнига :если G двудольный.
В общем, связь даже сильнее, чем то, что дает теорема Брукса для раскраски вершин:
- Теорема Визинга: график максимальной степени имеет краевое хроматическое число или же .
Прочие свойства
Граф имеет k- раскраску тогда и только тогда, когда он имеет ациклическую ориентацию, для которой самый длинный путь имеет длину не больше k ; это теорема Галлаи – Хассе – Роя – Витавера ( Nešetřil & Ossona de Mendez 2012 ).
Для плоских графов раскраски вершин по существу двойственны потокам нигде-нулю .
О бесконечных графах известно гораздо меньше. Ниже приведены два из немногих результатов о раскраске бесконечного графа:
- Если все конечные подграфы с бесконечным графом G являются к -раскрашиваемому, то и G , при предположении аксиомы выбора . Это де Брейна-Erdős теорема о де Брейна и Эрдёша (1951) .
- Если граф допускает полную n- раскраску для любого n ≥ n 0 , он допускает бесконечную полную раскраску ( Fawcett 1978 ).
Открытые проблемы
Как указано выше, Гипотеза Рида от 1998 г. состоит в том, что значение существенно ближе к нижней границе,
Хроматическим числом плоскости , где две точки смежны , если они имеют единичную расстояние, неизвестно, хотя это один из 5, 6 или 7. Другие открытые проблемы , касающиеся хроматического числа графов включают гипотезу хадвигеровского о том , что каждый граф с хроматическим числом k имеет полный граф на k вершинах в качестве минора , гипотеза Эрдеша – Фабера – Ловаса, ограничивающая хроматическое число объединений полных графов, имеющих не более одной общей вершины для каждой пары, и гипотеза Альбертсона, что среди k -хроматические графы: полные графы - это графы с наименьшим числом пересечений .
Когда Биркгоф и Льюис ввели хроматический полином в своей атаке на теорему о четырех цветах, они предположили, что для плоских графов G полином не имеет нулей в регионе . Хотя известно, что такой хроматический многочлен не имеет нулей в области и это , их гипотеза до сих пор не решена. Также остается нерешенной проблема характеризовать графы, которые имеют один и тот же хроматический многочлен, и определять, какие многочлены являются хроматическими.
Алгоритмы
Раскраска графика | |
---|---|
Решение | |
Имя | Раскраска графов, раскраска вершин, k -раскраска |
Вход | Граф G с n вершинами. Целое число k |
Выход | Допускает ли G правильную раскраску вершин в k цветов? |
Продолжительность | O (2 n n ) [10] |
Сложность | НП-полный |
Снижение с | 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 цветов n вершинам и проверяет допустимость каждой из них. Чтобы вычислить хроматическое число и хроматический полином, эта процедура используется для каждого, непрактично для всех входных графиков, кроме самых маленьких.
Используя динамическое программирование и ограничение числа максимальных независимых множеств , k- раскрашиваемость может быть определена во времени и пространстве.. [11] Используя принцип включения-исключения и алгоритм Йейтса для быстрого дзета-преобразования, k- раскрашиваемость может быть определена во времени.[10] для любого k . Более быстрые алгоритмы известны своей трех- и четырехкратной окраской, которую можно решить вовремя.[12] и, [13] соответственно.
Сокращение
сокращение графа G - это граф, полученный отождествлением вершин u и v и удалением всех ребер между ними. Остальные ребра, изначально инцидентные u или v , теперь инцидентны их идентификации. Эта операция играет важную роль при анализе раскраски графов.
Хроматическое число удовлетворяет рекуррентному соотношению :
в связи с Зыков (1949) , где U и V являются несмежные вершины, и- граф с добавленным ребром uv . Несколько алгоритмов основаны на оценке этой повторяемости, и результирующее дерево вычислений иногда называют деревом Зыкова. Время работы основано на эвристике выбора вершин u и v .
Хроматический полином удовлетворяет следующему рекуррентному соотношению
где u и v - смежные вершины, а- граф с удаленным ребром uv .представляет собой количество возможных правильных раскрасок графа, где вершины могут иметь одинаковый или разные цвета. Тогда правильные раскраски возникают из двух разных графов. Чтобы объяснить, что если вершины u и v имеют разные цвета, мы могли бы также рассмотреть граф, в котором u и v смежны. Если u и v имеют одинаковые цвета, мы могли бы также рассмотреть граф, в котором u и v сжаты. Любопытство Тутте по поводу того, какие другие свойства графа удовлетворяют эту повторяемость, привело его к открытию двумерного обобщения хроматического полинома, полинома Тутте .
Эти выражения порождают рекурсивную процедуру, называемую алгоритмом удаления-сжатия , которая составляет основу многих алгоритмов раскраски графов. Время выполнения удовлетворяет тому же рекуррентному соотношению, что и числа Фибоначчи , поэтому в худшем случае алгоритм работает во времени с полиномиальным множителемдля n вершин и m ребер. [14] Анализ можно улучшить с точностью до полиномиального множителя числаиз остовных деревьев входного графа. [15] На практике используются стратегии ветвей и границ и отказ от изоморфизма графов , чтобы избежать некоторых рекурсивных вызовов. Время выполнения зависит от эвристики, используемой для выбора пары вершин.
Жадная раскраска
Жадный алгоритм рассматривает вершины в определенном порядке,…, и присваивает наименьший доступный цвет, не используемый соседи среди ,…,, при необходимости добавив свежий цвет. Качество получаемой окраски зависит от выбранной вами расцветки. Существует упорядочение, которое приводит к жадной раскраске с оптимальным количествомцвета. С другой стороны, жадные раскраски могут быть сколь угодно плохими; например, граф короны на n вершинах может быть двухцветным, но имеет порядок, который приводит к жадной раскраске с цвета.
Для хордовых графов и для особых случаев хордовых графов, таких как интервальные графы и графы безразличия , алгоритм жадной раскраски может использоваться для поиска оптимальных раскрасок за полиномиальное время, выбирая порядок вершин, обратный порядку идеального исключения для график. В совершенно упорядочиваемые графики обобщать это свойство, но это NP-трудно найти идеальный порядок этих графиков.
Если вершины упорядочены в соответствии с их степенями , в результирующей жадной раскраске используется не болеецветов, не более чем на единицу больше максимальной степени графика. Эту эвристику иногда называют алгоритмом Уэлша – Пауэлла. [16] Другая эвристика, предложенная Брюла, устанавливает порядок динамически, пока алгоритм продолжает работу, выбирая следующую вершину, смежную с наибольшим числом разных цветов. [17] Многие другие эвристики раскраски графов аналогичным образом основаны на жадной раскраске для конкретной статической или динамической стратегии упорядочивания вершин, эти алгоритмы иногда называют алгоритмами последовательной раскраски .
Максимальное (наихудшее) количество цветов, которое может быть получено с помощью жадного алгоритма, используя порядок вершин, выбранный для максимизации этого числа, называется числом Гранди графа.
Параллельные и распределенные алгоритмы
В области распределенных алгоритмов раскраска графов тесно связана с проблемой нарушения симметрии . Современные рандомизированные алгоритмы быстрее при достаточно большой максимальной степени Δ, чем детерминированные алгоритмы. Самые быстрые рандомизированные алгоритмы используют технику множественных испытаний Schneider et al. [18]
В симметричном графе , A детерминированный распределенный алгоритм не может найти подходящую вершину окраски. Некоторая вспомогательная информация необходима, чтобы нарушить симметрию. Стандартное предположение состоит в том, что изначально каждый узел имеет уникальный идентификатор , например, из набора {1, 2, ..., n }. Иначе говоря, мы предполагаем, что нам дана n- раскраска. Задача состоит в том, чтобы уменьшить количество цветов с n , например, до Δ + 1. Чем больше цветов используется, например, O (Δ) вместо Δ + 1, тем меньше циклов связи требуется. [18]
Прямая распределенная версия жадного алгоритма (Δ + 1) -раскраски требует Θ ( n ) раундов связи в худшем случае - может потребоваться распространение информации с одной стороны сети на другую.
Простейший интересный случай представляет собой п - цикл . Ричард Коул и Узи Вишкин [19] показывают, что существует распределенный алгоритм, который уменьшает количество цветов с n до O (log n ) за один синхронный шаг связи. Повторяя ту же процедуру, можно получить 3-цветную раскраску n -цикла за O ( log * n ) шагов связи (при условии, что у нас есть уникальные идентификаторы узлов).
Функция log * , повторный логарифм , является чрезвычайно медленно растущей функцией, «почти постоянной». Следовательно, результат Коула и Вишкина поднял вопрос о том, существует ли распределенный алгоритм с постоянным временем для 3-раскраски n -цикла. Linial (1992) показал, что это невозможно: любой детерминированный распределенный алгоритм требует Ω ( log * n ) шагов связи, чтобы свести n- раскраску к 3-раскраске в n -цикле.
Технику Коула и Вишкина можно применять и к произвольным графам ограниченной степени; время работы - poly (Δ) + O ( log * n ). [20] Метод был распространен на графы единичных дисков Шнайдером и др. [21] Самые быстрые детерминированные алгоритмы (Δ + 1) -раскрашивания для малых Δ принадлежат Леониду Баренбойму, Майклу Элькину и Фабиану Куну. [22] Алгоритм Баренбойма и др. выполняется за время O (Δ) + log * ( n ) / 2, что является оптимальным с точки зрения n, поскольку постоянный множитель 1/2 не может быть улучшен из-за нижней границы Линиала. Панконези и Сринивасан (1996) используют разложение сети для вычисления раскраски Δ + 1 во времени..
Проблема раскраски ребер также изучалась в распределенной модели. Panconesi и Rizzi (2001) достигли (2Δ - 1) -раскрашивания за время O (Δ + log * n ) в этой модели. Нижняя оценка распределенной раскраски вершин, полученная Линиалом (1992), также применима к проблеме распределенной раскраски ребер.
Децентрализованные алгоритмы
Децентрализованные алгоритмы - это алгоритмы, в которых передача сообщений не разрешена (в отличие от распределенных алгоритмов, где происходит локальная передача сообщений), и существуют эффективные децентрализованные алгоритмы, которые раскрашивают граф, если существует надлежащая раскраска. Они предполагают, что вершина способна определить, использует ли какой-либо из ее соседей тот же цвет, что и вершина, то есть существует ли локальный конфликт. Это умеренное предположение во многих приложениях, например, при распределении беспроводных каналов обычно разумно предположить, что станция сможет обнаружить, используют ли другие мешающие передатчики тот же канал (например, путем измерения SINR). Этой сенсорной информации достаточно, чтобы позволить алгоритмам, основанным на обучающихся автоматах, найти правильную раскраску графа с вероятностью единица. [23]
Вычислительная сложность
Раскраска графов сложна в вычислительном отношении. Это NP-полной , чтобы решить , если данный граф допускает K -раскраска для данного к за исключением случаев , к ∈ {0,1,2}. В частности, вычислить хроматическое число NP-сложно. [24] Проблема 3-раскраски остается NP-полной даже на 4-регулярных планарных графах . [25] Однако для любого k > 3 существует k -раскраска плоского графа по теореме о четырех цветах , и можно найти такую раскраску за полиномиальное время.
Самый известный алгоритм аппроксимации вычисляет раскраску размером не более чем в пределах множителя O ( n (log log n ) 2 (log n) −3 ) от хроматического числа. [26] Для всех х > 0, аппроксимирующех хроматическое число в пределах п 1- е является NP-трудным . [27]
Также NP-сложно раскрасить 3-раскрашиваемый граф в 4 цвета [28] и k- раскрашиваемый граф в k (log k ) / 25 цветов для достаточно большой постоянной k . [29]
Вычисление коэффициентов хроматического полинома является # P-трудным . Фактически, даже вычисляя значениеявляется # P-трудным в любой рациональной точке k, кроме k = 1 и k = 2. [30] Не существует FPRAS для вычисления хроматического полинома в любой рациональной точке k ≥ 1.5, за исключением k = 2, если NP = RP . [31]
Для раскраски краев доказательство результата Визинга дает алгоритм, который использует не более Δ + 1 цветов. Однако выбор между двумя значениями-кандидатами для краевого хроматического числа является NP-полным. [32] Что касается алгоритмов аппроксимации, алгоритм Визинга показывает, что хроматическое число краев может быть аппроксимировано с точностью до 4/3, а результат жесткости показывает, что (4/3 - ε ) -алгоритм не существует для любого ε> 0, если только P = NP . Это одни из самых старых результатов в литературе по аппроксимационным алгоритмам, хотя ни в одной из статей это понятие явно не используется. [33]
Приложения
Планирование
Модели раскраски вершин для ряда задач планирования . [34] В наиболее чистой форме данный набор заданий должен быть назначен временным интервалам, для каждого задания требуется один такой интервал. Задания можно планировать в любом порядке, но пары заданий могут конфликтовать в том смысле, что они не могут быть назначены одному и тому же временному интервалу, например, потому что оба они полагаются на общий ресурс. Соответствующий граф содержит вершину для каждой работы и ребро для каждой конфликтующей пары работ. Хроматическое число графа - это как раз минимальное время изготовления , оптимальное время для завершения всех работ без конфликтов.
Детали задачи планирования определяют структуру графа. Например, при назначении самолетов для полетов результирующий граф конфликтов представляет собой интервальный граф , поэтому проблема раскраски может быть решена эффективно. При распределении полосы пропускания радиостанциям результирующий граф конфликтов представляет собой граф единичного диска , поэтому проблема раскраски является 3-аппроксимируемой.
Распределение регистров
Компилятор представляет собой компьютерную программу , которая переводит один компьютерный язык в другой. Чтобы сократить время выполнения результирующего кода, одним из методов оптимизации компилятора является выделение регистров , при котором наиболее часто используемые значения скомпилированной программы хранятся в регистрах быстрого процессора . В идеале значения назначаются регистрам, чтобы все они могли находиться в регистрах, когда они используются.
Хрестоматийный подход к этой проблеме состоит в моделировании ее как задачи раскраски графа. [35] Компилятор строит интерференционный граф , в котором вершины являются переменными, а ребро соединяет две вершины, если они необходимы одновременно. Если граф можно раскрасить в k цветов, то любой набор переменных, необходимых одновременно, можно сохранить не более чем в k регистрах.
Другие приложения
Проблема раскрашивания графика возникает во многих практических областях, таких как сопоставление с образцом , планирование занятий спортом, разработка планов рассадки, составление расписания экзаменов, расписание такси и решение головоломок судоку . [36]
Другие раскраски
Теория Рамсея
Важный класс проблем несобственной раскраски изучается в теории Рамсея , где ребрам графа присвоены цвета и нет ограничений на цвета инцидентных ребер. Простым примером является теорема о дружбе , которая гласит, что при любой раскраске ребер, полный граф из шести вершин, будет одноцветный треугольник; часто иллюстрируется высказыванием, что в любой группе из шести человек есть либо три общих незнакомца, либо три общих знакомых. Теория Рамсея занимается обобщением этой идеи для поиска регулярности среди беспорядка, поиска общих условий существования монохроматических подграфов с заданной структурой.
Другие раскраски
|
|
Раскраска также может быть рассмотрена для графиков со знаком и графиков усиления .
Смотрите также
- Критический график
- Гомоморфизм графов
- Строительство Hajós
- Математика судоку
- Многостраничный граф
- Уникально раскрашиваемый график
- График раскраски
Заметки
- ^ М. Кубале, История раскраски графов , в Кубале (2004)
- ↑ van Lint & Wilson (2001 , глава 33)
- ↑ Дженсен и Тофт (1995) , стр. 2
- ^ Брукс (1941)
- Перейти ↑ Descartes, Blanche (апрель 1947), «Проблема трех цветов», Eureka , 21
- ^ Скотт, Алекс; Seymour, Пол (2020), "Обзор х-ограниченность", Журнал теории графов , 95 (3): 2-3, DOI : 10.1002 / jgt.22601.
- ^ Берлинг, Джеймс Перкинс (1965), О проблемах окраски семейств прототипов (докторская диссертация) , Боулдер: Университет Колорадо.
- ^ а б Pawlik, A .; Kozik, J .; Krawczyk, T .; Lasoń, M .; Micek, P .; Троттер, В .; Вальчак, Б. (2014), «Бестреугольные графы пересечений отрезков с большим хроматическим числом», Журнал комбинаторной теории , серия B, 105 (5): 6–10, doi : 10.1016 / j.jctb.2013.11. 001
- ^ Erdős, Пол (1959), "Теория графов и вероятность", Canadian Journal математики , 11 : 34-38, DOI : 10,4153 / CJM-1959-003-9.
- ^ a b Björklund, Husfeldt & Koivisto (2009)
- ^ Лоулер (1976)
- ^ Beigel & Эпштайна (2005)
- ^ Фомина, Gaspers & Саурабй (2007)
- ^ Уилф (1986)
- ^ Sekine, Имаи & Tani (1995)
- ↑ Валлийский и Пауэлл (1967)
- ^ Brélaz (1979)
- ^ а б Шнайдер (2010)
- ↑ Cole & Vishkin (1986) , см. Также Cormen, Leiserson & Rivest (1990 , раздел 30.5).
- ^ Голдберг, Плоткин и Шеннон (1988)
- ^ Шнайдер (2008)
- ^ Баренбойм и Элькин (2009) ; Кун (2009)
- ^ Например, см. Leith & Clifford (2006) и Duffy, O'Connell & Sapozhnikov (2008) .
- ^ Garey, Johnson & Stockmeyer (1974) ; Гэри и Джонсон (1979) .
- ^ Дейли (1980)
- ^ Halldórsson (1993)
- ^ Цукерман (2007)
- ^ Гурусва & Кхан (2000)
- ^ Хот (2001)
- ^ Jaeger, Vertigan & Валлийский (1990)
- ^ Голдберг и Джеррам (2008)
- ^ Холиер (1981)
- ^ Крешенци & Kann (1998)
- ^ Маркс (2004)
- ^ Хайтина (1982)
- ^ Льюис, Р. Руководство по раскраске графов: алгоритмы и приложения . Издательство Springer International, 2015.
Рекомендации
- Barenboim, L .; Элькин, М. (2009), «Распределенная (Δ + 1) -раскраска за линейное (в Δ) время», Труды 41-го симпозиума по теории вычислений , стр. 111–120, arXiv : 0812.1379 , doi : 10.1145 / 1536414.1536432 , ISBN 978-1-60558-506-2, S2CID 13446345
- Beigel, R .; Эппштейн, Д. (2005), «3-раскраска во времени O (1,3289 n )», Журнал алгоритмов , 54 (2)): 168–204, arXiv : cs / 0006046 , doi : 10.1016 / j.jalgor.2004.06 .008 , S2CID 1209067
- Björklund, A .; Husfeldt, T .; Коивисто, М. (2009), "Установить разделение с помощью включения-исключения", SIAM журнал по вычислениям , 39 (2): 546-563, DOI : 10,1137 / 070683933
- Brélaz, D. (1979), "Новые методы цвет вершин графа", Communications по АКМ , 22 (4): 251-256, DOI : 10,1145 / 359094,359101 , S2CID 14838769
- Брукс, Р.Л. (1941), «О раскрашивании узлов сети», Труды Кембриджского философского общества , 37 (2): 194–197, Bibcode : 1941PCPS ... 37..194B , doi : 10.1017 / S030500410002168X
- de Bruijn, NG ; Эрдеш, П. (1951), "Проблема цвета для бесконечных графов и проблема теории отношений" (PDF) , Nederl. Акад. Wetensch. Proc. Сер. , 54 : 371-373, DOI : 10.1016 / S1385-7258 (51) 50053-7 , заархивированы от оригинала (PDF) на 2016-03-10 , извлекаются 2009-05-16(= Indag. Math. 13 )
- Бысков, JM (2004), "Перечисление максимальных независимых множеств с приложениями к раскраске графов", Operations Research Letters , 32 (6): 547–556, doi : 10.1016 / j.orl.2004.03.002
- Chaitin, GJ (1982), "Размещение регистров и распространение через раскраску графа", Proc. 1982 SIGPLAN симпозиум по Compiler Construction ., Стр 98-105, DOI : 10,1145 / 800230,806984 , ISBN 0-89791-074-5, S2CID 16872867
- Cole, R .; Vishkin, У. (1986), "Детерминированная монета бросание с приложениями к оптимальному списку параллельного рейтинга", информация и управление , 70 (1): 32-53, DOI : 10.1016 / S0019-9958 (86) 80023-7
- Кормен, TH; Лейзерсон, CE; Ривест, Р.Л. (1990), Введение в алгоритмы (1-е изд.), MIT Press
- Crescenzi, P .; Канн, В. (декабрь 1998 г.), "Как найти результаты наилучшего приближения - продолжение Гэри и Джонсона", ACM SIGACT News , 29 (4): 90, doi : 10.1145 / 306198.306210 , S2CID 15748200
- Дейли, Д.П. (1980), "Уникальность раскрашиваемости и раскрашиваемость плоских 4-регулярных графов NP-полна", Дискретная математика , 30 (3): 289–293, DOI : 10.1016 / 0012-365X (80) 90236-8
- Даффи, К .; O'Connell, N .; Сапожников, А. (2008), «Анализ сложности децентрализованного алгоритма раскраски графа» (PDF) , Письма об обработке информации , 107 (2): 60–63, DOI : 10.1016 / j.ipl.2008.01.002
- Fawcett, BW (1978), "О бесконечных полных раскрасках графов", Can. J. Math. , 30 (3): 455-457, DOI : 10,4153 / CJM-1978-039-8
- Фомина, FV ; Гасперс, С .; Саураб, С. (2007), «Улучшенные точные алгоритмы для подсчета 3- и 4-раскрасок», Proc. 13-я ежегодная международная конференция, COCOON 2007 , конспект лекций по информатике , 4598 , Springer, стр. 65–74, DOI : 10.1007 / 978-3-540-73545-8_9 , ISBN 978-3-540-73544-1
- Garey, MR ; Джонсон, Д.С. (1979), Компьютеры и несговорчивость: Руководство по теории NP-полноты , WH Freeman, ISBN 0-7167-1045-5
- Garey, MR ; Джонсон, DS ; Стокмайер, Л. (1974), «Некоторые упрощенные NP-полные задачи», Труды шестой ежегодной ACM симпозиум по теории вычислений , стр 47-63,. DOI : 10,1145 / 800119,803884 , S2CID 207693360
- Goldberg, LA ; Джеррам, М. (июль 2008 г.), «Неприблизимость многочлена Тутте», Информация и вычисления , 206 (7): 908–929, arXiv : cs / 0605140 , doi : 10.1016 / j.ic.2008.04.003 , S2CID 53304001
- Гольдберг, А.В .; Плоткин С.А.; Shannon, GE (1988), "Параллель нарушения симметрии в разреженных графов" , SIAM журнал по дискретной математике , 1 (4): 434-446, DOI : 10,1137 / 0401044
- Гурусвами, V .; Кханна, С. (2000), "О твердости 4-раскраски 3-раскраску графа", Труды 15 - й ежегодный IEEE конференция по вычислительной сложности , С. 188-197,. DOI : 10.1109 / CCC.2000.856749 , ISBN 0-7695-0674-7, S2CID 47551585
- Halldórsson, MM (1993), «Еще лучшая гарантия производительности для приблизительной раскраски графа», Information Processing Letters , 45 : 19–23, DOI : 10.1016 / 0020-0190 (93) 90246-6
- Holyer, И. (1981), "NP-полнота края раскраска", SIAM журнал по вычислениям , 10 (4): 718-720, DOI : 10,1137 / 0210055
- Jaeger, F .; Вертиган, DL; Уэлш, DJA (1990), «О вычислительной сложности многочленов Джонса и Тутте», Математические слушания Кембриджского философского общества , 108 (1): 35–53, Bibcode : 1990MPCPS.108 ... 35J , doi : 10.1017 / S0305004100068936
- Дженсен, TR; Тофт, Б. (1995), Проблемы раскраски графов , Wiley-Interscience, Нью-Йорк, ISBN 0-471-02865-7
- Khot, S. (2001), "Улучшенные результаты неаппроксимируемости для MaxClique, хроматического числа и приближенной окраски графа", Proc. 42-й ежегодный симпозиум по основам компьютерных наук , стр. 600–609, DOI : 10.1109 / SFCS.2001.959936 , ISBN 0-7695-1116-3, S2CID 11987483
- Кубале, М. (2004), Раскраски графиков, Американское математическое общество, ISBN 0-8218-3458-4
- Куна, Ф. (2009), «Слабая раскраска графы: распределенные алгоритмы и их применение», Труды 21 - го симпозиума по Параллельности в алгоритмах и архитектурах , С. 138-144,. DOI : 10,1145 / 1583991,1584032 , ISBN 978-1-60558-606-9, S2CID 8857534
- Лоулер, EL (1976), «Заметка о сложности проблемы хроматического числа», Информационные письма , 5 (3): 66–67, DOI : 10.1016 / 0020-0190 (76) 90065-X
- Лейт, диджей; Клиффорд, П. (2006), "Самоуправляемый алгоритм выбора распределенного канала для WLAN", Proc. RAWNET 2006, Бостон, Массачусетс (PDF) , дата обращения 03.03.2016
- Льюис, RMR (2016), Руководство по раскрашиванию графиков: алгоритмы и приложения , Springer International Publishing, ISBN 978-3-319-25728-0
- Linial, Н. (1992), "Местность в распределенных алгоритмов графа", SIAM журнал по вычислениям , 21 (1): 193-201, CiteSeerX 10.1.1.471.6378 , DOI : 10,1137 / 0221015
- ван Линт, JH; Уилсон, Р.М. (2001), Курс комбинаторики (2-е изд.), Cambridge University Press, ISBN 0-521-80340-3
- Маркс, Даниэль (2004), «Проблемы раскраски графов и их приложения в планировании», Periodica Polytechnica, Electrical Engineering , 48 , стр. 11–16, CiteSeerX 10.1.1.95.4268
- Mycielski, J. (1955), "Sur le coloriage des graphes" (PDF) , Colloq. Математика. , 3 (2): 161-162, DOI : 10.4064 / см-3-2-161-162.
- Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), «Теорема 3.13», Разреженность: графы, структуры и алгоритмы , алгоритмы и комбинаторика, 28 , Гейдельберг: Спрингер, стр. 42, DOI : 10.1007 / 978-3-642-27875-4 , ЛВП : 10338.dmlcz / 143192 , ISBN 978-3-642-27874-7, MR 2920058.
- Панконези, Алессандро; Рицци, Ромео (2001), «Некоторые простые распределенные алгоритмы для разреженных сетей» (PDF) , Распределенные вычисления , Берлин, Нью-Йорк: Springer-Verlag , 14 (2): 97–100, doi : 10.1007 / PL00008932 , ISSN 0178- 2770 , S2CID 17661948
- Panconesi, A .; Сринивасан, А. (1996), "О сложности декомпозиции распределенной сети", Журнал алгоритмов , 20
- Секин, К .; Imai, H .; Тани, С. (1995), "Вычисление полинома Тутте графа среднего размера", Proc. 6 - й Международный симпозиум по алгоритмам и вычислениям (ISAAC 1995) , Lecture Notes в области компьютерных наук , 1004 , Springer, С. 224-233,. DOI : 10.1007 / BFb0015427 , ISBN 3-540-60573-8
- Шнайдер, Дж. (2010), «Новая техника для нарушения распределенной симметрии» (PDF) , Труды симпозиума по принципам распределенных вычислений
- Шнайдер, Дж. (2008), "Лог-звездный алгоритм максимального независимого множества для графов с ограниченным ростом" (PDF) , Труды симпозиума по принципам распределенных вычислений
- Валлийский, DJA; Пауэлл, МБ (1967), «Верхняя граница хроматического числа графа и его применение к задачам планирования», Компьютерный журнал , 10 (1): 85–86, DOI : 10.1093 / comjnl / 10.1.85
- Уэст, DB (1996), Введение в теорию графов , Prentice-Hall, ISBN 0-13-227828-6
- Уилф, HS (1986), Алгоритмы и сложность , Прентис – Холл
- Цукерман, D. (2007), "Линейные степени экстракторов и inapproximability Макса клики и хроматическое число", теории вычислений , 3 : 103-128, DOI : 10.4086 / toc.2007.v003a006
- Зыков А.А. О некоторых свойствах линейных комплексов // Матем. Сборник , Новые серии, 24 (66): 163–188, MR 0035428. Переведен на английский на амер. Математика. Soc. Перевод , 1952, MR0051516 .
Внешние ссылки
- Высокопроизводительные алгоритмы раскраски графов Набор из 8 различных алгоритмов (реализованных на C ++), используемых в книге «Руководство по раскраске графов: алгоритмы и приложения» (Springer International Publishers, 2015).
- Graph Coloring Page от Джозефа Калберсона (программы раскраски графиков)
- CoLoRaTiOn Джима Эндрюса и Майка Феллоуза - это головоломка с раскраской графиков.
- Ссылки на исходные коды Graph Coloring
- Код для эффективного вычисления Тутте, Хроматических полиномов и Полиномов потока от Гэри Хаггарда, Дэвида Дж. Пирса и Гордона Ройла
- Веб-приложение для раскраски графов от Хосе Антонио Мартина Х.