Раскраска графа — теоретико-графовая конструкция, частный случай разметки графа. При раскраске элементам графа ставятся в соответствие метки с учётом определённых ограничений; эти метки традиционно называются «цветами». В простейшем случае такой способ окраски вершин графа, при котором любым двум смежным вершинам соответствуют разные цвета, называется раскраской вершин. Аналогично раскраска рёбер присваивает цвет каждому ребру так, чтобы любые два смежных ребра имели разные цвета. Наконец, раскраска областей планарного графа назначает цвет каждой области, так, что каждые две области, имеющие общую границу, не могут иметь одинаковый цвет.
Раскраска вершин — главная задача раскраски графов, все остальные задачи в этой области могут быть сведены к ней. Например, раскраска рёбер графа — это раскраска вершин его рёберного графа, а раскраска областей планарного графа — это раскраска вершин его двойственного графа. Тем не менее, другие проблемы раскраски графов часто ставятся и решаются в изначальной постановке. Причина этого частично заключается в том, что это даёт лучшее представление о происходящем и более показательно, а частично из-за того, что некоторые задачи таким образом решать удобнее (например, раскраска рёбер).
Раскраска графов находит применение и во многих практических областях, а не только в теоретических задачах. Помимо классических типов проблем, различные ограничения могут также быть наложены на граф, на способ присвоения цветов или на сами цвета. Этот метод, например, используется в популярной головоломке Судоку. В этой области всё ещё ведутся активные исследования.
История Первые результаты были получены для плоских графов в задаче раскрашивания карт. Пытаясь раскрасить карту округов Англии, сформулировал проблему четырёх красок, отметив, что четырёх цветов достаточно, чтобы раскрасить карту так, чтобы любые два смежных региона имели разные цвета. Его брат передал вопрос своему учителю по математике, Огастесу де Моргану, который упомянул о нём в своем письме Уильяму Гамильтону в 1852 году. Артур Кэли поднял эту проблему на встрече Лондонского математического сообщества в 1878 году. В том же году Тэйтом было предложено первое решение этой задачи. Раскраску вершин первоначального графа он свел к раскраске рёбер двойственного графа и предположил, что эта задача всегда имеет решение. В 1880 году опубликовал статью, в которой утверждалось, что ему удалось установить результат, и на десятилетие проблема четырёх цветов считалась решённой. За это достижение Кемпе был избран членом Лондонского Королевского общества и позже — президентом Лондонского математического сообщества.
В 1890 году Хивуд нашёл ошибку в доказательстве Кемпе. В этой же статье он доказал теорему пяти красок, показав, что любая плоская карта может быть раскрашена не более, чем пятью цветами. При этом он опирался на идеи Кемпе. В следующем столетии было разработано большое количество теорий в попытках уменьшить минимальное число цветов. Теорема четырёх красок была окончательно доказана в 1977 году учеными и Вольфгангом Хакеном с использованием компьютерного перебора. Идея доказательства во многом опиралась на идеи Хивуда и Кемпе и игнорировала большинство промежуточных исследований. Доказательство теоремы четырёх красок является одним из первых доказательств, в которых был использован компьютер.
В 1912 году Джордж Дэвид Биркхоф предложил использовать для изучения задач раскраски хроматический многочлен, являющийся важной частью в алгебраической теории графов. Хроматический многочлен впоследствии был обобщён Уильямом Таттом (многочлен Татта). Кемпе в 1879 году уже обращал внимание на общий случай, когда граф не являлся плоским. Много результатов обобщений раскраски плоских графов на поверхности более высоких порядков появилось в начале XX века.
В 1960 году сформулировал гипотезу о совершенных графах, мотивированное понятием из теории информации, а именно нулевой ошибкой ёмкости графаC.E. Shannon, "The zero-error capacity of a noisy channel, " IEEE Trans. Information Theory, pp. 8-19, 1956., представленным Шенноном. Утверждение оставалось неподтвержденным на протяжении 40 лет, пока не было доказано как знаменитая строгая теорема о совершенных графах математиками , , Сеймуром и Томасом в 2002 году.
Раскраска графов как алгоритмическая проблема начала изучаться с 1970-х годов: определение хроматического числа — входит в число 21 NP-полных задач Карпа (1972). И примерно в то же время были разработаны разнообразные алгоритмы на базе поиска с возвратом и рекурсивного удаления и стягивания Зыкова. С 1981 года раскраска графа применяется для распределения регистров в компиляторах.
Определение и терминология
Раскраска вершин
Когда говорят о раскраске графов, почти всегда подразумевают под этим раскраску их вершин, то есть присвоение цветовых меток вершинам графа так, чтобы любые две вершины, имеющие общее ребро, имели разные цвета. Так как графы, в которых есть петли, не могут быть раскрашены таким образом, они не являются предметом обсуждения.
Терминология, в которой метки называются цветами, происходит от раскраски политических карт. Такие метки как красный или синий используются, только когда число цветов мало, обычно же подразумевается, что метки являются целыми числами .
Раскраска с использованием цветов называется -раскраской. Наименьшее число цветов, необходимое для раскраски графа , называется его хроматическим числом и часто записывается как . Иногда используется , так как обозначает эйлерову характеристику. Подмножество вершин, выделенных одним цветом, называется цветовым классом, каждый такой класс формирует независимый набор. Таким образом, -раскраска — это то же самое, что и разделение вершин на независимых наборов.
Хроматический многочлен
Хроматический многочлен — функция , которая считает число -раскрасок графа . Из названия следует, что для заданных эта функция является многочленом, зависящим от . Этот факт был обнаружен Биркгофом и Льюисом при попытке доказать гипотезу четырёх красок.
Например, граф на изображении справа может быть раскрашен 12 способами с использованием 3 цветов. Двумя цветами он не может быть окрашен в принципе. Используя 4 цвета, мы получаем 24+4*12 = 72 вариантов раскраски: при использовании всех 4 цветов, есть 4! = 24 корректных способа (каждое присвоение 4 цветов для любого графа из 4 вершин является корректным); и для каждых 3 цветов из этих 4 есть 12 способов раскраски. Тогда для графа в примере таблица чисел корректных раскрасок будет начинаться так:
Доступное число цветов 1 2 3 4 … Количество способов раскраски 0 0 12 72 …
Для графа в примере и, конечно, .
Хроматический многочлен содержит по меньшей мере столько же информации о раскрашиваемости , сколько и хроматическое число. В самом деле, — наименьшее целое положительное число, не являющееся корнем хроматического многочлена: .
+Хроматические многочлены для некоторых графов Треугольный Полный граф Дерево с ребрами Цикл Граф Петерсена
Рёберная раскраска
Рёберная раскраска графа подразумевает под собой назначение цветов ребрам так, что никакие два ребра одного цвета не принадлежат одной вершине. Эта задача эквивалентна разделению множества граней на множества независимых граней. Наименьшее число цветов, необходимое для рёберной раскраски графа — это его хроматический индекс, или рёберное хроматическое число, .
Тотальная раскраска
Тотальная раскраска — один из видов раскраски вершин и рёбер графа. Под ней подразумевают такое присвоение цветов, что ни соседние вершины, ни смежные ребра, ни вершины и ребра, которые их соединяют, не имеют одинакового цвета. Полное хроматическое число графа — это наименьшее число цветов, необходимое для любой полной раскраски.
Свойства Если — пустой граф, то хроматический многочлен обращается в единицу — . Если граф — объединение непересекающихся подграфов и , то его хроматический многочлен является произведением хроматических многочленов подграфов: . Если в есть петля, то хроматический многочлен обращается в нуль —
Назначение всем вершинам разных цветов всегда даёт правильную раскраску, так что.
Единственный вид графов, которые могут быть раскрашены одним цветом — это нулевые графы.
Полный граф , состоящий из вершин требует цветов.
При оптимальной раскраске должно быть по меньшей мере одно ребро из рёбер графа между каждыми двумя цветовыми классами, так что: .
Если является объединением непересекающихся подграфов и , то .
Если содержит клики размера , тогда необходимо минимум цветов для раскраски этой клики, другими словами хроматическое число больше, либо равно кликовому числу: . Для интервальных графов это ограничение точно.
По теореме о четырёх красках, любой плоский граф может быть раскрашен четырьмя цветами.
2-раскрашиваемые графы — это двудольные графы, в том числе и деревья.
Граф является двудольным в том и только в том случае, если он не содержит циклов нечётной длины.
Жадная раскраска показывает, что любой граф может быть раскрашен при использовании на один цвет больше, чем его максимальная степень вершины: .
Полные графы имеют и , графы-циклы имеют и , так что для них это ограничение является наилучшим, во всех других случаях, ограничение может быть улучшено: теорема Брукса утверждает, что для связанного, простого графа , если не является ни полным графом, ни графов-циклом.
Графы с большим хроматическим числом Графы с большими кликами имеют большое хроматическое число, но обратное утверждение не всегда верно. Граф Грёча — это пример 4-раскрашиваемого графа без треугольников, и этот пример может быть обобщён на граф Мычельского. Теорема Мычельского (впервые установлена Зыковым в 1949 году, опубликована Мычельским в 1955 году): существуют графы без треугольников со сколь угодно большими хроматическими числами.
Из теоремы Брукса следует, что графы с большим хроматическим числом должны иметь высокую максимальную степень вершины. Другое локальное условие, из-за которого хроматическое число может быть большим — это наличие большой клики. Но раскрашиваемость графа зависит не только от локальных условий: граф с большим обхватом локально выглядит как дерево, так все циклы длинные, но его хроматическое число не равно 2: cуществуют графы со сколь угодно большим обхватом и хроматическим числом (Эрдёш).
Ограничения на хроматический индекс Рёберная раскраска — это раскраска вершин его линейного графа :
Более того, имеет место теорема Кёнига: , если — двудольный.
В общем случае, связь намного сильнее, чем даёт теорема Брукса для раскраски вершин: граф с максимальной степенью вершины имеет рёберное хроматическое число или (теорема Визинга).
Другие свойства Граф является -хроматическим тогда и только тогда, когда он имеет ациклическую ориентацию, для которой длина наибольшего пути равна . Это было доказано в теореме Галлаи — Хассе — Роя — Витавера.
Для плоских графов, раскраска вершин двойственно эквивалентна нигде не нулевому потоку.
О бесконечных графах известно намного меньше. В частности, установлено, что если все конечные подграфы бесконечного графа -хроматические, то и тоже является -хроматическим (доказывается при предположении аксиомы выбора, теорема де Брёйна — Эрдёша. Если граф допускает полную -раскраску для любого , то он допускает бесконечную полную раскраску.
Открытые вопросы Хроматическое число плоскости, в которой две точки являются смежными, если между ними единичное расстояние, неизвестно. Оно может быть равным 5, 6, или 7. Другие открытые вопросы о хроматическом числе графов включают в себя гипотезу Хадвигера, утверждающую, что любой граф с хроматическим числом имеет полный граф из вершин, как его минор, гипотезу Эрдёша — Фабера — Ловаса, которая ограничивает хроматическое число полных графов, которые имеют ровно одну общую вершину для каждой пары графов, и гипотезу Альбертсона о том, что среди -хроматических графов полными являются те, которые имеют наименьшее число пересечений.