Математика / Дискретная математика

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

Хроматический многочлен P_G(k) считает правильные раскраски вершин графа в k цветов. Правило удаления и стягивания выражает его через два меньших графа и позволяет считать ответ рекурсивно.

Опубликовано: Обновлено:

Формула

$$P_G(k)=P_{G-e}(k)-P_{G/e}(k)$$
Схема Удаление и стягивание ребра
GG−eG/eP_G=P_{G−e}−P_{G/e}ребро e между правыми вершинами

Путь из трёх вершин и две разные ветви рекурсии.

Обозначения

$P_G(k)$
число правильных раскрасок графа G в k цветов, шт.
$e$
выбранное ребро графа, —
$G-e$
граф после удаления ребра e, —
$G/e$
граф после стягивания концов e в одну вершину, —
$k$
число доступных цветов, шт.

Условия применения

Граф конечный и неориентированный. Раскраска правильная, если концы каждого ребра имеют разные цвета; цвета считаются различимыми. Ребро e не является петлёй: стягивание петли требует отдельного соглашения. Для полиномиального тождества достаточно рассматривать целые k≥0, после чего равенство продолжается как равенство многочленов.

Ограничения

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

Подробное объяснение

В правильной раскраске выбранного ребра e его концы различаются. После удаления e разрешены два класса раскрасок: с разными цветами и с одинаковым цветом концов. Первый класс и есть раскраски исходного графа. Второй класс можно сжать: одинаково окрашенные концы заменить одной вершиной, получив G/e. Поэтому число раскрасок G равно числу раскрасок G-e минус число раскрасок G/e.

Повторяя операцию, граф распадается на простые случаи: пустой граф на n вершинах имеет k^n раскрасок, а граф с петлёй — ноль. Для полного графа K_n результат k(k-1)...(k-n+1), поскольку каждой следующей вершине запрещены цвета всех предыдущих.

Знак вычитания важен: удаление ослабляет ограничение, а стягивание ровно возвращает запрещённый случай совпадения цветов. Для графа без петель степень P_G равна числу вершин, а коэффициент при старшей степени равен единице.

Многочлен даёт не только значение при конкретном k. Его корни и коэффициенты отражают структуру графа; рекурсия связывает комбинаторный подсчёт с операциями над графами и позволяет строить вычислимый алгоритм.

Как пользоваться формулой

  1. Выберите ребро e, концы которого удобно анализировать в исходном графе и в его окрестности.
  2. Постройте G-e, удалив только это ребро и сохранив все вершины и остальные связи графа.
  3. Постройте G/e, отождествив концы e и объединив все их инцидентные рёбра.
  4. Рекурсивно найдите два многочлена и вычтите значение стянутого графа из удалённого.
  5. Остановитесь на пустых графах или графах с петлёй, используя известные базовые случаи.
  6. Проверьте степень, старший коэффициент и значение при выбранном числе цветов отдельным подсчётом.

Историческая справка

Идея считать раскраски графа возникла из задачи о раскраске карт и постепенно стала алгебраическим инвариантом графа. Джордж Биркгоф ввёл хроматический многочлен в 1912 году при исследовании планарных графов и гипотезы о четырёх цветах. Правило удаления и стягивания оформилось как базовая рекурсия теории графов и позднее вошло в общую теорию полиномов Татта. В современной записи многочлен определяют для любого конечного графа, а рекурсивное правило связывает комбинаторный подсчёт с операциями над графами. Важный поворот произошёл, когда стало ясно, что один и тот же инвариант изучает раскраски, циклы и свойства матроидов; поэтому формула используется и за пределами карт. Исторические обозначения менялись, но смысл — точный подсчёт правильных раскрасок различимыми цветами — сохраняется.

Историческая линия формулы

Хроматический многочлен обычно связывают с Джорджем Биркгофом (1912), однако правило удаления и стягивания развивалось в более широкой традиции комбинаторики графов. Современная формулировка опирается на работы Биркгофа, Уитни и последующее развитие полинома Татта.

Пример

Рассмотрим путь из трёх вершин a—b—c и найдём P(k). Удалим ребро ab. Граф G−ab состоит из ребра bc и изолированной вершины a, поэтому P_{G−ab}(k)=k·(k−1)·k=k²(k−1). Стянем ab: вершины a и b сольются, останется одно ребро между новой вершиной и c, значит P_{G/ab}(k)=k(k−1). По правилу P_G(k)=k²(k−1)−k(k−1)=k(k−1)². При k=3 получаем 3·2²=12; прямой выбор цвета для b (3 способа), затем для a и c (по 2 способа) подтверждает результат. Степень равна трём, как и должно быть для трёх вершин, а старший коэффициент равен единице. При k=1 результат нулевой: в непустом графе с ребром нельзя использовать один цвет. Такая проверка одновременно подтверждает формулу и условия её применимости.

Частая ошибка

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

Практика

Задачи с решением

Треугольник

Условие. Найдите число правильных раскрасок треугольника в 3 цвета.

Решение. Первая вершина имеет 3 выбора, вторая — 2, третья должна отличаться от обеих и имеет 1 выбор: 3·2·1.

Ответ. 6 раскрасок.

Путь из четырёх вершин

Условие. Сколько правильных раскрасок пути P4 в 2 цвета?

Решение. Для первой вершины 2 выбора; каждая следующая вынужденно получает противоположный цвет: 2·1·1·1.

Ответ. 2 раскраски.

Дополнительные источники

  • https://math.mit.edu/~apost/courses/18.217_2020/lectures/lecture37_18217.pdf
  • https://matthbeck.github.io/papers/crt.pdf

Связанные формулы

Информатика

Алгоритм A*: кратчайший путь по оценке f=g+h

$f(v)=g(v)+h(v)$

Алгоритм A* выбирает вершину по сумме уже пройденной стоимости g и допустимой оценки оставшегося пути h. При не завышающей эвристике он находит оптимальный маршрут и обычно просматривает меньше вершин, чем поиск Дейкстры.

Математика

Теорема Кирхгофа: число остовов через лапласиан

$\tau(G)=\det L^{(i)},\qquad L=D-A$

Число остовных деревьев неориентированного графа равно определителю любого главного минора его лапласиана. Теорема Кирхгофа заменяет перебор связных подграфов одним матричным вычислением.

Математика

Код Прюфера: число деревьев с заданными степенями

$N(d_1,\ldots,d_n)=\frac{(n-2)!}{\prod_{i=1}^{n}(d_i-1)!},\qquad d_i\ge1,\quad\sum_i d_i=2(n-1)$

В коде Прюфера метка вершины встречается на единицу меньше её степени. Поэтому число помеченных деревьев с фиксированной степенью каждой вершины равно мультиномиальному коэффициенту.

Математика

Формула Кэли: число деревьев с помеченными вершинами

$T_n=n^{n-2},\qquad n\ge2$

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