Хроматичний многочлен графу

Хромати́чний многочле́н — многочлен, досліджуваний в алгебричній теорії графів, що подає число розфарбувань графа як функцію від кількості кольорів. Спочатку його визначив Джордж Біркгоф для спроби розв'язання проблеми чотирьох фарб. Узагальнив та систематично вивчив ^[en], Татт узагальнив хроматичний многочлен до многочлена Татта, пов'язавши його з ^[en] статистичної фізики.

Всі неізоморфні графи з 3 вершинами і їхні хроматичні многочлени, за годинниковою стрілкою згори.
Незалежна 3-множина: ${\displaystyle k^{3}}$.
Ребро й одна вершина: ${\displaystyle k^{2}(k-1)}$.
3-шлях: ${\displaystyle k(k-1)^{2}}$.
3-кліка: ${\displaystyle k(k-1)(k-2)}$.

Історія

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

^[ru] узагальнив многочлен Біркгофа з планарного випадку на графи загального вигляду в 1932 році. 1968 року Рід порушив питання: які многочлени є хроматичними многочленами для деяких графів (задача залишається відкритою), і ввів поняття хроматично еквівалентних графів. Нині хроматичні многочлени є центральними об'єктами алгебричної теорії графів.

Визначення

Всі правильні розфарбування графів з 3 вершинами при використанні k кольорів (${\displaystyle k=0,1,2,3}$). Хроматичний многочлен кожного графа інтерполює число правильних розфарбувань.

Хроматичний многочлен графа 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}$.
• Коефіцієнти будь-якого хроматичного многочлена знакозмінні.
• Абсолютні значення коефіцієнтів будь-якого хроматичного многочлена утворюють ^[en].
• ${\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}.}$

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

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

Кажуть, що два графи хроматично еквівалентні, якщо вони мають однакові хроматичні многочлени. Ізоморфні графи мають однакові хроматичні многочлени, але неізоморфні графи можуть бути хроматично еквівалентними. Наприклад, всі дерева з 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}.}$

Тоді як дійсна пряма, таким чином, має великі шматки, які не містять хроматичних коренів ні для якого графа, будь-яка точка на комплексній площині довільно близька до хроматичного кореня в тому сенсі, що існує нескінченне сімейство графів, хроматичні корені яких щільні на комплексній площині.

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

Хроматичний многочлен категоризовано за допомогою теорії гомологій, близько пов'язаної з ^[en].

Алгоритми

Хроматичний многочлен
Вхід	Граф G з n вершинами.
Вихід	Коефіцієнти ${\displaystyle P(G,t)}$
Час роботи	${\displaystyle O(2^{n}n^{r})}$ для деякої константи ${\displaystyle r}$
Складність	-складна
Зводиться з	#3SAT

#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}$
Складність	-складна, крім випадків ${\displaystyle k=0,1,2}$
Апроксимованість	Немає FPRAS для ${\displaystyle k>2}$

Обчислювальні задачі, пов'язані з хроматичними многочленами:

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

Перша задача більш загальна, оскільки, знаючи коефіцієнти ${\displaystyle P(G,t)}$, можна обчислити значення многочлена в будь-якій точці за поліноміальний час. Обчислювальна складність другої задачі сильно залежить від величини k. Коли k — натуральне число, задачу можна розглядати як обчислення кількості k-розфарбувань даного графа. Наприклад, задача включає підрахунок 3-розфарбувань як канонічну задачу для вивчення складності підрахунку. Ця задача є повною в класі .

Ефективні алгоритми

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

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

В інтернеті робляться спроби розв'язати задачу колективно, і їм допомагають активні автономні помічники, особливо для хроматичних многочленів високого ступеня.

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

