Хроматический полином графа: как считать и применять

Хроматический полином графа $P(G, k)$ отвечает на простой по формулировке вопрос: сколькими способами можно правильно раскрасить вершины графа $G$ в $k$ цветов так, чтобы соседние вершины получили разные цвета. Удивительно, что ответ всегда оказывается многочленом от $k$ - и в этом многочлене зашифровано много структурной информации о графе. Этот объект изучают в курсе дискретной математики и комбинаторики, он связан с хроматическим числом, задачей о четырёх красках и даже со статистической физикой. Разберём определение, способы вычисления и свойства коэффициентов на конкретных примерах.

Что такое правильная раскраска

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

Хроматический полином $P(G, k)$ - это число различных правильных раскрасок графа $G$ в $k$ цветов. Здесь цвета считаются различимыми: перестановка цветов даёт другую раскраску. Например, для графа из двух вершин, соединённых ребром, первую вершину можно покрасить $k$ способами, а вторую - любым из оставшихся $k - 1$ цветов, поэтому $P(G, k) = k(k-1)$.

Чтобы не путаться в рекурсии и сразу увидеть полином для конкретного графа со всеми промежуточными шагами, удобно прогнать пример через инструмент ниже - задайте рёбра и получите разбор.

Базовые примеры

Для простых семейств графов хроматический полином выписывается напрямую.

Пустой граф $\overline{K_n}$ из $n$ вершин без рёбер: каждую вершину красим независимо, поэтому $P(\overline{K_n}, k) = k^n$.

Полный граф $K_n$: все вершины попарно смежны, значит все цвета должны быть разными. Первую вершину красим $k$ способами, вторую - $k - 1$, и так далее:

$P(K_n, k) = k(k-1)(k-2)\cdots(k-n+1).$

Дерево $T$ на $n$ вершинах: корень красим $k$ способами, каждую следующую вершину при обходе - любым из $k - 1$ цветов, отличным от уже окрашенного родителя. Получаем

$P(T, k) = k(k-1)^{n-1}.$

Простой цикл $C_n$ имеет красивую формулу:

$P(C_n, k) = (k-1)^n + (-1)^n (k-1).$

Теорема об удалении и стягивании

Главный универсальный инструмент - рекуррентное соотношение, известное как теорема об удалении и стягивании (deletion–contraction). Для любого ребра $e = uv$ графа $G$ верно

$P(G, k) = P(G - e, k) - P(G / e, k),$

где $G - e$ - граф с удалённым ребром $e$, а $G / e$ - граф, в котором вершины $u$ и $v$ стянуты в одну (а кратные рёбра, если возникли, заменены одним).

Идея проста. Правильные раскраски графа $G - e$ распадаются на два класса: те, где $u$ и $v$ имеют разные цвета (это в точности правильные раскраски $G$), и те, где $u$ и $v$ совпали по цвету (это правильные раскраски $G / e$). Отсюда $P(G - e, k) = P(G, k) + P(G / e, k)$, что и даёт формулу выше. Рекурсию применяют, пока не останутся графы без рёбер, для которых полином равен $k^{\text{(число вершин)}}$.

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

Хроматический полином графа $G$ с $n$ вершинами и $m$ рёбрами - это многочлен степени ровно $n$ со старшим коэффициентом $1$. Его коэффициенты подчиняются нескольким закономерностям:

• Свободный член равен нулю: $P(G, 0) = 0$ (в ноль цветов раскрасить нельзя).
• Коэффициент при $k^{n-1}$ равен $-m$, то есть минус числу рёбер.
• Знаки коэффициентов чередуются: запишем $P(G, k) = \sum_{i} (-1)^{n-i} a_i\, k^{i}$, где все $a_i \ge 0$.

Для связного графа младший ненулевой член - это $k^1$ (степень самого низкого члена связана с числом компонент связности: она равна числу компонент). Эти свойства удобны для самопроверки: посчитав полином, можно сверить старший коэффициент, коэффициент при $k^{n-1}$ и обращение в ноль при $k = 0$.

Связь с хроматическим числом

