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

#k-раскраски
#k-раскраски
Вход	Граф G с n вершинами.
Выход
Время работы	Принадлежит P для . для . В противном случае для некоторой константы
Сложность	#P-трудна пока
Approximability	No FPRAS for

Хроматический многочлен
Хроматический многочлен
Вход	Граф G с n вершинами.
Выход	Коэффициенты
Время работы	для некоторой константы
Сложность	#P-трудна
Сводится из	#3SAT

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

Все неизоморфные графы с 3 вершинами и их хроматические многочлены, по часовой стрелке сверху.
Независимое 3-множество:

k^{3}

.
Ребро и одна вершина:

k^{2}(k-1)

.
3-путь:

k(k-1)^{2}

.
3-клика:

k(k-1)(k-2)

.

История

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

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

Определение

Все правильные раскраски графов с 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, проходящий через точки

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

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

P(P_{3},t)=t(t-1)^{2},\qquad 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)\left(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352\right)$

Свойства

Для фиксированного графа 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[2].

Значение производной от многочлена в точке 1, $P'(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$ .
Коэффициенты любого хроматического многочлена знакопеременны.
Абсолютные значения коэффициентов любого хроматического многочлена образует логарифмически вогнутую последовательность[3].
$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 изоморфны.

Все циклы хроматически уникальны[4].

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

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

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

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

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

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

Хроматический многочлен категоризирован с помощью теории гомологий, близко связанной с гомологией Хованова[7].

Алгоритмы

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

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

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

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

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

Известны алгоритмы полиномиального времени для вычисления хроматического многочлена для широкого класса графов, в который входят хордальные графы[8] и графы с ограниченной кликовой шириной[9][10]. Второй из этих классов, в свою очередь, включает кографы и графы с ограниченной древесной шириной, такие как внешнепланарные графы.

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

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

Рекурсивный способ вычисления хроматического многочлена базируется на стягивании ребра — для пары вершин $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$ . В первой форме рекурсия прекращается на наборе пустых графов. Эти рекуррентные отношения называются также фундаментальной теоремой редукции[12]. Вопрос Татта о том, какие другие свойства графа удовлетворяют тем же рекуррентным соотношениям, привёл к открытию обобщения хроматического многочлена на две переменные — многочлену Татта.

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

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

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

Метод куба

Существует естественный геометрический подход к раскраске графов, если заметить, что при назначении натуральных чисел каждой вершине раскраска графов является вектором целочисленной решётки. Поскольку присвоение двум вершинам $i$ и $j$ одного цвета эквивалентно равенству координат $i$ и $j$ в векторе раскраски, каждое ребро можно ассоциировать с гиперплоскостью вида $\{x\in R^{d}:x_{i}=x_{j}\}$ . Набор таких гиперплоскостей для данного графа называется его графической конфигурацией гиперплоскостей. Правильная раскраска графа — это раскраска, вектор которой не оказывается на запрещённой плоскости. Ограниченные множеством цветов $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 (включая отрицательные целые числа и даже все комплексные числа), за исключением трёх «простых точек»[16]. Таким образом, сложность вычисления хроматического многочлена полностью понятна.

В многочлене

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

коэффициент $a_{n}$ всегда равен 1, а также известны некоторые другие свойства коэффициентов. Это поднимает вопрос, нельзя ли вычислить некоторые коэффициенты попроще. Однако задача вычисления a_r для фиксированного r и данного графа G является #P-трудной[17].

Не известно никакого аппроксимационного алгоритма вычисления $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[18].

Примечания

Biggs, 1993, с. Некоторые главы.
Stanley, 1973.
Huh, 2012.
Chao, Whitehead, 1978.
Jackson, 1993.
Sokal, 2004.
Helme-Guizon, Rong, 2005.
Naor, Naor, Schaffer, 1987.
Giménez, Hliněný, Noy, 2005.
Makowsky, Rotics, Averbouch, Godlin, 2006.
Shirado, Christakis, 2017, с. 370–374.
Dong, Koh, Teo, 2005.
Pemmaraju, Skiena, 2003.
Wilf, 1986.
Sekine, Imai, Tani, 1995.
Йегер, Вертиган и Уэлш (Jaeger, Vertigan, Welsh 1990), базируясь на сведении Линиала (Linial 1986).
Oxley, Welsh, 2002.
Goldberg, Jerrum, 2008.

Литература

