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

История

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

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

Определение

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

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

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

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

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

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

${\displaystyle P(P_{3},t)=t(t-1)^{2},\qquad P(P_{3},3)=12.}$

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

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

Примеры

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

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

Свойства

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

Выражение

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

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

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

Если граф G имеет n вершин, m рёбер и c компонент ${\displaystyle G_{1},\cdots ,G_{c}}$ , то

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

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

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

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

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

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

В частности,

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритмы

#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 -трудна пока ${\displaystyle k=0,1,2}$
Approximability	No FPRAS for ${\displaystyle k>2}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Метод куба

Существует естественный геометрический подход к раскраске графов, если заметить, что при назначении натуральных чисел каждой вершине раскраска графов является вектором целочисленной решётки. Поскольку присвоение двум вершинам ${\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-трудна. Аналогично, вычисление ${\displaystyle P(G,3)}$ для данного графа G #P-полна. С другой стороны, для ${\displaystyle k=0,1,2}$ легко вычислить ${\displaystyle P(G,k)}$ , так что соответствующие задачи имеют полиномиальную по времени трудность. Для целых чисел ${\displaystyle k>3}$ задача #P-трудна, что устанавливается подобно случаю ${\displaystyle k=3}$ . Фактически, известно, что ${\displaystyle P(G,x)}$ #P-трудна для всех x (включая отрицательные целые числа и даже все комплексные числа), за исключением трёх «простых точек» . Таким образом, сложность вычисления хроматического многочлена полностью понятна.

В многочлене

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

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

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

Примечания

Литература

• А. Ю. Эвнин. (рус.) // Математическое образование . — 2014. — № 4(72) . — С. 9—15 .
• Biggs N. Algebraic Graph Theory. — Cambridge University Press, 1993. — ISBN 0-521-45897-8 .
• Hirokazu Shirado, Nicholas A. Christakis. // Nature. — 2017. — Т. 545 , вып. 7654 . — С. 370–374 . — doi : .
• 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 : .
• Goldberg L.A., Jerrum M. Inapproximability of the Tutte polynomial // Information and Computation. — 2008. — Т. 206 , вып. 7 . — С. 908 . — doi : .
• Laure Helme-Guizon, Yongwu Rong. A categorification of the chromatic polynomial // Algebraic & Geometric Topology. — 2005. — Т. 5 , вып. 4 . — С. 1365–1388 . — doi : .
• 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 : .
• 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 : .
• Linial N. Hard enumeration problems in geometry and combinatorics // SIAM J. Algebraic Discrete Methods. — 1986. — Т. 7 , вып. 2 . — С. 331–335 . — doi : .
• 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 : .
• 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 : .
• Oxley J. G., Welsh D. J. A. Chromatic, flow and reliability polynomials: The complexity of their coefficients. // . — 2002. — Т. 11 , вып. 4 . — С. 403–426 .
• Pemmaraju S., Skiena S. section 7.4.2 // . — 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 // . — 2004. — Т. 13 , вып. 2 . — С. 221–261 . — doi : .
• Stanley R. P. Acyclic orientations of graphs // Disc. Math. . — 1973. — Т. 5 , вып. 2 . — С. 171–178 . — doi : .
• 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. (англ.) на сайте Wolfram MathWorld .
• PlanetMath
• Code for computing Tutte, Chromatic and Flow Polynomials by Gary Haggard, David J. Pearce and Gordon Royle: (недоступная ссылка)