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

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

Хроматический многочлен является графом полиномиальным изучается в алгебраической теории графов , ветвь математики . Он подсчитывает количество раскрасок графа как функцию количества цветов и был первоначально определен Джорджем Дэвидом Биркгофом для изучения проблемы четырех цветов . Она была обобщена на многочлен Татта по Hassler Уитни и WT Татта , связывая его с моделью Поттс из статистической физики .

История [ править ]

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

Хасслер Уитни обобщил многочлен Биркгофа с плоского случая на общие графы в 1932 году. В 1968 году Рид спросил, какие многочлены являются хроматическими многочленами некоторого графа, вопрос, который остается открытым, и ввел понятие хроматически эквивалентных графов. ^[1] Сегодня хроматические многочлены являются одним из центральных объектов алгебраической теории графов . ^[2]

Определение [ править ]

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

Для графа G , подсчитывает количество его (собственно) вершина к -раскраске . Другие обычно используемые обозначения включают в себя , или . Существует единственный многочлен, вычисленный для любого целого числа k ≥ 0, который совпадает с ; это называется хроматической многочлен от G .${\ Displaystyle P (G, k)}$${\ Displaystyle P_ {G} (к)}$${\ Displaystyle \ чи _ {G} (к)}$${\displaystyle \pi _{G}(k)}$ ${\displaystyle P(G,x)}$${\displaystyle P(G,k)}$

Например, чтобы раскрасить граф путей на 3 вершинах в k цветов, можно выбрать любой из k цветов для первой вершины, любой из оставшихся цветов для второй вершины и, наконец, для третьей вершины, любой из цветов, которые отличаются от выбора второй вершины. Следовательно, - количество k- раскрасок . Таким образом, для переменной x (не обязательно целого числа) мы имеем . (Красители , которые отличаются только перестановкой цветов или с помощью автоморфизмов из G все еще считаются разными.)${\displaystyle P_{3}}$${\displaystyle k-1}$${\displaystyle k-1}$${\displaystyle P(P_{3},k)=k\cdot (k-1)\cdot (k-1)}$${\displaystyle P_{3}}$${\displaystyle P(P_{3},x)=x(x-1)^{2}=x^{3}-2x^{2}+x}$

Удаление – сокращение [ править ]

Тот факт, что количество k- раскрасок является полиномом от k, следует из рекуррентного соотношения, называемого рекуррентностью удаления-сжатия или фундаментальной теоремой сведения . ^[3] Он основан на сжатии ребер : для пары вершин и граф получается объединением двух вершин и удалением всех ребер между ними. Если и смежны в G , пусть обозначает граф, полученный удалением ребра . Тогда числа k- раскрасок этих графов удовлетворяют:${\displaystyle u}$${\displaystyle v}$${\displaystyle G/uv}$${\displaystyle u}$${\displaystyle v}$${\displaystyle G-uv}$${\displaystyle uv}$

${\displaystyle P(G,k)=P(G-uv,k)-P(G/uv,k)}$

Эквивалентно, если и не являются смежными в G и является графом с добавленным ребром , то${\displaystyle u}$${\displaystyle v}$${\displaystyle G+uv}$${\displaystyle uv}$

${\displaystyle P(G,k)=P(G+uv,k)+P(G/uv,k)}$

Это следует из наблюдения, что каждая k- раскраска группы G либо дает разные цвета и , либо одни и те же цвета. В первом случае это дает (правильную) k- раскраску , а во втором - раскраску . Наоборот, всякая k- раскраска группы G может быть однозначно получена из k -раскраски или (если и не являются смежными в G ).${\displaystyle u}$${\displaystyle v}$${\displaystyle G+uv}$${\displaystyle G/uv}$${\displaystyle G+uv}$${\displaystyle G/uv}$${\displaystyle u}$${\displaystyle v}$

Следовательно, хроматический многочлен можно рекурсивно определить как

${\displaystyle P(G,x)=x^{n}}$для безреберного графа на n вершинах и

${\displaystyle P(G,x)=P(G-uv,x)-P(G/uv,x)}$для графа G с произвольно выбранным ребром .${\displaystyle uv}$

Поскольку количество k- раскрасок графа без ребер действительно равно , по индукции по количеству ребер следует, что для всех G многочлен совпадает с количеством k- раскрасок в каждой целой точке x  =  k . В частности, хроматический многочлен - это единственный интерполирующий многочлен степени не выше n через точки${\displaystyle k^{n}}$${\displaystyle P(G,x)}$

${\displaystyle \left\{(0,P(G,0)),(1,P(G,1)),\ldots ,(n,P(G,n))\right\}.}$

