Раскраска графов

Корректная раскраска вершин графа наименьшим набором цветов - тремя.

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

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

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

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

История

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

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

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

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

Раскраска графов начала изучаться как алгоритмическая проблема с 1970-х годов: определение хроматического числа — одна из 21 NP-полных задач Карпа с 1972 года.

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

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

Этот граф может быть раскрашен 3 цветами 12 способами.

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

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

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

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

Все не изоморфные графы из 3 вершин и их хроматические многочлены. Пустой граф E₃ (красный) допускает раскраску одним цветом, остальные - нет. Зеленый граф может быть раскрашен 3 цветами 12 способами.

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

Доступное число цветов	1	2	3	4	…
Количество способов раскраски	0	0	12	72	…

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

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

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

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

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

Реберная раскраска

Основная статья: Рёберная раскраска

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

Тотальная раскраска

Основная статья: Тотальная раскраска

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

Свойства

Ограничения на хроматическое число

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

$1\leq \chi (G)\leq n.\,$

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

$\chi (G)(\chi (G)-1)\leq 2m.\,$

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

$\chi (G)\geq \omega (G).\,$

Для интервальных графов это ограничение точно.

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

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

$\chi (G)\leq \Delta (G)+1.\,$

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

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

Графы с большим хроматическим числом

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

Теорема Мыцельского: Существуют графы без треугольников со сколь угодно большими хроматическими числами.

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

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

Ограничения на хроматический индекс

Рёберная раскраска G - это раскраска вершин его линейного графа $L(G)$, и наоборот. То есть,

$\chi '(G)=\chi (L(G)).\,$

Более того,

Теорема Кёнига: $\chi '(G)=\Delta (G)$, если G - двудольный.

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

Теорема Визинга: Граф с максимальной степенью вершины $\Delta$ имеет реберное хроматическое число $\Delta$ или $\Delta +1$.

Другие свойства

Граф является k-хроматическим тогда и только тогда, когда он имеет ациклическую ориентацию, для которой длина наибольшего пути равна k. Это это было доказано в теореме Галлаи-Хассе-Роя-Витавера.Шаблон:-1

Для плоских графов, раскраска вершин эквивалентна везде-ненулевому потоку.

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

• Если все конечные подграфы бесконечного графа G k-хроматические, то и G тоже является k-хроматическим, по предположению аксиомы выбора. Это - формулировка теоремы Дэ Брейна–Эрдуша.Шаблон:-1
• Если граф допускает полную n-раскраску для любого n ≥ n₀, то он допускает бесконечную полную раскраску.Шаблон:-1

Открытые вопросы

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

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

Применение

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

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

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

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

Основная статья: Распределение регистров

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

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

Другие применения

Задача раскраски графов была поставлена во многих других областях применения, включая сравнение с шаблоном.

Решение головоломки Судоку можно рассматривать как завершение раскраски 9 цветами заданного графа из 81 вершины.