Хромати́чний многочле́н — многочлен, досліджуваний в алгебричній теорії графів, що подає число розфарбувань графа як функцію від кількості кольорів. Спочатку його визначив Джордж Біркгоф для спроби розв'язання проблеми чотирьох фарб. Узагальнив та систематично вивчив [en], Татт узагальнив хроматичний многочлен до многочлена Татта, пов'язавши його з [en] статистичної фізики.
Історія
Джордж Біркгоф увів хроматичний многочлен 1912 року, визначаючи його тільки для планарних графів у спробі довести теорему про чотири фарби. Якщо позначає число правильних розфарбувань графа G k кольорами, то можна було б довести теорему про чотири фарби, показавши, що для всіх планарних графів G. Таким чином він сподівався використати засоби математичного аналізу та алгебри для вивчення коренів многочленів до вивчення комбінаторної задачі розфарбовування.
[ru] узагальнив многочлен Біркгофа з планарного випадку на графи загального вигляду в 1932 році. 1968 року Рід порушив питання: які многочлени є хроматичними многочленами для деяких графів (задача залишається відкритою), і ввів поняття хроматично еквівалентних графів. Нині хроматичні многочлени є центральними об'єктами алгебричної теорії графів.
Визначення
Хроматичний многочлен графа G рахує число правильних розфарбувань вершин. Зазвичай многочлен позначається як , , або . Далі використовуватимемо останнє позначення.
Наприклад, шлях з 3 вершинами не можна розфарбувати в 0 колорів або 1 кольором. Використовуючи 2 кольори граф можна розфарбувати двома способами. Використовуючи 3 кольори граф можна розфарбувати 12 способами.
Доступно кольорів | 0 | 1 | 2 | 3 |
Число розфарбувань | 0 | 0 | 2 | 12 |
Для графа G з n вершинами хроматичний многочлен визначається як унікальний інтерполяційний многочлен степеня, що не перевищує n, який проходить через точки
Якщо граф G не містить вершин з петлями, то хроматичний многочлен є зведеними многочленом степеня рівно n. Фактично, для наведеного вище прикладу маємо
Хроматичний многочлен включає принаймні стільки інформації про розфарбовуваність графа G, скільки міститься в хроматичному числі. Більше того, хроматичне число є найменшим додатним цілим, за якого хроматичний многочлен не перетворюється на нуль,
Приклади
Трикутник | |
Повний граф | |
Шлях | |
Будь-яке дерево з n вершинами | |
Цикл | |
Граф Петерсена |
Властивості
Для фіксованого графа G з n вершинами хроматичний многочлен є, фактично, многочленом степеня n. За визначенням, обчислення значення многочлена дає число k-розфарбувань графа G для . Це правильно і для k> n.
Вираз
дає число ациклічних орієнтацій графа G.
Значення похідної від многочлена в точці 1, дорівнює з точністю до знака хроматичному інваріанту .
Якщо граф G має n вершин, m ребер і c компонент , то
- Коефіцієнти при дорівнюють нулю.
- Коефіцієнти при всі ненульові.
- Коефіцієнт при в дорівнює 1.
- Коефіцієнт при в дорівнює .
- Коефіцієнти будь-якого хроматичного многочлена знакозмінні.
- Абсолютні значення коефіцієнтів будь-якого хроматичного многочлена утворюють [en].
Граф G з n вершинами є деревом тоді й лише тоді, коли
Хроматична еквівалентність
Кажуть, що два графи хроматично еквівалентні, якщо вони мають однакові хроматичні многочлени. Ізоморфні графи мають однакові хроматичні многочлени, але неізоморфні графи можуть бути хроматично еквівалентними. Наприклад, всі дерева з n вершинами мають однакові хроматичні многочлени:
Зокрема,
є хроматичним многочленом як для клешні, так і для шляху з 4 вершинами.
Хроматична єдиність
Граф хроматично унікальний, якщо він визначається хроматичним многочленом з точністю до ізоморфізму. Іншими словами, якщо граф G хроматично унікальний, то з випливає, що G і H ізоморфні.
Всі цикли хроматично унікальні.
Хроматичні корені
Корінь (або нуль) хроматичного многочлена (називається «хроматичним коренем») — це значення x, для якого . Хроматичні корені добре вивчено. Фактично, Біркгоф увів хроматичний многочлен, щоб показати, що для планарних графів для x ≥ 4. Це довело б теорему про чотири фарби.
Ніякий граф не можна розфарбувати в 0 кольорів, так що 0 завжди є хроматичним коренем. Тільки графи без ребер можна розфарбувати в один колір, так що 1 є хроматичним коренем будь-якого графа, що має щонайменше одне ребро. З іншого боку, за винятком цих двох випадків, ніякий граф не може мати хроматичним коренем дійсне число, менше або рівне 32/27. Результат Татта пов'язує золотий перетин з вивченням хроматичних коренів, показуючи, що хроматичні корені існують дуже близько до — якщо є планарною тріангуляцією сфери, то
Тоді як дійсна пряма, таким чином, має великі шматки, які не містять хроматичних коренів ні для якого графа, будь-яка точка на комплексній площині довільно близька до хроматичного кореня в тому сенсі, що існує нескінченне сімейство графів, хроматичні корені яких щільні на комплексній площині.
Категоризація
Хроматичний многочлен категоризовано за допомогою теорії гомологій, близько пов'язаної з [en].
Алгоритми
Хроматичний многочлен | |
---|---|
Вхід | Граф G з n вершинами. |
Вихід | Коефіцієнти |
Час роботи | для деякої константи |
Складність | -складна |
Зводиться з | #3SAT |
#k-розфарбування | |
---|---|
Вхід | Граф G з n вершинами. |
Вихід | |
Час роботи | Належить P для . для . В іншому випадку для деякої константи |
Складність | -складна, крім випадків |
Апроксимованість | Немає FPRAS для |
Обчислювальні задачі, пов'язані з хроматичними многочленами:
- знаходження хроматичного многочлена для даного графа G;
- обчислення у фіксованій точці k для даного графа G.
Перша задача більш загальна, оскільки, знаючи коефіцієнти , можна обчислити значення многочлена в будь-якій точці за поліноміальний час. Обчислювальна складність другої задачі сильно залежить від величини k. Коли k — натуральне число, задачу можна розглядати як обчислення кількості k-розфарбувань даного графа. Наприклад, задача включає підрахунок 3-розфарбувань як канонічну задачу для вивчення складності підрахунку. Ця задача є повною в класі .
Ефективні алгоритми
Для деяких базових класів графів відомі явні формули хроматичних многочленів. Наприклад, для дерев і клік, що показано в таблиці вище.
Відомі алгоритми поліноміального часу для обчислення хроматичного многочлена для широкого класу графів, до якого входять хордальні графи і графи з обмеженою кліковою шириною. Другий з цих класів, своєю чергою, включає кографи і графи з обмеженою деревною шириною, такі як зовніпланарні графи.
В інтернеті робляться спроби розв'язати задачу колективно, і їм допомагають активні автономні помічники, особливо для хроматичних многочленів високого ступеня.
Видалення — стягування
Рекурсивний спосіб обчислення хроматичного многочлена базується на стягуванні ребра — для пари вершин і граф виходить шляхом злиття двох вершин і видалення ребра між ними. Хроматичний многочлен задовольняє рекурсивному співвідношенню
- ,
де і є суміжними вершинами і є графом з видаленим ребром . Еквівалентно,
якщо і не суміжні і є графом з доданим ребром . У першій формі рекурсія припиняється на наборі порожніх графів. Ці рекурентні відношення називаються також фундаментальною теоремою редукції. Питання Татта про те, які інші властивості графа відповідають тим самим рекурентним співвідношенням, привело до відкриття узагальнення хроматичного многочлена на дві змінні — многочлена Татта.
Вирази дають рекурсивну процедуру, звану алгоритмом видалення — стягування, яка є основою багатьох алгоритмів розфарбування графів. Функція ChromaticPolynomial у системі комп'ютерної алгебри Mathematica використовує другу рекурентну формулу якщо граф щільний, і першу, якщо граф розріджений. Найгірший час роботи для обох формул задовольняє рекурентному співвідношенням для чисел Фібоначчі, так що в гіршому випадку алгоритм працює за час (з точністю до деякого поліноміального коефіцієнта)
на графі з n вершинами і m ребрами. Аналіз часу роботи можна поліпшити до поліноміального множника числа кістякових дерев вхідного графа. На практиці використовується стратегія гілок і меж разом з відкиданням ізоморфних графів, щоб виключити рекурсивні виклики, і час залежить від евристики, використовуваної при виборі пари вершин (для виключення-стягування).
Метод куба
Існує природний геометричний підхід до розфарбовування графів, якщо зауважити, що при призначенні натуральних чисел кожній вершині розфарбування графів є вектором цілочисельної ґратки. Оскільки присвоєння двом вершинам і одного кольору еквівалентне рівності координат і у векторі розфарбування, кожне ребро можна асоціювати з гіперплощиною виду . Набір таких гіперплощин для даного графа називається його графічною [en]. Правильне розфарбування графа — це розфарбування, вектор якої не виявляється на забороненій площині. Обмежені множиною кольорів , точки решітки потрапляють у куб . У цьому контексті хроматичний многочлен підраховує точки ґратки в -кубі, які не потрапляють на графічну конфігурацію.
Обчислювальна складність
Задача обчислення числа 3-розфарбувань цього графа є канонічним прикладом -повної задачі, так що задача обчислення коефіцієнтів хроматичного многочлена #P-складна. Аналогічно, задача обчислення для даного графа G #P-повна. З іншого боку, для легко обчислити , так що відповідні завдання мають поліноміальну за часом складність. Для цілих чисел задача #P-складна, що встановлюється подібно до випадку . Фактично, відомо, що #P-складна для всіх x (включно з від'ємними цілими числами і навіть всіма комплексними числами), за винятком трьох «простих точок». Таким чином, складність обчислення хроматичного многочлена повністю зрозуміла.
У многочлені
коефіцієнт завжди дорівнює 1, а також відомі деякі інші властивості коефіцієнтів. Це порушує питання, чи не можна обчислити деякі коефіцієнти простіше. Однак задача обчислення ar для фіксованого r і даного графа G є #P-складною.
Не відомо жодного апроксимаційного алгоритму обчислення для будь-якого x, за винятком трьох простих точок. У цілих точках відповідна задача розв'язності визначення, чи можна даний граф розфарбувати в k кольорів, NP-складна. Такі задачі не можна апроксимувати з будь-яким коефіцієнтом за допомогою поліноміального ймовірнісного алгоритму з обмеженою помилкою, хіба тільки NP = RP, оскільки будь-яка мультиплікативна апроксимація розрізняла б значення 0 і 1, що було б ефективним розв'язком задачі за допомогою поліноміального ймовірнісного алгоритму з обмеженою помилкою у формі задачі розв'язності. Зокрема, при деяких припущеннях, це виключає можливість повністю поліноміальної рандомізованої апроксимаційної схеми (FPRAS). Для інших точок потрібні складніші міркування і питання перебуває у фокусі активних пошуків. На 2008 рік відомо, що не існує для обчислення для будь-якого x > 2, хіба тільки NP = .
Примітки
- 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) (26 июня). — С. 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 (26 червня). — С. 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) — .
- 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:
- Goldberg L.A., Jerrum M. Inapproximability of the Tutte polynomial // Information and Computation. — 2008. — Т. 206, вип. 7 (26 червня). — С. 908. — DOI: .
- Laure Helme-Guizon, Yongwu Rong. A categorification of the chromatic polynomial // Algebraic & Geometric Topology. — 2005. — Т. 5, вип. 4 (26 червня). — С. 1365–1388. — DOI: .
- Huh J. Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs. — arXiv:1008.4749v3, 2012. — 26 червня.
- Jackson B. A Zero-Free Interval for Chromatic Polynomials of Graphs // Combinatorics, Probability and Computing. — 1993. — Т. 2 (26 червня). — С. 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 (26 червня). — С. 35–53. — DOI: .
- Linial N. Hard enumeration problems in geometry and combinatorics // SIAM J. Algebraic Discrete Methods. — 1986. — Т. 7, вип. 2 (26 червня). — С. 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 (26 червня). — С. 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 (26 червня). — С. 221–261. — DOI: .
- Stanley R. P. Acyclic orientations of graphs // . — 1973. — Т. 5, вип. 2 (26 червня). — С. 171–178. — DOI: .
- 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]
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Hromati chnij mnogochle n mnogochlen doslidzhuvanij v algebrichnij teoriyi grafiv sho podaye chislo rozfarbuvan grafa yak funkciyu vid kilkosti koloriv Spochatku jogo viznachiv Dzhordzh Birkgof dlya sprobi rozv yazannya problemi chotiroh farb Uzagalniv ta sistematichno vivchiv en Tatt uzagalniv hromatichnij mnogochlen do mnogochlena Tatta pov yazavshi jogo z en statistichnoyi fiziki Vsi neizomorfni grafi z 3 vershinami i yihni hromatichni mnogochleni za godinnikovoyu strilkoyu zgori Nezalezhna 3 mnozhina k 3 displaystyle k 3 Rebro j odna vershina k 2 k 1 displaystyle k 2 k 1 3 shlyah k k 1 2 displaystyle k k 1 2 3 klika k k 1 k 2 displaystyle k k 1 k 2 IstoriyaDzhordzh Birkgof uviv hromatichnij mnogochlen 1912 roku viznachayuchi jogo tilki dlya planarnih grafiv u sprobi dovesti teoremu pro chotiri farbi Yaksho P G k displaystyle P G k poznachaye chislo pravilnih rozfarbuvan grafa G k kolorami to mozhna bulo b dovesti teoremu pro chotiri farbi pokazavshi sho P G 4 gt 0 displaystyle P G 4 gt 0 dlya vsih planarnih grafiv G Takim chinom vin spodivavsya vikoristati zasobi matematichnogo analizu ta algebri dlya vivchennya koreniv mnogochleniv do vivchennya kombinatornoyi zadachi rozfarbovuvannya ru uzagalniv mnogochlen Birkgofa z planarnogo vipadku na grafi zagalnogo viglyadu v 1932 roci 1968 roku Rid porushiv pitannya yaki mnogochleni ye hromatichnimi mnogochlenami dlya deyakih grafiv zadacha zalishayetsya vidkritoyu i vviv ponyattya hromatichno ekvivalentnih grafiv Nini hromatichni mnogochleni ye centralnimi ob yektami algebrichnoyi teoriyi grafiv ViznachennyaVsi pravilni rozfarbuvannya grafiv z 3 vershinami pri vikoristanni k koloriv k 0 1 2 3 displaystyle k 0 1 2 3 Hromatichnij mnogochlen kozhnogo grafa interpolyuye chislo pravilnih rozfarbuvan Hromatichnij mnogochlen grafa G rahuye chislo pravilnih rozfarbuvan vershin Zazvichaj mnogochlen poznachayetsya yak P G k displaystyle P G k x G k displaystyle chi G k p G k displaystyle pi G k abo P G k displaystyle P G k Dali vikoristovuvatimemo ostannye poznachennya Napriklad shlyah P 3 displaystyle P 3 z 3 vershinami ne mozhna rozfarbuvati v 0 koloriv abo 1 kolorom Vikoristovuyuchi 2 kolori graf mozhna rozfarbuvati dvoma sposobami Vikoristovuyuchi 3 kolori graf mozhna rozfarbuvati 12 sposobami Dostupno koloriv k displaystyle k 0 1 2 3 Chislo rozfarbuvan P P 3 k displaystyle P P 3 k 0 0 2 12 Dlya grafa G z n vershinami hromatichnij mnogochlen viznachayetsya yak unikalnij interpolyacijnij mnogochlen stepenya sho ne perevishuye n yakij prohodit cherez tochki 0 P G 0 1 P G 1 n P G n displaystyle left 0 P G 0 1 P G 1 cdots n P G n right Yaksho graf G ne mistit vershin z petlyami to hromatichnij mnogochlen ye zvedenimi mnogochlenom stepenya rivno n Faktichno dlya navedenogo vishe prikladu mayemo P P 3 t t t 1 2 P P 3 3 12 displaystyle P P 3 t t t 1 2 qquad P P 3 3 12 Hromatichnij mnogochlen vklyuchaye prinajmni stilki informaciyi pro rozfarbovuvanist grafa G skilki mistitsya v hromatichnomu chisli Bilshe togo hromatichne chislo ye najmenshim dodatnim cilim za yakogo hromatichnij mnogochlen ne peretvoryuyetsya na nul x G min k P G k gt 0 displaystyle chi G min k P G k gt 0 PrikladiHromatichni mnogochleni dlya deyakih grafiv Trikutnik K 3 displaystyle K 3 t t 1 t 2 displaystyle t t 1 t 2 Povnij graf K n displaystyle K n t t 1 t 2 t n 1 displaystyle t t 1 t 2 cdots t n 1 Shlyah P n displaystyle P n t t 1 n 1 displaystyle t t 1 n 1 Bud yake derevo z n vershinami t t 1 n 1 displaystyle t t 1 n 1 Cikl C n displaystyle C n t 1 n 1 n t 1 displaystyle t 1 n 1 n t 1 Graf Petersena t t 1 t 2 t 7 12 t 6 67 t 5 230 t 4 529 t 3 814 t 2 775 t 352 displaystyle t t 1 t 2 left t 7 12t 6 67t 5 230t 4 529t 3 814t 2 775t 352 right VlastivostiDlya fiksovanogo grafa G z n vershinami hromatichnij mnogochlen P G t displaystyle P G t ye faktichno mnogochlenom stepenya n Za viznachennyam obchislennya znachennya mnogochlena P G k displaystyle P G k daye chislo k rozfarbuvan grafa G dlya k 0 1 n displaystyle k 0 1 cdots n Ce pravilno i dlya k gt n Viraz 1 V G P G 1 displaystyle 1 V G P G 1 daye chislo aciklichnih oriyentacij grafa G Znachennya pohidnoyi vid mnogochlena v tochci 1 P G 1 displaystyle P G 1 dorivnyuye z tochnistyu do znaka hromatichnomu invariantu 8 G displaystyle theta G Yaksho graf G maye n vershin m reber i c komponent G 1 G c displaystyle G 1 cdots G c to Koeficiyenti pri t 0 t c 1 displaystyle t 0 cdots t c 1 dorivnyuyut nulyu Koeficiyenti pri t c t n displaystyle t c cdots t n vsi nenulovi Koeficiyent pri t n displaystyle t n v P G t displaystyle P G t dorivnyuye 1 Koeficiyent pri t n 1 displaystyle t n 1 v P G t displaystyle P G t dorivnyuye m displaystyle m Koeficiyenti bud yakogo hromatichnogo mnogochlena znakozminni Absolyutni znachennya koeficiyentiv bud yakogo hromatichnogo mnogochlena utvoryuyut en P G t P G 1 t P G 2 t P G c t displaystyle P G t P G 1 t P G 2 t cdots P G c t Graf G z n vershinami ye derevom todi j lishe todi koli P G t t t 1 n 1 displaystyle P G t t t 1 n 1 Hromatichna ekvivalentnist Tri grafi z hromatichnim mnogochlenom rivnim x 2 x 1 3 x displaystyle x 2 x 1 3 x Kazhut sho dva grafi hromatichno ekvivalentni yaksho voni mayut odnakovi hromatichni mnogochleni Izomorfni grafi mayut odnakovi hromatichni mnogochleni ale neizomorfni grafi mozhut buti hromatichno ekvivalentnimi Napriklad vsi dereva z n vershinami mayut odnakovi hromatichni mnogochleni x 1 n 1 x displaystyle x 1 n 1 x Zokrema x 1 3 x displaystyle x 1 3 x ye hromatichnim mnogochlenom yak dlya kleshni tak i dlya shlyahu z 4 vershinami Hromatichna yedinist Graf hromatichno unikalnij yaksho vin viznachayetsya hromatichnim mnogochlenom z tochnistyu do izomorfizmu Inshimi slovami yaksho graf G hromatichno unikalnij to z P G t P H t displaystyle P G t P H t viplivaye sho G i H izomorfni Vsi cikli hromatichno unikalni Hromatichni koreni Korin abo nul hromatichnogo mnogochlena nazivayetsya hromatichnim korenem ce znachennya x dlya yakogo P G x 0 displaystyle P G x 0 Hromatichni koreni dobre vivcheno Faktichno Birkgof uviv hromatichnij mnogochlen shob pokazati sho dlya planarnih grafiv P G x gt 0 displaystyle P G x gt 0 dlya x 4 Ce dovelo b teoremu pro chotiri farbi Niyakij graf ne mozhna rozfarbuvati v 0 koloriv tak sho 0 zavzhdi ye hromatichnim korenem Tilki grafi bez reber mozhna rozfarbuvati v odin kolir tak sho 1 ye hromatichnim korenem bud yakogo grafa sho maye shonajmenshe odne rebro Z inshogo boku za vinyatkom cih dvoh vipadkiv niyakij graf ne mozhe mati hromatichnim korenem dijsne chislo menshe abo rivne 32 27 Rezultat Tatta pov yazuye zolotij peretin ϕ displaystyle phi z vivchennyam hromatichnih koreniv pokazuyuchi sho hromatichni koreni isnuyut duzhe blizko do ϕ 2 displaystyle phi 2 yaksho G n displaystyle G n ye planarnoyu triangulyaciyeyu sferi to P G n ϕ 2 ϕ 5 n displaystyle P G n phi 2 leq phi 5 n Todi yak dijsna pryama takim chinom maye veliki shmatki yaki ne mistyat hromatichnih koreniv ni dlya yakogo grafa bud yaka tochka na kompleksnij ploshini dovilno blizka do hromatichnogo korenya v tomu sensi sho isnuye neskinchenne simejstvo grafiv hromatichni koreni yakih shilni na kompleksnij ploshini Kategorizaciya Hromatichnij mnogochlen kategorizovano za dopomogoyu teoriyi gomologij blizko pov yazanoyi z en AlgoritmiHromatichnij mnogochlenVhidGraf G z n vershinami VihidKoeficiyenti P G t displaystyle P G t Chas robotiO 2 n n r displaystyle O 2 n n r dlya deyakoyi konstanti r displaystyle r Skladnist skladnaZvoditsya z 3SAT k rozfarbuvannyaVhidGraf G z n vershinami VihidP G k displaystyle P G k Chas robotiNalezhit P dlya k 0 1 2 displaystyle k 0 1 2 O 1 626 2 n displaystyle O 1 6262 n dlya k 3 displaystyle k 3 V inshomu vipadku O 2 n n r displaystyle O 2 n n r dlya deyakoyi konstanti r displaystyle r Skladnist skladna krim vipadkiv k 0 1 2 displaystyle k 0 1 2 AproksimovanistNemaye FPRAS dlya k gt 2 displaystyle k gt 2 Obchislyuvalni zadachi pov yazani z hromatichnimi mnogochlenami znahodzhennya hromatichnogo mnogochlena P G t displaystyle P G t dlya danogo grafa G obchislennya P G k displaystyle P G k u fiksovanij tochci k dlya danogo grafa G Persha zadacha bilsh zagalna oskilki znayuchi koeficiyenti P G t displaystyle P G t mozhna obchisliti znachennya mnogochlena v bud yakij tochci za polinomialnij chas Obchislyuvalna skladnist drugoyi zadachi silno zalezhit vid velichini k Koli k naturalne chislo zadachu mozhna rozglyadati yak obchislennya kilkosti k rozfarbuvan danogo grafa Napriklad zadacha vklyuchaye pidrahunok 3 rozfarbuvan yak kanonichnu zadachu dlya vivchennya skladnosti pidrahunku Cya zadacha ye povnoyu v klasi Efektivni algoritmi Dlya deyakih bazovih klasiv grafiv vidomi yavni formuli hromatichnih mnogochleniv Napriklad dlya derev i klik sho pokazano v tablici vishe Vidomi algoritmi polinomialnogo chasu dlya obchislennya hromatichnogo mnogochlena dlya shirokogo klasu grafiv do yakogo vhodyat hordalni grafi i grafi z obmezhenoyu klikovoyu shirinoyu Drugij z cih klasiv svoyeyu chergoyu vklyuchaye kografi i grafi z obmezhenoyu derevnoyu shirinoyu taki yak zovniplanarni grafi V interneti roblyatsya sprobi rozv yazati zadachu kolektivno i yim dopomagayut aktivni avtonomni pomichniki osoblivo dlya hromatichnih mnogochleniv visokogo stupenya Vidalennya styaguvannya Rekursivnij sposib obchislennya hromatichnogo mnogochlena bazuyetsya na styaguvanni rebra dlya pari vershin u displaystyle u i v displaystyle v graf G u v displaystyle G uv vihodit shlyahom zlittya dvoh vershin i vidalennya rebra mizh nimi Hromatichnij mnogochlen zadovolnyaye rekursivnomu spivvidnoshennyu P G k P G u v k P G u v k displaystyle P G k P G uv k P G uv k de u displaystyle u i v displaystyle v ye sumizhnimi vershinami i G u v displaystyle G uv ye grafom z vidalenim rebrom u v displaystyle uv Ekvivalentno P G k P G u v k P G u v k displaystyle P G k P G uv k P G uv k yaksho u displaystyle u i v displaystyle v ne sumizhni i G u v displaystyle G uv ye grafom z dodanim rebrom u v displaystyle uv U pershij formi rekursiya pripinyayetsya na nabori porozhnih grafiv Ci rekurentni vidnoshennya nazivayutsya takozh fundamentalnoyu teoremoyu redukciyi Pitannya Tatta pro te yaki inshi vlastivosti grafa vidpovidayut tim samim rekurentnim spivvidnoshennyam privelo do vidkrittya uzagalnennya hromatichnogo mnogochlena na dvi zminni mnogochlena Tatta Virazi dayut rekursivnu proceduru zvanu algoritmom vidalennya styaguvannya yaka ye osnovoyu bagatoh algoritmiv rozfarbuvannya grafiv Funkciya ChromaticPolynomial u sistemi komp yuternoyi algebri Mathematica vikoristovuye drugu rekurentnu formulu yaksho graf shilnij i pershu yaksho graf rozridzhenij Najgirshij chas roboti dlya oboh formul zadovolnyaye rekurentnomu spivvidnoshennyam dlya chisel Fibonachchi tak sho v girshomu vipadku algoritm pracyuye za chas z tochnistyu do deyakogo polinomialnogo koeficiyenta ϕ n m 1 5 2 n m O 1 62 n m displaystyle phi n m left frac 1 sqrt 5 2 right n m in O left 1 62 n m right na grafi z n vershinami i m rebrami Analiz chasu roboti mozhna polipshiti do polinomialnogo mnozhnika chisla t G displaystyle t G kistyakovih derev vhidnogo grafa Na praktici vikoristovuyetsya strategiya gilok i mezh razom z vidkidannyam izomorfnih grafiv shob viklyuchiti rekursivni vikliki i chas zalezhit vid evristiki vikoristovuvanoyi pri vibori pari vershin dlya viklyuchennya styaguvannya Metod kuba Isnuye prirodnij geometrichnij pidhid do rozfarbovuvannya grafiv yaksho zauvazhiti sho pri priznachenni naturalnih chisel kozhnij vershini rozfarbuvannya grafiv ye vektorom cilochiselnoyi gratki Oskilki prisvoyennya dvom vershinam i displaystyle i i j displaystyle j odnogo koloru ekvivalentne rivnosti koordinat i displaystyle i i j displaystyle j u vektori rozfarbuvannya kozhne rebro mozhna asociyuvati z giperploshinoyu vidu x R d x i x j displaystyle x in R d x i x j Nabir takih giperploshin dlya danogo grafa nazivayetsya jogo grafichnoyu en Pravilne rozfarbuvannya grafa ce rozfarbuvannya vektor yakoyi ne viyavlyayetsya na zaboronenij ploshini Obmezheni mnozhinoyu koloriv k displaystyle k tochki reshitki potraplyayut u kub 0 k n displaystyle 0 k n U comu konteksti hromatichnij mnogochlen pidrahovuye tochki gratki v 0 k displaystyle 0 k kubi yaki ne potraplyayut na grafichnu konfiguraciyu Obchislyuvalna skladnist Zadacha obchislennya chisla 3 rozfarbuvan cogo grafa ye kanonichnim prikladom povnoyi zadachi tak sho zadacha obchislennya koeficiyentiv hromatichnogo mnogochlena P skladna Analogichno zadacha obchislennya P G 3 displaystyle P G 3 dlya danogo grafa G P povna Z inshogo boku dlya k 0 1 2 displaystyle k 0 1 2 legko obchisliti P G k displaystyle P G k tak sho vidpovidni zavdannya mayut polinomialnu za chasom skladnist Dlya cilih chisel k gt 3 displaystyle k gt 3 zadacha P skladna sho vstanovlyuyetsya podibno do vipadku k 3 displaystyle k 3 Faktichno vidomo sho P G x displaystyle P G x P skladna dlya vsih x vklyuchno z vid yemnimi cilimi chislami i navit vsima kompleksnimi chislami za vinyatkom troh prostih tochok Takim chinom skladnist obchislennya hromatichnogo mnogochlena povnistyu zrozumila U mnogochleni P G t a 1 t a 2 t 2 a n t n displaystyle P G t a 1 t a 2 t 2 dots a n t n koeficiyent a n displaystyle a n zavzhdi dorivnyuye 1 a takozh vidomi deyaki inshi vlastivosti koeficiyentiv Ce porushuye pitannya chi ne mozhna obchisliti deyaki koeficiyenti prostishe Odnak zadacha obchislennya ar dlya fiksovanogo r i danogo grafa G ye P skladnoyu Ne vidomo zhodnogo aproksimacijnogo algoritmu obchislennya P G x displaystyle P G x dlya bud yakogo x za vinyatkom troh prostih tochok U cilih tochkah k 3 4 displaystyle k 3 4 dots vidpovidna zadacha rozv yaznosti viznachennya chi mozhna danij graf rozfarbuvati v k koloriv NP skladna Taki zadachi ne mozhna aproksimuvati z bud yakim koeficiyentom za dopomogoyu polinomialnogo jmovirnisnogo algoritmu z obmezhenoyu pomilkoyu hiba tilki NP RP oskilki bud yaka multiplikativna aproksimaciya rozriznyala b znachennya 0 i 1 sho bulo b efektivnim rozv yazkom zadachi za dopomogoyu polinomialnogo jmovirnisnogo algoritmu z obmezhenoyu pomilkoyu u formi zadachi rozv yaznosti Zokrema pri deyakih pripushennyah ce viklyuchaye mozhlivist povnistyu polinomialnoyi randomizovanoyi aproksimacijnoyi shemi FPRAS Dlya inshih tochok potribni skladnishi mirkuvannya i pitannya perebuvaye u fokusi aktivnih poshukiv Na 2008 rik vidomo sho ne isnuye dlya obchislennya P G x displaystyle P G x dlya bud yakogo x gt 2 hiba tilki NP PrimitkiBiggs 1993 s deyaki rozdili Stanley 1973 Huh 2012 Chao Whitehead 1978 Jackson 1993 Sokal 2004 Helme Guizon Rong 2005 Naor Naor Schaffer 1987 Gimenez Hlineny Noy 2005 Makowsky Rotics Averbouch Godlin 2006 Shirado Christakis 2017 s 370 374 Dong Koh Teo 2005 Pemmaraju Skiena 2003 Wilf 1986 Sekine Imai Tani 1995 Yeger Vertigan i Velsh Jaeger Vertigan Welsh 1990 gruntuyuchis na zvedenni Liniala Linial 1986 Oxley Welsh 2002 Goldberg Jerrum 2008 LiteraturaA Yu Evnin Hromaticheskij mnogochlen grafa v zadachah 2014 4 72 26 iyunya S 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 T 545 vip 7654 26 chervnya S 370 374 DOI 10 1038 nature22332 Chao C Y Whitehead E G On chromatic equivalence of graphs Theory and Applications of Graphs Springer 1978 T 642 S 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 Gimenez O Hlineny 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 T 3787 S 59 68 DOI 10 1007 11604686 6 Goldberg L A Jerrum M Inapproximability of the Tutte polynomial Information and Computation 2008 T 206 vip 7 26 chervnya S 908 DOI 10 1016 j ic 2008 04 003 Laure Helme Guizon Yongwu Rong A categorification of the chromatic polynomial Algebraic amp Geometric Topology 2005 T 5 vip 4 26 chervnya S 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 26 chervnya Jackson B A Zero Free Interval for Chromatic Polynomials of Graphs Combinatorics Probability and Computing 1993 T 2 26 chervnya S 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 T 108 26 chervnya S 35 53 DOI 10 1017 S0305004100068936 Linial N Hard enumeration problems in geometry and combinatorics SIAM J Algebraic Discrete Methods 1986 T 7 vip 2 26 chervnya S 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 T 4271 S 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 S 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 T 11 vip 4 26 chervnya S 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 S 224 233 Sokal A D Chromatic Roots are Dense in the Whole Complex Plane 2004 T 13 vip 2 26 chervnya S 221 261 DOI 10 1017 S0963548303006023 Stanley R P Acyclic orientations of graphs 1973 T 5 vip 2 26 chervnya S 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 PosilannyaWeisstein Eric W Chromatic polynomial angl na sajti Wolfram MathWorld PlanetMath Chromatic polinomialni 20 serpnya 2008 u Wayback Machine Code for computing Tutte Chromatic and Flow Polinomiv by Gary Haggard David J Pearce and Gordon Royle 1