Любопытство Тутте о том, какие другие инварианты графа удовлетворяют таким повторениям, привело его к открытию двумерного обобщения хроматического полинома, полинома Тутте .${\displaystyle T_{G}(x,y)}$

Примеры [ править ]

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

Треугольник ${\displaystyle K_{3}}$	${\displaystyle x(x-1)(x-2)}$
Полный график ${\displaystyle K_{n}}$	${\displaystyle x(x-1)(x-2)\cdots (x-(n-1))}$
Безреберный граф ${\displaystyle {\overline {K}}_{n}}$	${\displaystyle x^{n}}$
График пути ${\displaystyle P_{n}}$	${\displaystyle x(x-1)^{n-1}}$
Любое дерево на n вершинах	${\displaystyle x(x-1)^{n-1}}$
Цикл ${\displaystyle C_{n}}$	${\displaystyle (x-1)^{n}+(-1)^{n}(x-1)}$
Граф Петерсена	${\displaystyle x(x-1)(x-2)\left(x^{7}-12x^{6}+67x^{5}-230x^{4}+529x^{3}-814x^{2}+775x-352\right)}$

Свойства [ править ]

Для фиксированного G на n вершинах хроматический многочлен является моническим многочленом степени ровно n с целыми коэффициентами.${\displaystyle P(G,x)}$

Хроматический полином включает, по крайней мере, столько же информации о раскрашиваемости G, сколько и хроматическое число. Действительно, хроматическое число - это наименьшее положительное целое число, которое не является нулем хроматического полинома,

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

Полином оценивали при , то есть , дает раз количество ациклических ориентаций в G . ^[4]${\displaystyle -1}$${\displaystyle P(G,-1)}$${\displaystyle (-1)^{|V(G)|}}$

