Задача о раскраске графа

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

История

Истоки задачи о раскраске графа восходят к картографической раскраске. В 1852 году Фрэнсис Гутри, студент Университетского колледжа Лондона, заметил, что для раскраски карты графств Англии достаточно четырёх цветов, чтобы никакие две соседние области не были одного цвета. Он задался вопросом, всегда ли это верно. Эта проблема, известная как проблема четырёх красок, стала одной из самых знаменитых в математике. Формально она была сформулирована как задача о раскраске планарного графа (графа, который можно нарисовать на плоскости без пересечения рёбер). В 1976 году Кеннет Аппель и Вольфганг Хакен из Иллинойского университета доказали теорему о четырёх красках, используя компьютерный перебор 1936 конфигураций. Это доказательство стало первым крупным математическим доказательством, выполненным с помощью компьютера, и вызвало споры о его приемлемости.

В 1879 году Альфред Кемп опубликовал «доказательство» теоремы о четырёх красках, которое через 11 лет было опровергнуто Перси Хивудом. Хивуд показал, что для планарных графов достаточно пяти цветов (теорема о пяти красках), и ввёл понятие хроматического числа. Развитие теории графов в XX веке привело к формализации задачи о раскраске в общем виде, а в 1972 году Ричард Карп включил задачу о раскраске графа (в формулировке «3-раскрашиваемость») в список 21 NP-полной задачи Карпа, что доказало её вычислительную сложность.

Основные определения

Вершинная раскраска

Правильная вершинная раскраска графа G = (V, E) — это отображение f: V → C, где C — множество цветов, такое, что для любого ребра (u, v) ∈ E выполняется f(u) ≠ f(v). Если |C| = k, раскраска называется k-раскраской. Граф, допускающий k-раскраску, называется k-раскрашиваемым.

Хроматическое число χ(G) — это наименьшее k, при котором граф является k-раскрашиваемым. Если χ(G) = 2, граф называется двудольным. Если χ(G) ≤ k, граф называется k-хроматическим.

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

Рёберная раскраска — это присвоение цветов рёбрам графа, при котором никакие два ребра, инцидентные одной вершине, не имеют одинакового цвета. Минимальное количество цветов, необходимое для рёберной раскраски, называется хроматическим индексом χ'(G). Теорема Визинга (1964) утверждает, что для любого простого графа χ'(G) равно либо Δ(G) (максимальной степени вершины), либо Δ(G) + 1.

Полная раскраска

Полная раскраска — это раскраска, при которой одновременно раскрашиваются и вершины, и рёбра, причём любые два инцидентных элемента (вершина и ребро) имеют разные цвета, а также два смежных ребра и две смежные вершины.

Классификация и виды задач

Задача о раскраске в k цветов

Это задача разрешения: существует ли для данного графа G и числа k правильная раскраска вершин не более чем k цветами? Для k = 1 задача тривиальна (граф без рёбер). Для k = 2 задача сводится к проверке двудольности графа, что решается за линейное время с помощью поиска в ширину или глубину. Для k ≥ 3 задача является NP-полной.

Задача о нахождении хроматического числа

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

Раскраска планарных графов

Для планарных графов χ(G) ≤ 4 (теорема о четырёх красках). Задача 3-раскрашиваемости планарного графа является NP-полной, что доказано в 1976 году Ларри Стокмейером.

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

Хроматический многочлен P(G, k) — это функция, равная количеству различных правильных раскрасок вершин графа G с использованием ровно k цветов (или не более k цветов, в зависимости от определения). Введён Джорджем Биркгофом в 1912 году для изучения проблемы четырёх красок. Например, для полного графа K_n хроматический многочлен равен k(k-1)(k-2)...(k-n+1).

Применение

Составление расписаний

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

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

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

Регистрация переменных (регистровая раскраска)

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

Судоку

Головоломка судоку является частным случаем задачи о раскраске графа с 9 цветами, где вершины — клетки, а рёбра соединяют клетки, которые не могут содержать одинаковые цифры (строка, столбец, блок 3×3).

Задача о составлении карты

Раскраска политической карты так, чтобы соседние страны имели разные цвета, — классическая задача, приведшая к формулировке проблемы четырёх красок.

Алгоритмы

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

• Поиск с возвратом (Backtracking): Перебор всех возможных назначений цветов вершинам с отсечением ветвей, нарушающих условие правильности. Эффективен для графов небольшого размера (до 30–50 вершин).
• Алгоритм Брона — Кербоша: Используется для нахождения всех максимальных независимых множеств, что может быть применено для раскраски.
• Алгоритм на основе DSATUR (Degree of Saturation): Эвристический точный алгоритм, выбирающий на каждом шаге вершину с наибольшей степенью насыщения (количеством различных цветов среди соседей). Часто работает быстрее простого поиска с возвратом.

Приближённые и эвристические алгоритмы

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

Алгоритмы для специальных классов графов

• Двудольные графы: Раскрашиваются в 2 цвета за линейное время.
• Хордальные графы: Раскрашиваются оптимально с помощью алгоритма, основанного на порядке симплициального удаления вершин.
• Совершенные графы: Для них хроматическое число равно размеру максимальной клики, и раскраска находится за полиномиальное время (теорема о совершенных графах, доказанная Ловасом и Сеймуром).

Сложность

Задача о раскраске графа в общем виде является одной из классических NP-трудных задач. Даже для k = 3 задача определения, является ли граф 3-раскрашиваемым, остаётся NP-полной. Это означает, что не существует известного алгоритма, решающего задачу за полиномиальное время для всех графов, если P ≠ NP. Приближение хроматического числа с точностью до константы также является NP-трудной задачей. Однако для многих специальных классов графов (двудольные, планарные, совершенные) существуют эффективные полиномиальные алгоритмы.

Интересные факты

• Теорема о четырёх красках была первой крупной теоремой, доказанной с помощью компьютера. Её доказательство до сих пор не может быть проверено человеком без компьютера.
• Хроматическое число полного графа K_n равно n.
• Хроматическое число пустого графа (без рёбер) равно 1.
• Граф, хроматическое число которого равно 2, — это в точности двудольный граф, не содержащий нечётных циклов.
• Задача о раскраске графа тесно связана с задачей о клике: χ(G) ≥ ω(G), где ω(G) — размер максимальной клики, но неравенство может быть строгим (например, для графа Грёча с χ = 4 и ω = 3).
• Проблема раскраски карты на торе (поверхности рода 1) требует 7 цветов (теорема Хивуда).

Источники

• Дистель Р. Теория графов. — Новосибирск: Издательство Института математики, 2002.
• Харари Ф. Теория графов. — М.: Мир, 1973.
• Оре О. Теория графов. — М.: Наука, 1980.
• Карп Р. М. Reducibility among combinatorial problems // Complexity of Computer Computations. — Plenum Press, 1972. — С. 85–103.
• Appel K., Haken W. Every planar map is four colorable. — American Mathematical Society, 1989.