Рекурсивний спосіб обчислення хроматичного многочлена базується на стягуванні ребра — для пари вершин ${\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}\}}$. Набір таких гіперплощин для даного графа називається його графічною ^[en]. Правильне розфарбування графа — це розфарбування, вектор якої не виявляється на забороненій площині. Обмежені множиною кольорів ${\displaystyle k}$, точки решітки потрапляють у куб ${\displaystyle [0,k]^{n}}$. У цьому контексті хроматичний многочлен підраховує точки ґратки в ${\displaystyle [0,k]}$-кубі, які не потрапляють на графічну конфігурацію.

Обчислювальна складність

Задача обчислення числа 3-розфарбувань цього графа є канонічним прикладом -повної задачі, так що задача обчислення коефіцієнтів хроматичного многочлена #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 рік відомо, що не існує для обчислення ${\displaystyle P(G,x)}$ для будь-якого x > 2, хіба тільки NP = .

Примітки

1. Biggs, 1993, с. деякі розділи.
2. Stanley, 1973.
3. Huh, 2012.
4. Chao, Whitehead, 1978.
5. Jackson, 1993.
6. Sokal, 2004.
7. Helme-Guizon, Rong, 2005.
8. Naor, Naor, Schaffer, 1987.
9. Giménez, Hliněný, Noy, 2005.
10. Makowsky, Rotics, Averbouch, Godlin, 2006.
11. Shirado, Christakis, 2017, с. 370–374.
12. Dong, Koh, Teo, 2005.
13. Pemmaraju, Skiena, 2003.
14. Wilf, 1986.
15. Sekine, Imai, Tani, 1995.
16. Єгер, Вертіган і Велш (Jaeger, Vertigan, Welsh, 1990), ґрунтуючись на зведенні Лініала (Linial, 1986).
17. Oxley, Welsh, 2002.
18. Goldberg, Jerrum, 2008.

Література

• А. Ю. Эвнин. Хроматический многочлен графа в задачах // . — 2014. — № 4(72) (3 ноября). — С. 9—15.
• Biggs N. Algebraic Graph Theory. — Cambridge University Press, 1993. — .
• Hirokazu Shirado, Nicholas A. Christakis. Locally noisy autonomous agents improve global human coordination in network experiments // Nature. — 2017. — Т. 545, вип. 7654 (3 листопада). — С. 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) — .
• Dong F. M., Koh K. M., Teo K. L. Chromatic polynomials and chromaticity of graphs. — World Scientific Publishing Company, 2005. — .
• 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 (3 листопада). — С. 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 (3 листопада). — С. 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. — 3 листопада.
• Jackson B. A Zero-Free Interval for Chromatic Polynomials of Graphs // Combinatorics, Probability and Computing. — 1993. — Т. 2 (3 листопада). — С. 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 (3 листопада). — С. 35–53. — DOI:10.1017/S0305004100068936.
• Linial N. Hard enumeration problems in geometry and combinatorics // SIAM J. Algebraic Discrete Methods. — 1986. — Т. 7, вип. 2 (3 листопада). — С. 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. // . — 2002. — Т. 11, вип. 4 (3 листопада). — С. 403–426.
• Pemmaraju S., Skiena S. section 7.4.2 // Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. — Cambridge University Press, 2003. — .
• 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 (3 листопада). — С. 221–261. — DOI:10.1017/S0963548303006023.
• Stanley R. P. Acyclic orientations of graphs // . — 1973. — Т. 5, вип. 2 (3 листопада). — С. 171–178. — DOI:10.1016/0012-365X(73)90108-8.
• Vitaly I. Voloshin. Coloring Mixed Hypergraphs: Theory, Algorithms and Applications. — American Mathematical Society, 2002. — .
• Wilf H. S. Algorithms and Complexity. — Prentice–Hall, 1986. — .

Посилання

• Weisstein, Eric W. Chromatic polynomial(англ.) на сайті Wolfram MathWorld.
• PlanetMath Chromatic поліноміальні [Архівовано 20 серпня 2008 у Wayback Machine.]
• Code for computing Tutte, Chromatic and Flow Поліномів by Gary Haggard, David J. Pearce and Gordon Royle: [1]