Производная, равная 1, равна хроматическому инварианту с точностью до знака.${\displaystyle P'(G,1)}$ ${\displaystyle \theta (G)}$

Если G имеет n вершин и c компонент , то${\displaystyle G_{1},\ldots ,G_{c}}$

• Коэффициенты при равны нулю.${\displaystyle x^{0},\ldots ,x^{c-1}}$
• Все коэффициенты ненулевые и чередуются по знакам.${\displaystyle x^{c},\ldots ,x^{n}}$
• Коэффициент при равен 1 (многочлен однозначный ).${\displaystyle x^{n}}$
• Коэффициент равен .${\displaystyle x^{n-1}}$${\displaystyle -|E(G)|}$

Докажем это индукцией по количеству ребер на простом графе G с вершинами и ребрами. Когда , G - пустой граф. Следовательно по определению . Таким образом , коэффициент IS , что означает утверждение верно для пустого графа. Когда , как в G имеет только один край, . Таким образом коэффициент равен . Таким образом, утверждение верно для k = 1. Используя сильную индукцию, предположим, что утверждение верно для . Пусть у G есть ребра. По принципу сокращения-удаления ,${\displaystyle n}$${\displaystyle k}$${\displaystyle k=0}$${\displaystyle P(G,x)=x^{n}}$${\displaystyle x^{n-1}}$${\displaystyle 0}$${\displaystyle k=1}$${\displaystyle P(G,x)=x^{n}-x^{n-1}}$${\displaystyle x^{n-1}}$${\displaystyle -1=-|E(G)|}$${\displaystyle k=0,1,2,\ldots ,(k-1)}$${\displaystyle k}$

${\displaystyle P(G,x)=P(G-e,x)-P(G/e,x)}$,

Пусть , а . Отсюда . Так получается из G удалением только одного ребра е , так и , таким образом , утверждение верно для к .${\displaystyle P(G-e,x)=x^{n}-a_{n-1}x^{n-1}+a_{n-2}x^{n-2}-\cdots }$${\displaystyle P(G.e,x)=x^{n-1}-b_{n-2}x^{n-2}+b_{n-3}x^{n-3}-\cdots }$
${\displaystyle P(G,x)=x^{n}-(a_{n-1}+1)x^{n-1}+\cdots }$
${\displaystyle G-e}$${\displaystyle a_{n-1}=k-1}$${\displaystyle a_{n-1}+1=k}$

• Коэффициент - это умноженное на количество ациклических ориентаций, которые имеют уникальный сток в указанной произвольно выбранной вершине. ^[5]${\displaystyle x^{1}}$${\displaystyle (-1)^{n-1}}$
• Абсолютные значения коэффициентов каждого хроматического полинома образуют логарифмически вогнутую последовательность . ^[6]
• ${\displaystyle \scriptstyle P(G,x)=P(G_{1},x)P(G_{2},x)\cdots P(G_{c},x)}$

Последнее свойство обобщается тем фактом , что , если G является к -clique суммой из и (т.е. график , полученный путем склеивания двух при клике на K вершин), то${\displaystyle G_{1}}$${\displaystyle G_{2}}$

${\displaystyle P(G,x)={\frac {P(G_{1},x)P(G_{2},x)}{x(x-1)\cdots (x-k+1)}}.}$

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

${\displaystyle P(G,x)=x(x-1)^{n-1}.}$

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

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

Два графа называются хроматически эквивалентными, если они имеют один и тот же хроматический многочлен. Изоморфные графы имеют один и тот же хроматический полином, но неизоморфные графы могут быть хроматически эквивалентными. Например, все деревья на n вершинах имеют один и тот же хроматический многочлен. В частности, это хроматические многочлен как кулачковый графа и путь графа на 4 вершин.${\displaystyle (x-1)^{3}x}$

Граф хроматически уникален, если он определяется своим хроматическим многочленом с точностью до изоморфизма. Другими словами, G хроматически уникальна, тогда это означало бы, что G и H изоморфны. Все графы циклов хроматически уникальны. ^[7]${\displaystyle P(G,x)=P(H,x)}$

Хроматические корни [ править ]

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

Ни один граф не может быть 0-цветным, поэтому 0 всегда является хроматическим корнем. Только графы без ребер могут быть одноцветными, поэтому 1 - хроматический корень каждого графа с хотя бы одним ребром. С другой стороны, за исключением этих двух точек, ни один граф не может иметь хроматический корень с действительным числом, меньшим или равным 32/27. ^[8] Результат Тутте связывает золотое сечение с изучением хроматических корней, показывая, что хроматические корни существуют очень близко к : Если это плоская триангуляция сферы, то${\displaystyle \phi }$${\displaystyle \phi ^{2}}$${\displaystyle G_{n}}$

${\displaystyle P(G_{n},\phi ^{2})\leq \phi ^{5-n}.}$

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

Раскраски с использованием всех цветов [ править ]

Для графа G на п вершин, пусть обозначит число раскрасок с использованием ровно к цвету до переименования цветов (так Красители , которые могут быть получены друг из друга перестановки цветов считаются одним; Красители , полученные автоморфизмами из G все еще подсчитываются отдельно ). Другими словами, подсчитывает количество разбиений набора вершин на k (непустых) независимых наборов . Затем подсчитывает количество раскрасок, используя ровно k цветов (с различимыми цветами). Для целого числа x все x${\displaystyle e_{k}}$${\displaystyle e_{k}}$${\displaystyle k!\cdot e_{k}}$-раскраски G можно однозначно получить, выбрав целое число k ≤ x , выбрав k используемых цветов из имеющихся x и раскрась с использованием именно этих k (различимых) цветов. Следовательно:

${\displaystyle P(G,x)=\sum _{k=0}^{x}{\binom {x}{k}}k!\cdot e_{k}=\sum _{k=0}^{x}(x)_{k}\cdot e_{k}}$,

где обозначает падающий факториал . Таким образом, числа являются коэффициентами полинома в основе падающих факториалов.${\displaystyle (x)_{k}=x(x-1)(x-2)\cdots (x-k+1)}$${\displaystyle e_{k}}$${\displaystyle P(G,x)}$${\displaystyle 1,(x)_{1},(x)_{2},(x)_{3},\ldots }$

Пусть будет k -й коэффициент в стандартном базисе , то есть:${\displaystyle a_{k}}$${\displaystyle P(G,x)}$${\displaystyle 1,x,x^{2},x^{3},\ldots }$

${\displaystyle P(G,x)=\sum _{k=0}^{n}a_{k}x^{k}}$

Стирлинга чисел дают замену базиса между стандартной основой и основой падающих факториалов. Из этого следует:

${\displaystyle a_{k}=\sum _{j=0}^{n}(-1)^{j-k}{\begin{bmatrix}j\\k\end{bmatrix}}e_{j}}$   и   .${\displaystyle e_{k}=\sum _{j=0}^{n}{\begin{Bmatrix}j\\k\end{Bmatrix}}a_{j}}$

Категоризация [ править ]

Хроматический многочлен классифицируется теорией гомологий, тесно связанной с гомологиями Хованова . ^[10]

Алгоритмы [ править ]

Хроматический полином
Вход	Граф G с n вершинами.
Выход	Коэффициенты ${\displaystyle P(G,x)}$
Продолжительность	${\displaystyle O(2^{n}n^{r})}$ для некоторой постоянной ${\displaystyle r}$
Сложность	#P -жёсткий
Снижение с	# 3СБ

# k-раскраски
Вход	Граф G с n вершинами.
Выход	${\displaystyle P(G,k)}$
Продолжительность	В P для . для . В противном случае для некоторой постоянной${\displaystyle k=0,1,2}$${\displaystyle O(1.6262^{n})}$${\displaystyle k=3}$${\displaystyle O(2^{n}n^{r})}$${\displaystyle r}$
Сложность	# P-hard, если только${\displaystyle k=0,1,2}$
Аппроксимируемость	Нет FPRAS для ${\displaystyle k>2}$

Вычислительные проблемы, связанные с хроматическим полиномом, включают:

• нахождение хроматического полинома данного графа G ;${\displaystyle P(G,x)}$
• оценки в фиксированной точке х для данного G .${\displaystyle P(G,x)}$

Первая проблема является более общей, потому что, если бы мы знали коэффициенты, мы могли бы вычислить ее в любой момент за полиномиальное время, потому что степень равна n . Сложность второго типа задач сильно зависит от значения x и интенсивно изучается с точки зрения вычислительной сложности . Когда x - натуральное число, эта проблема обычно рассматривается как вычисление количества раскрасок x данного графа. Например, сюда входит задача №3-раскраска подсчета количества 3-раскрасок, каноническая задача в изучении сложности подсчета, завершенная для класса подсчета #P .${\displaystyle P(G,x)}$

Эффективные алгоритмы [ править ]

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

Алгоритмы с полиномиальным временем известны для вычисления хроматического полинома для более широких классов графов, включая хордовые графы ^[11] и графы ограниченной ширины клики . ^[12] Последний класс включает кографы и графы ограниченной древовидной ширины , такие как внешнепланарные графы .

Удаление – сокращение [ править ]

Делеция -сжатие рецидивы дает способ вычисления хроматического многочлена, называемый алгоритмом удаление-сжатие . В первой форме (с минусом) повторение заканчивается набором пустых графов. Во второй форме (с плюсом) он завершается набором полных графиков. Это составляет основу многих алгоритмов раскраски графов. Функция ChromaticPolynomial в пакете Combinatorica системы компьютерной алгебры Mathematica использует второе повторение, если граф плотный, и первое повторение, если граф разреженный. ^[13] Время работы любой формулы в наихудшем случае удовлетворяет тому же рекуррентному соотношению, что и числа Фибоначчи., поэтому в худшем случае алгоритм работает за время с полиномиальным множителем

${\displaystyle \phi ^{n+m}=\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n+m}\in O\left(1.62^{n+m}\right),}$

