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

Все неизоморфные графы с 3 вершинами и их хроматические многочлены, по часовой стрелке сверху.
Независимое 3-множество: $k^3$.
Ребро и одна вершина: $k^2(k-1)$.
3-путь: $k(k-1{)}^2$.
3-клика: $k(k-1)(k-2)$.

Хроматический многочлен — многочлен, изучаемый в алгебраической теории графов, представляющий число раскрасок графа как функцию от числа цветов. Первоначально определён Джорджем Биркгофов для попытки решения на проблемы четырёх красок. Обобщен и систематически изучен Хасслером Уитни, Татт обобщил хроматический многочлен до многочлена Татта, связав его с Шаблон:Не переведено 5 статистической физики.

История

Джордж Биркгоф ввёл хроматический многочлен в 1912 году, определяя его только для планарных графов в попытке доказать теорему о четырёх красках. Если $P(G,k)$ обозначает число правильных раскрасок графа G k цветами, то можно было бы доказать теорему о четырёх красках, показав, что $P(G,4)>0$ для всех планарных графов G. Таким образом он надеялся использовать мощь математического анализа и алгебры для изучения корней многочленов для изучения комбинаторной задачи раскраски.

Хасслер Уитни обобщил многочлен Биркгофа с планарного случая на графы общего вида в 1932. В 1968 году Рид поднял вопрос: какие многочлены являются хроматическими многочленами для некоторых графов (задача остаётся открытой), и ввёл понятие хроматически эквивалентных графов. В настоящее время хроматические многочлены являются центральными объектами алгебраической теории графовШаблон:Sfn.

Определение

Все правильные раскраски графов с 3 вершинами при использовании kцветов ($k=0,1,2,3$). Хроматический многочлен каждого графа интерполирует число правильных раскрасок.

Хроматический многочлен графа G считает число правильных раскрасок вершин. Обычно многочлен обозначается как $P_G(k)$, ${\chi }_G(k)$, ${\pi }_G(k)$ или $P(G,k)$. Последнее обозначение будем использовать в остальной части статьи.

Например, путь $P_3$ с 3 вершинами не может быть раскрашен в 0 цветов или 1 цветом. Используя 2 цвета граф можно раскрасить двумя способами. Используя 3 цвета граф можно раскрасить 12 способами.

Доступно цветов $k$	0	1	2	3
Число раскрасок $P(P_3,k)$	0	0	2	12

Для графа G с n вершинами хроматический многочлен определяется как уникальный интерполирующий многочлен степени, не превосходящей n, проходящий через точки

$\{(0,P(G,0)),(1,P(G,1)),\cdots ,(n,P(G,n))\}.$

Если граф G не содержит вершин с петлями, то хроматический многочлен является приведённым многочленом степени в точности n. Фактически, для приведённого выше примера мы имеем

$P(P_3,t)=t(t-1{)}^2,P(P_3,3)=12.$

Хроматический многочлен включает по меньшей мере столько информации о раскрашиваемости графа G, сколько содержится в хроматическом числе. Более того, хроматическое число является наименьшим положительным целым, при котором хроматический многочлен не обращается в нуль,

$\chi (G)=min\{k:P(G,k)>0\}.$

Примеры

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

Треугольник $K_3$	$t(t-1)(t-2)$
Полный граф $K_n$	$t(t-1)(t-2)\cdots (t-(n-1))$
Путь $P_n$	$t(t-1{)}^{n-1}$
Любое дерево с n вершинами	$t(t-1{)}^{n-1}$
Цикл $C_n$	$(t-1{)}^n+(-1{)}^n(t-1)$
Граф Петерсена	$t(t-1)(t-2)(t^7-12t^6+67t^5-230t^4+529t^3-814t^2+775t-352)$

Свойства

Для фиксированного графа G с n вершинами хроматический многочлен $P(G,t)$ является, фактически, многочленом степени n. По определению, вычисление значения многочлена $P(G,k)$ даёт число k-раскрасок графа G для $k=0,1,\cdots ,n$. То же самое верно для k > n.

Выражение

$(-1{)}^{|V(G)|}P(G,-1)$

даёт число ациклических ориентаций графа GШаблон:Sfn.

Значение производной от многочлена в точке 1, $P^{\prime }(G,1)$ равно с точностью до знака хроматическому инварианту $\theta (G)$.

Если граф G имеет n вершин, m рёбер и c компонент $G_1,\cdots ,G_c$, то

• Коэффициенты при $t^0,\cdots ,t^{c-1}$ равны нулю.
• Коэффициенты при $t^c,\cdots ,t^n$ все ненулевые.
• Коэффициент при $t^n$ в $P(G,t)$ равен 1.
• Коэффициент при $t^{n-1}$ в $P(G,t)$ равен $-m$.
• Коэффициенты любого хроматического многочлена знакопеременны.
• Абсолютные значения коэффициентов любого хроматического многочлена образует Шаблон:Не переведено 5Шаблон:Sfn.
• $P(G,t)=P(G_1,t)P(G_2,t)\cdots P(G_c,t)$