Хроматическое число $\chi(G)$ - это минимальное число цветов, в которое граф можно правильно раскрасить. Оно напрямую читается из полинома: $\chi(G)$ - это наименьшее целое $k$, при котором $P(G, k) > 0$. Если $P(G, k_0) = 0$, то в $k_0$ цветов граф раскрасить нельзя.

Поэтому хроматический полином - более тонкая характеристика, чем хроматическое число: он не только говорит, раскрашиваем ли граф в $k$ цветов, но и считает количество таких раскрасок. Например, $P(G, \chi(G))$ показывает, сколько вообще существует оптимальных раскрасок. Сама структура расстояний и связности графа при этом играет роль - близкие понятия можно освежить в разборе про радиус и диаметр графа.

Пример вычисления вручную

Найдём полином цикла $C_3$ (треугольника) через удаление–стягивание. Возьмём любое ребро $e$. Граф $C_3 - e$ - это путь из трёх вершин (дерево), для него $P = k(k-1)^2$. Граф $C_3 / e$ - это путь из двух вершин (одно ребро), для него $P = k(k-1)$. Тогда

$P(C_3, k) = k(k-1)^2 - k(k-1) = k(k-1)\big[(k-1) - 1\big] = k(k-1)(k-2).$

Это совпадает с формулой для полного графа $K_3$ (треугольник и есть $K_3$). Проверим свойства: степень $3$ равна числу вершин, старший коэффициент $1$, коэффициент при $k^2$ равен $-3$ (минус три ребра), свободный член ноль. Хроматическое число: $P(C_3, 2) = 2 \cdot 1 \cdot 0 = 0$, а $P(C_3, 3) = 3 \cdot 2 \cdot 1 = 6 > 0$, поэтому $\chi(C_3) = 3$.

Где это применяется

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

В физике хроматический полином связан с моделью Поттса в статистической механике: статсумма антиферромагнитной модели при нулевой температуре по сути совпадает с $P(G, k)$. А обобщением хроматического полинома служит полином Тутте $T(G, x, y)$, из которого хроматический получается специализацией переменных.

Частые ошибки

• Считают цвета неразличимыми. В определении $P(G, k)$ цвета помечены: раскраски, отличающиеся перестановкой цветов, считаются разными.
• Путают знак в теореме: правильная формула - $P(G, k) = P(G - e, k) - P(G / e, k)$, с минусом перед стянутым графом.
• При стягивании ребра забывают склеить возникшие кратные рёбра в одно - иначе появятся лишние ограничения и полином будет неверным.
• Берут степень полинома меньше числа вершин. Степень $P(G, k)$ всегда ровно равна числу вершин $n$.
• Определяют хроматическое число как корень полинома. $\chi(G)$ - это наименьшее $k$, при котором значение становится положительным, а не где полином обращается в ноль.

FAQ

Почему число раскрасок всегда многочлен? Это следствие теоремы об удалении и стягивании: рекурсия сводит любой граф к графам без рёбер, для которых число раскрасок равно $k^n$ - многочлену. Линейные комбинации многочленов снова дают многочлен.

Может ли у двух разных графов совпадать хроматический полином? Да. Полином не определяет граф однозначно: существуют хроматически эквивалентные неизоморфные графы. Например, все деревья на $n$ вершинах имеют один полином $k(k-1)^{n-1}$.

Как полином помогает понять, планарен ли граф? Напрямую - нет, планарность по полиному не читается. Но теорема о четырёх красках утверждает $P(G, 4) > 0$ для любого планарного графа, то есть значение полинома в $k = 4$ для планарных графов всегда положительно.

Коротко

Хроматический полином $P(G, k)$ считает число правильных раскрасок графа в $k$ цветов и всегда оказывается многочленом степени $n$ (числа вершин) со старшим коэффициентом $1$ и коэффициентом $-m$ при $k^{n-1}$. Универсальный способ вычисления - рекуррентная теорема об удалении и стягивании $P(G, k) = P(G - e, k) - P(G / e, k)$, доводимая до графов без рёбер. Из полинома читается хроматическое число $\chi(G)$ как наименьшее $k$ с $P(G, k) > 0$, а сам объект применяется в расписаниях, распределении частот и модели Поттса.