А. Ю. Эвнин. Хроматический многочлен графа в задачах (рус.) // Математическое образование. — 2014. — № 4(72). — С. 9—15.
Biggs N. Algebraic Graph Theory. — Cambridge University Press, 1993. — ISBN 0-521-45897-8.
Hirokazu Shirado, Nicholas A. Christakis. Locally noisy autonomous agents improve global human coordination in network experiments // Nature. — 2017. — Т. 545, вып. 7654. — С. 370–374. — doi:10.1038/nature22332.
Chao C.-Y., Whitehead E. G. On chromatic equivalence of graphs // Theory and Applications of Graphs. — Springer, 1978. — Т. 642. — С. 121–131. — (Lecture Notes in Mathematics). — ISBN 978-3-540-08666-6.
Dong F. M., Koh K. M., Teo K. L. Chromatic polynomials and chromaticity of graphs. — World Scientific Publishing Company, 2005. — ISBN 981-256-317-2.
Giménez O., Hliněný P., Noy M. Computing the Tutte polynomial on graphs of bounded clique-width // Proc. 31st Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2005). — Springer-Verlag, 2005. — Т. 3787. — С. 59–68. — doi:10.1007/11604686_6.
Goldberg L.A., Jerrum M. Inapproximability of the Tutte polynomial // Information and Computation. — 2008. — Т. 206, вып. 7. — С. 908. — doi:10.1016/j.ic.2008.04.003.
Laure Helme-Guizon, Yongwu Rong. A categorification of the chromatic polynomial // Algebraic & Geometric Topology. — 2005. — Т. 5, вып. 4. — С. 1365–1388. — doi:10.2140/agt.2005.5.1365.
Huh J. Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs. — arXiv:1008.4749v3, 2012.
Jackson B. A Zero-Free Interval for Chromatic Polynomials of Graphs // Combinatorics, Probability and Computing. — 1993. — Т. 2. — С. 325–336. — doi:10.1017/S0963548300000705.
Jaeger F., Vertigan D. L., Welsh D. J. A. On the computational complexity of the Jones and Tutte polynomials // Mathematical Proceedings of the Cambridge Philosophical Society. — 1990. — Т. 108. — С. 35–53. — doi:10.1017/S0305004100068936.
Linial N. Hard enumeration problems in geometry and combinatorics // SIAM J. Algebraic Discrete Methods. — 1986. — Т. 7, вып. 2. — С. 331–335. — doi:10.1137/0607036.
Makowsky J. A., Rotics U., Averbouch I., Godlin B. Computing graph polynomials on graphs of bounded clique-width // Proc. 32nd Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2006). — Springer-Verlag, 2006. — Т. 4271. — С. 191–204. — (Lecture Notes in Computer Science). — doi:10.1007/11917496_18.
Naor J., Naor M., Schaffer A. Fast parallel algorithms for chordal graphs // Proc. 19th ACM Symp. Theory of Computing (STOC '87). — 1987. — С. 355–364. — doi:10.1145/28395.28433.
Oxley J. G., Welsh D. J. A. Chromatic, flow and reliability polynomials: The complexity of their coefficients. // Combinatorics, Probability and Computing. — 2002. — Т. 11, вып. 4. — С. 403–426.
Pemmaraju S., Skiena S. section 7.4.2 // Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. — Cambridge University Press, 2003. — ISBN 0-521-80686-0.
Sekine K., Imai H., Tani S. Computing the Tutte polynomial of a graph of moderate size // Algorithms and Computation, 6th International Symposium, Lecture Notes in Computer Science 1004. — Cairns, Australia, December 4–6, 1995: Springer, 1995. — С. 224–233.
Sokal A. D. Chromatic Roots are Dense in the Whole Complex Plane // Combinatorics, Probability and Computing. — 2004. — Т. 13, вып. 2. — С. 221–261. — doi:10.1017/S0963548303006023.
Stanley R. P. Acyclic orientations of graphs // Disc. Math.. — 1973. — Т. 5, вып. 2. — С. 171–178. — doi:10.1016/0012-365X(73)90108-8.
Vitaly I. Voloshin. Coloring Mixed Hypergraphs: Theory, Algorithms and Applications.. — American Mathematical Society, 2002. — ISBN 0-8218-2812-6.
Wilf H. S. Algorithms and Complexity. — Prentice–Hall, 1986. — ISBN 0-13-021973-8.

Ссылки

Weisstein, Eric W. Chromatic polynomial (англ.) на сайте Wolfram MathWorld.
PlanetMath Chromatic polynomial
Code for computing Tutte, Chromatic and Flow Polynomials by Gary Haggard, David J. Pearce and Gordon Royle: (недоступная ссылка)

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[_f97ef9c5a321ea0e-1] Biggs, 1993, с. Некоторые главы.

[_a1b00599676c2db5-2] Stanley, 1973.

[_fc771153b3131b61-3] Huh, 2012.

[_d035e951f418ebf2-4] Chao, Whitehead, 1978.

[_d28468d6ef5f0fe8-5] Jackson, 1993.

[_412197c24feb07db-6] Sokal, 2004.

[_9af451017255f04e-7] Helme-Guizon, Rong, 2005.

[_11e7d36ac322eb56-8] Naor, Naor, Schaffer, 1987.

[_136484162b56b588-9] Giménez, Hliněný, Noy, 2005.

[_dca30009eb2486c3-10] Makowsky, Rotics, Averbouch, Godlin, 2006.

[_846d4bdc229dc385-11] Shirado, Christakis, 2017, с. 370–374.

[_c22ae338821b10e6-12] Dong, Koh, Teo, 2005.

[_01322ea229e12d63-13] Pemmaraju, Skiena, 2003.

[_4e880c5fba0578e3-14] Wilf, 1986.

[_cc401337562a184a-15] Sekine, Imai, Tani, 1995.

[16] Йегер, Вертиган и Уэлш (Jaeger, Vertigan, Welsh 1990), базируясь на сведении Линиала (Linial 1986).

[_a457b6f7b43c23b3-17] Oxley, Welsh, 2002.

[_ebbc223e46f19004-18] Goldberg, Jerrum, 2008.