на графе с n вершинами и m ребрами. ^[14] Анализ может быть улучшена с точностью до полиномиального множителя числа из остовных деревьев входного графа. ^[15] На практике стратегии ветвей и границ и отказ от изоморфизма графов используются, чтобы избежать некоторых рекурсивных вызовов, время выполнения зависит от эвристики, используемой для выбора пары вершин.${\displaystyle t(G)}$

Метод куба [ править ]

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

Вычислительная сложность [ править ]

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

В расширении

${\displaystyle P(G,x)=a_{1}x+a_{2}x^{2}+\cdots +a_{n}x^{n},}$

коэффициент всегда равен 1, и известны некоторые другие свойства коэффициентов. Возникает вопрос, легко ли вычислить некоторые коэффициенты. Однако вычислительная проблема вычисления a _r для фиксированного r ≥ 1 и данного графа G является # P-сложной даже для двудольных плоских графов. ^[17]${\displaystyle a_{n}}$

Нет аппроксимации алгоритмы для вычислений не известны для любого х для трех простых точек , за исключением. В целочисленных точках соответствующая проблема принятия решения о том, может ли данный граф быть k- окрашенным, является NP-трудной . Такие задачи не могут быть приближены к любому мультипликативному коэффициенту с помощью вероятностного алгоритма с ограниченной ошибкой, если NP = RP, потому что любое мультипликативное приближение будет различать значения 0 и 1, эффективно решая версию решения за вероятностное полиномиальное время с ограниченной ошибкой. В частности, при том же предположении это исключает возможность полностью полиномиальной схемы рандомизированной аппроксимации (FPRAS).${\displaystyle P(G,x)}$${\displaystyle k=3,4,\ldots }$. По другим пунктам нужны более сложные аргументы, и этот вопрос находится в центре активных исследований. С 2008 ^[update]года известно, что не существует FPRAS для вычислений для любого x > 2, если только NP  =  RP не выполняется. ^[18]${\displaystyle P(G,x)}$

Заметки [ править ]

Ссылки [ править ]

Внешние ссылки [ править ]

• Вайсштейн, Эрик В. "Хроматический многочлен" . MathWorld .
• PlanetMath Хроматический многочлен
• Код для вычисления Тутте, Хроматических полиномов и Полиномов потока Гэри Хаггарда, Дэвида Дж. Пирса и Гордона Ройла: [1]