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

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

История

Истоки теории хроматических чисел лежат в знаменитой «проблеме четырёх красок», сформулированной в середине XIX века. В 1852 году Фрэнсис Гутри, пытаясь раскрасить карту графств Англии, заметил, что для любой карты на плоскости достаточно четырёх цветов, чтобы соседние области не совпадали по цвету. Задача сводилась к раскраске вершин планарного графа. В 1879 году Альфред Кемпе опубликовал ошибочное доказательство, которое было опровергнуто в 1890 году Перси Хивудом, который, однако, установил, что для планарных графов достаточно пяти цветов (теорема о пяти красках). Полное доказательство теоремы четырёх красок было получено только в 1976 году Кеннетом Аппелем и Вольфгангом Хакеном с использованием компьютерного перебора, что вызвало дискуссии о природе математического доказательства. В XX веке изучение хроматического числа стало самостоятельной областью, тесно связанной с алгебраической топологией, теорией Рамсея и алгоритмами.

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

Пусть G = (V, E) — неориентированный граф без петель и кратных рёбер. Правильная раскраска вершин — это отображение f: V → {1, 2, …, k}, такое что для любого ребра (u, v) ∈ E выполняется f(u) ≠ f(v). Хроматическое число χ(G) — это наименьшее k, для которого существует правильная раскраска.

Если χ(G) = k, граф называется k-хроматическим. Если χ(G) ≤ k, граф называется k-раскрашиваемым.

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

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

Свойства и оценки

Хроматическое число графа обладает рядом важных свойств и допускает различные оценки.

Нижние оценки

• Кликовое число: Если граф содержит клику (полный подграф) размера ω(G), то χ(G) ≥ ω(G), так как все вершины клики должны быть разного цвета. Однако равенство выполняется не всегда (например, для циклов нечётной длины χ = 3, а ω = 2).
• Хроматическое число и степень: χ(G) ≥ n / α(G), где n — число вершин, а α(G) — число независимости (максимальный размер множества вершин, не соединённых рёбрами). Это следует из того, что каждый цветовой класс является независимым множеством.
• Алгебраическая связь: χ(G) ≥ 1 + λ_max / |λ_min|, где λ_max и λ_min — наибольшее и наименьшее собственные значения матрицы смежности графа (теорема Хоффмана).

Верхние оценки

• Жадная раскраска: Если вершины графа упорядочены произвольным образом, то жадный алгоритм (окрашивание каждой вершины в минимальный доступный цвет) использует не более Δ(G) + 1 цвета, где Δ(G) — максимальная степень вершины. Следовательно, χ(G) ≤ Δ(G) + 1. Для полных графов и нечётных циклов эта оценка точна (теорема Брукса, 1941).
• Теорема Брукса: Для любого связного графа G, не являющегося полным графом или нечётным циклом, выполняется χ(G) ≤ Δ(G).
• Число Рамсея: Хроматическое число связано с числами Рамсея: если граф не содержит полного подграфа размера k, то его хроматическое число может быть сколь угодно велико (теорема Эрдёша, 1959).

Классификация графов по хроматическому числу

Графы делятся на несколько классов в зависимости от значения χ(G):

• 1-хроматические графы: Графы без рёбер (пустые графы). Любая вершина может быть окрашена в один цвет, так как нет смежных вершин.
• 2-хроматические графы: Это в точности двудольные графы. К ним относятся деревья, чётные циклы, полные двудольные графы K_{m,n}. Критерий: граф является двудольным тогда и только тогда, когда он не содержит циклов нечётной длины.
• 3-хроматические графы: Включают нечётные циклы (C_5, C_7, …), граф Петерсена, а также некоторые планарные графы, для которых трёх цветов недостаточно (например, граф Грёча).
• 4-хроматические графы: Классический пример — полный граф K_4. Согласно теореме о четырёх красках, любой планарный граф имеет χ(G) ≤ 4. Существуют планарные графы, для которых χ(G) = 4 (например, граф, двойственный карте с четырьмя взаимно граничащими областями).

Алгоритмы вычисления

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

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

• Перебор с возвратом (backtracking): Алгоритм, основанный на рекурсивном переборе всех возможных раскрасок. Для графов с небольшим числом вершин (до 20–30) может быть эффективным.
• Алгоритм с использованием независимых множеств: Поиск максимальных независимых множеств и их комбинаций.
• Алгоритм Брона — Кербоша: Используется для поиска всех клик, что может помочь в оценке нижней границы.

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

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

Применение

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

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

Классическая задача: распределить экзамены по временным слотам так, чтобы ни один студент не сдавал два экзамена одновременно. Вершины графа — экзамены, рёбра соединяют экзамены, которые не могут проходить одновременно (например, из-за пересечения по студентам). Хроматическое число графа даёт минимальное количество временных слотов.

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

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

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

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

Картография

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

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

• Существуют графы с произвольно большим хроматическим числом, не содержащие треугольников (клик размера 3). Первый такой пример был построен А. А. Зыковым в 1949 году.
• Хроматическое число графа может быть сколь угодно большим, даже если его обхват (длина минимального цикла) также сколь угодно велик (теорема Эрдёша, 1959).
• Проблема четырёх красок оставалась нерешённой более 120 лет и была доказана с помощью компьютера, что вызвало споры о допустимости компьютерных доказательств в математике.
• Хроматический многочлен графа — это многочлен P(G, k), который для данного k показывает количество правильных раскрасок вершин в k цветов. Например, для полного графа K_n P(K_n, k) = k(k-1)...(k-n+1).

Источники

• Харари Ф. Теория графов. — М.: Мир, 1973.
• Дистель Р. Теория графов. — Новосибирск: Изд-во Ин-та математики, 2002.
• Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. — М.: Наука, 1990.
• Bondy J. A., Murty U. S. R. Graph Theory. — Springer, 2008.
• Appel K., Haken W. Every planar map is four colorable. — Bulletin of the American Mathematical Society, 1976.