Раскраска графика

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

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

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

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

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

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

История [ править ]

Первые результаты о раскраске графов касаются почти исключительно плоских графов в форме раскраски карт . Пытаясь раскрасить карту графств Англии, Фрэнсис Гатри выдвинул гипотезу о четырех цветах, отметив, что четырех цветов достаточно для раскрашивания карты, так что ни один регион, имеющий общую границу, не получил одного цвета. Брат Гатри передал этот вопрос своему учителю математики Августу де Моргану из Университетского колледжа , который упомянул его в письме Уильяму Гамильтону в 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 допустимых трехцветных раскрасок. Итак, для графика в примере таблица количества допустимых раскрасок должна начинаться так:

Хроматический многочлен является функцией Р ( О ,  т ) , что подсчитывает количество т -раскраску  G . Как видно из названия, для данного G функция действительно является многочленом в  т . Для графа-примера P ( G ,  t ) =  t ( t  - 1) ² ( t  - 2), и действительно,  P ( G , 4) = 72.

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

${\displaystyle \chi (G)=\min\{k\,\colon \,P(G,k)>0\}.}$

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

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

Раскраска краев [ править ]

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

Полная окраска [ править ]

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

Без названия [ править ]

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

Свойства [ править ]

Верхние границы хроматического числа [ править ]

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

${\displaystyle 1\leq \chi (G)\leq n.}$

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

${\displaystyle \chi (G)(\chi (G)-1)\leq 2m.}$

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

${\displaystyle \chi (G)\geq \omega (G).}$

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

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

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

${\displaystyle \chi (G)\leq \Delta (G)+1.}$

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

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

Нижние границы хроматического числа [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Границы хроматического индекса [ править ]

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

${\displaystyle \chi '(G)=\chi (L(G)).}$

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

${\displaystyle \chi '(G)\geq \Delta (G).}$

Более того,

Теорема Кёнига : если G двудольна.${\displaystyle \chi '(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 \omega (G)\leq \chi (G)\leq \Delta (G)+1.}$${\displaystyle \chi (G)\leq \left\lceil {\frac {\omega (G)+\Delta (G)+1}{2}}\right\rceil .}$

Хроматическим числом плоскости , где две точки смежны , если они имеют единичную расстояние, неизвестно, хотя это один из 5, 6 или 7. Другие открытые проблемы , касающиеся хроматического числа графов включают гипотезу хадвигеровского о том , что каждый граф с хроматическим числом к имеет полный граф на K вершинах как несовершеннолетнему , то Erdős-Faber-Lovász гипотеза ограничивающей хроматическое число объединений полных графов , которые имеют не более одной общей вершину каждую пару, а Альбертсон предположение , что среди к -хроматические графы, полные графы - это графы с наименьшимномер перехода .

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

Алгоритмы [ править ]

Полиномиальное время [ править ]

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

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

Точные алгоритмы [ править ]

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

Используя динамическое программирование и ограничение количества максимальных независимых множеств , k- раскрашиваемость может быть определена во времени и пространстве . ^[7] Используя принцип включения-исключения и алгоритм Йейтса для быстрого дзета-преобразования, k- раскрашиваемость может быть определена во времени ^[6] для любого k . Известны более быстрые алгоритмы с возможностью трех- и четырехкратной раскраски, которую можно решить во времени ^[8] и , ^[9] соответственно.${\displaystyle O(2.4423^{n})}$${\displaystyle O(2^{n}n)}$${\displaystyle O(1.3289^{n})}$${\displaystyle O(1.7272^{n})}$

Сокращение [ править ]

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

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

${\displaystyle \chi (G)={\text{min}}\{\chi (G+uv),\chi (G/uv)\}}$

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

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

${\displaystyle P(G-uv,k)=P(G/uv,k)+P(G,k)}$

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

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

Жадная раскраска [ править ]

Две жадные раскраски одного и того же графа с использованием разных порядков вершин. Правый пример обобщается на двукратные графы с 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 \chi (G)}$${\displaystyle n/2}$

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

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

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

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

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

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

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

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

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

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

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

Децентрализованные алгоритмы [ править ]

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

Вычислительная сложность [ править ]

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

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

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

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

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

Приложения [ править ]

Планирование [ править ]

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

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

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

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

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

Другие приложения [ править ]

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

Другие раскраски [ править ]

Теория Рэмси [ править ]

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

Другие раскраски [ править ]

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

См. Также [ править ]

Викискладе есть медиафайлы по теме раскраски графов .

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

Примечания [ править ]

Ссылки [ править ]

Внешние ссылки [ править ]

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