Граф G с n вершинами является деревом тогда и только тогда, когда

$P(G,t)=t(t-1{)}^{n-1}.$

Хроматическая эквивалентность

Три графа с хроматическим многочленом, равным $(x-2)(x-1{)}^{3}x$.

Говорят, что два графа хроматически эквивалентны, если они имеют одинаковые хроматические многочлены. Изоморфные графы имеют одинаковые хроматические многочлены, но неизоморфные графы могут быть хроматически эквивалентными. Например, все деревья с n вершинами имеют одинаковые хроматические многочлены:

$(x-1{)}^{n-1}x,$

В частности,

$(x-1{)}^{3}x$

является хроматическим многочленом как для клешни, так и для пути с 4 вершинами.

Хроматическая единственность

Граф является хроматически уникальным, если он определяется хроматическим многочленом с точностью до изоморфизма. Другими словами, если граф G хроматически уникален, то из $P(G,t)=P(H,t)$ следует, что G и H изоморфны.

Все циклы хроматически уникальныШаблон:Sfn.

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

Корень (или нуль) хроматического многочлена (называется «хроматическим корнем») — это значение x, для которого $P(G,x)=0$. Хроматические корни хорошо изучены. Фактически, исходным побуждением Биркгофа для введения хроматического многочлена было показать, что для планарных графов $P(G,x)>0$ для x ≥ 4. Это доказало бы теорему о четырёх красках.

Никакой граф нельзя раскрасить в 0 цветов, так что 0 всегда является хроматическим корнем. Только графы без рёбер могут быть раскрашены в один цвет, так что 1 является хроматическим корнем любого графа, имеющего по меньшей мере одно ребро. С другой стороны, за исключением этих двух случаев, никакой граф не может иметь в качестве хроматического корня вещественное число, меньшее либо равное 32/27Шаблон:Sfn. Результат Татта связывает золотое сечение $\varphi$ с изучением хроматических корней, показывая, что хроматические корни существуют очень близко к ${\varphi }^2$ — если $G_n$ является планарной триангуляцией сферы, то

$P(G_n,{\varphi }^2)\le {\varphi }^{5-n}.$

В то время как вещественная прямая, таким образом, имеет большие куски, которые не содержат хроматических корней ни для какого графа, любая точка на комплексной плоскости произвольно близка к хроматическому корню в том смысле, что существует бесконечное семейство графов, хроматические корни которых плотны на комплексной плоскостиШаблон:Sfn.

Категоризация

Хроматический многочлен категоризирован с помощью теории гомологий, близко связанной с Шаблон:Не переведено 5Шаблон:Sfn.

Алгоритмы

Вычислительные задачи, связанные с хроматическими многочленами

• нахождение хроматического многочлена $P(G,t)$ для данного графа G;
• вычисление $P(G,k)$ в фиксированной точке k для данного графа G.

Первая задача более общая, поскольку, зная коэффициенты $P(G,t)$, мы можем вычислить значение многочлена в любой точке за полиномиальное время. Вычислительная сложность второй задачи сильно зависит от величины k. Когда k является натуральным числом, задачу можно рассматривать как вычисление количества k-раскрасок данного графа. Например, задача включает подсчёт 3-раскрасок в качестве канонической задачи для изучения сложности подсчёта. Эта задача является полной в классе #P.

Эффективные алгоритмы

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

Известны алгоритмы полиномиального времени для вычисления хроматического многочлена для широкого класса графов, в который входят хордальные графыШаблон:Sfn и графы с ограниченной кликовой ширинойШаблон:SfnШаблон:Sfn. Второй из этих классов, в свою очередь, включает кографы и графы с ограниченной древесной шириной, такие как внешнепланарные графы.

В интернете присутствуют лица, пытающиеся решить задачу коллективно, и им помогают активные автономные помощники, особенно для хроматических многочленов высокой степениШаблон:Sfn.

Удаление — стягивание

Рекурсивный способ вычисления хроматического многочлена базируется на стягивании ребра — для пары вершин $u$ и $v$ граф $G/uv$ получается путём слияния двух вершин и удаления ребра между ними. Хроматический многочлен удовлетворяет рекурсивному соотношению

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

где $u$ и $v$ являются смежными вершинами и $G-uv$ является графом с удалённым ребром $uv$. Эквивалентно,

$P(G,k)=P(G+uv,k)+P(G/uv,k)$

если $u$ и $v$ не смежны и $G+uv$ является графом с добавленным ребром $uv$. В первой форме рекурсия прекращается на наборе пустых графов. Эти рекуррентные отношения называются также фундаментальной теоремой редукцииШаблон:Sfn. Вопрос Татта о том, какие другие свойства графа удовлетворяют тем же рекуррентным соотношениям, привёл к открытию обобщения хроматического многочлена на две переменные — многочлену Татта.

Выражения дают рекурсивную процедуру, называемую алгоритмом удаления — стягивания, которая является базисом многих алгоритмов раскраски графов. Функция ChromaticPolynomial в системе компьютерной алгебры Mathematica использует вторую рекуррентную формулу если граф плотный, и первую, если граф разреженныйШаблон:Sfn. Худшее время работы для обоих формул удовлетворяет рекуррентному соотношению для чисел Фибоначчи, так что в худшем случае алгоритм работает за время (с точностью до некоторого полиномиального коэффициента)

${\varphi }^{n+m}={\left(\frac{1+\sqrt{5}}{2}\right)}^{n+m}\in O\left(\mathrm{1,6}{2}^{n+m}\right)$

на графе с n вершинами и m рёбрамиШаблон:Sfn. Анализ времени работы можно улучшить до полиномиального множителя числа $t(G)$ остовных деревьев входного графаШаблон:Sfn. На практике используется стратегия ветвей и границ вместе с отбрасыванием изоморфных графов, чтобы исключить рекурсивные вызовы, и время зависит от эвристики, используемой при выборе пары вершин (для исключения-стягивания).

Метод куба

Существует естественный геометрический подход к раскраске графов, если заметить, что при назначении натуральных чисел каждой вершине раскраска графов является вектором целочисленной решётки. Поскольку присвоение двум вершинам $i$ и $j$ одного цвета эквивалентно равенству координат $i$ и $j$ в векторе раскраски, каждое ребро можно ассоциировать с гиперплоскостью вида $\{x\in R^d:x_i=x_j\}$. Набор таких гиперплоскостей для данного графа называется его графической Шаблон:Не переведено 5. Правильная раскраска графа — это раскраска, вектор которой не оказывается на запрещённой плоскости. Ограниченные множеством цветов $k$, точки решётки попадают в куб $[0,k{]}^n$. В этом контексте хроматический многочлен подсчитывает точки решётки в $[0,k]$-кубе, которые не попадают на графическую конфигурацию.

Вычислительная сложность

Задача вычисления числа 3-раскрасок данного графа является каноническим примером #P-полной задачи, так что задача вычисления коэффициентов хроматического многочлена #P-трудна. Аналогично, вычисление $P(G,3)$ для данного графа G #P-полна. С другой стороны, для $k=0,1,2$ легко вычислить $P(G,k)$, так что соответствующие задачи имеют полиномиальную по времени трудность. Для целых чисел $k>3$ задача #P-трудна, что устанавливается подобно случаю $k=3$. Фактически, известно, что $P(G,x)$ #P-трудна для всех x (включая отрицательные целые числа и даже все комплексные числа), за исключением трёх «простых точек». Таким образом, сложность вычисления хроматического многочлена полностью понятна.

В многочлене

$P(G,t)=a_{1}t+a_2{t}^2+\dots +a_n{t}^n,$

коэффициент $a_n$ всегда равен 1, а также известны некоторые другие свойства коэффициентов. Это поднимает вопрос, нельзя ли вычислить некоторые коэффициенты попроще. Однако задача вычисления a_r для фиксированного r и данного графа G является #P-труднойШаблон:Sfn.

Не известно никакого аппроксимационного алгоритма вычисления $P(G,x)$ для любого x, за исключением трёх простых точек. В целых точках $k=3,4,\dots$ соответствующая задача разрешимости определения, может ли данный граф быть раскрашен в k цветов, NP-трудна. Такие задачи не могут быть аппроскимированы с любым коэффициентом с помощью полиномиального вероятностного алгоритма с ограниченной ошибкой, разве только NP = RP, поскольку любая мультипликативная аппроксимация различала бы значения 0 и 1, что было бы эффективным решением задачи с помощью полиномиального вероятностного алгоритма с ограниченной ошибкой в форме задачи разрешимости. В частности, при некоторых предположениях, это исключает возможность полностью полиномиальной рандомизированной аппроксимационной схемы (FPRAS). Для других точек нужны более сложные рассуждения и вопрос находится в фокусе активных поисков. На 2008 известно, что не существует FPRAS-схемы для вычиcления $P(G,x)$ для любого x > 2, разве только NP = RPШаблон:Sfn.

Литература

• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга

Ссылки

• Шаблон:MathWorld
• PlanetMath Chromatic polynomial
• Code for computing Tutte, Chromatic and Flow Polynomials by Gary Haggard, David J. Pearce and Gordon Royle: [1]Шаблон:Недоступная ссылка