Chromatický polynom

Chromatický polynom je polynom studovaný v algebraické teorii grafů , který představuje počet zabarvení grafu jako funkci počtu barev. Původně ji definoval George Birkhoff jako pokus vyřešit problém čtyř barev . Tutt , zobecněný a systematicky studovaný Hasslerem Whitneyem , zobecnil chromatický polynom na Tuttův polynom tím, že jej dal do souvislosti s Pottsovým modelem fyziky .

Historie

George Birkhoff představil chromatický polynom v roce 1912 a definoval jej pouze pro rovinné grafy ve snaze dokázat větu o čtyřech barvách . Jestliže udává počet správných zabarvení grafu G k barvami, pak by se dala dokázat věta o čtyřech barvách tím, že pro všechny rovinné grafy G . Tímto způsobem doufal, že využije sílu počtu a algebry ke studiu kořenů polynomů ke studiu problému kombinatorického zbarvení. $P(G,k)$ $P(G,4)>0$

Hassler Whitney zobecnil Birkhoffův polynom z rovinného případu na obecné grafy v roce 1932. V roce 1968 Reed položil otázku, které polynomy jsou chromatické polynomy pro některé grafy (problém zůstává otevřený), a zavedl pojem chromaticky ekvivalentních grafů. V současné době jsou chromatické polynomy ústředními objekty algebraické teorie grafů [1] .

Definice

Chromatický polynom grafu G počítá počet správných zabarvení vrcholů . Polynom je obvykle označován jako , , nebo . Druhý zápis bude použit ve zbytku článku. $P_{G}(k)$ $\chi _{G}(k)$ $\pi _{G}(k)$ $P(G,k)$

Například cestu se 3 vrcholy nelze obarvit 0 barvami nebo 1 barvou. Pomocí 2 barev lze graf vybarvit dvěma způsoby. Pomocí 3 barev lze graf vybarvit 12 způsoby. $P_{3}$

Dostupné barvy $k$	0	jeden	2	3
Počet omalovánek $P(P_{3},k)$	0	0	2	12

Je -li dán graf G s n vrcholy, je chromatický polynom definován jako jedinečný interpolační polynom stupně nejvýše n procházejícího body.

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

Pokud graf G neobsahuje žádné vrcholy se smyčkami, pak chromatický polynom je redukovaný polynom stupně přesně n . Ve skutečnosti pro výše uvedený příklad máme

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

Chromatický polynom obsahuje alespoň tolik informací o vybarvitelnosti grafu G , kolik je obsaženo v chromatickém čísle. Navíc chromatické číslo je nejmenší kladné celé číslo, pro které chromatický polynom nezmizí,

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

Příklady

Chromatické polynomy pro některé grafy

Trojúhelník $K_{3}$	$t(t-1)(t-2)$
Kompletní graf $K_n$	$t(t-1)(t-2)\cdots (t-(n-1))$
Cesta $P_{n}$	$t(t-1)^{{n-1}}$
Libovolný strom s n vrcholy	$t(t-1)^{{n-1}}$
Cyklus $C_{n}$	$(t-1)^{n}+(-1)^{n}(t-1)$
hrabě z Petersenu	$t(t-1)(t-2)\left(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{ 2}+775t-352\vpravo)$

Vlastnosti

Pro pevný graf G s n vrcholy je chromatický polynom ve skutečnosti polynom stupně n . Podle definice výpočet hodnoty polynomu udává počet k -zabarvení grafu G pro . Totéž platí pro k > n . $P(G,t)$ $P(G,k)$ $k=0,1,\cdots ,n$

Výraz

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

udává počet acyklických orientací grafu G [2] .

Hodnota derivace polynomu v bodě 1 je až do znaménka rovna chromatickému invariantu . $P'(G,1)$ $\theta (G)$

Pokud má graf G n vrcholů, m hran a c komponent , pak $G_{1},\cdots ,G_{c}$

Koeficienty pro jsou rovny nule. ${\displaystyle t^{0},\cdots ,t^{c-1))$
Všechny koeficienty pro jsou nenulové. ${\displaystyle t^{c},\cdots ,t^{n))$
Koeficient at je roven 1. $t^{n}$ $P(G,t)$
Koeficient at je roven . $t^{n-1}$ $P(G,t)$ $-m$
Koeficienty libovolného chromatického polynomu jsou znaménkové střídavé.
Absolutní hodnoty koeficientů libovolného chromatického polynomu tvoří logaritmicky konkávní sekvenci [3] .
$P(G,t)=P(G_{1},t)P(G_{2},t)\cdots P(G_{c},t)$

Graf G s n vrcholy je strom právě tehdy a jen tehdy

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

Chromatická ekvivalence

O dvou grafech se říká, že jsou chromaticky ekvivalentní, pokud mají stejné chromatické polynomy. Izomorfní grafy mají stejné chromatické polynomy, ale neizomorfní grafy mohou být chromaticky ekvivalentní. Například všechny stromy s n vrcholy mají stejné chromatické polynomy:

(x-1)^{n-1}x,

Zejména,

(x-1)^{3}x

je chromatický polynom pro dráp i 4-vrcholovou cestu .

Chromatická jedinečnost

Graf je chromaticky jedinečný, pokud je definován chromatickým polynomem až po izomorfismus. Jinými slovy, pokud je graf G chromaticky jedinečný, pak z toho plyne, že G a H jsou izomorfní. $P(G,t)=P(H,t)$

Všechny cykly jsou chromaticky jedinečné [4] .

Chromatické kořeny

Kořen (nebo nula ) chromatického polynomu (nazývaného „chromatický kořen“) je hodnota x , pro kterou . Chromatické kořeny jsou dobře studovány. Ve skutečnosti Birkhoffova původní motivace pro zavedení chromatického polynomu měla ukázat, že pro rovinné grafy pro x ≥ 4. To by dokázalo teorém o čtyřech barvách . $P(G,x)=0$ $P(G,x)>0$

Žádný graf nemůže být obarven 0 barvami, takže 0 je vždy chromatický kořen. Pouze grafy bez hran mohou být jednobarevné, takže 1 je chromatický kořen každého grafu s alespoň jednou hranou. Na druhou stranu, s výjimkou těchto dvou případů, žádný graf nemůže mít reálné číslo jako svůj chromatický kořen menší nebo rovný 32/27 [5] . Tattův výsledek dává zlatý řez do souvislosti se studiem chromatických kořenů, což ukazuje, že chromatické kořeny existují velmi blízko - pokud je rovinná triangulace koule, pak $\phi$ $\phi ^{2}$ $G_{n}$

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

Zatímco reálná čára má tedy velké kusy, které neobsahují žádné chromatické kořeny pro žádný graf, jakýkoli bod v komplexní rovině je libovolně blízko chromatickému kořenu v tom smyslu, že existuje nekonečná rodina grafů, jejichž chromatické kořeny jsou v komplexní rovině husté. rovina [6] .

Kategorizace

Chromatický polynom je kategorizován pomocí teorie homologie, která je blízce příbuzná Khovanovově homologii [7] .

Algoritmy

Chromatický polynom
Vchod	Graf G s n vrcholy.
Výstup	Kurzy $P(G,t)$
Pracovní doba	$O(2^{n}n^{r})$ za nějakou stálou $r$
Složitost	#P je těžké
Sníženo z	#3SAT

#k-barvení
Vchod	Graf G s n vrcholy.
Výstup	$P(G,k)$
Pracovní doba	Patří do P pro . pro . v opačném případě $k=0,1,2$ $O(1{,}6262^{n})$ $k=3$ $O(2^{n}n^{r})$ za nějakou stálou $r$
Složitost	#P je zatím těžké $k=0,1,2$
Přibližnost	Žádné FPRAS pro $k>2$

Výpočtové problémy související s chromatickými polynomy

nalezení chromatického polynomu pro daný graf G ; $P(G,t)$
výpočet v pevném bodě k pro daný graf G . $P(G,k)$

První problém je obecnější, protože se znalostí koeficientů můžeme vypočítat hodnotu polynomu v libovolném bodě polynomického času. Výpočetní složitost druhého problému silně závisí na hodnotě k . Když k je přirozené číslo, problém lze považovat za výpočet počtu k -zabarvení daného grafu. Například problém zahrnuje počítání 3 zabarvení jako kanonický problém pro studium složitosti počítání. Tento úkol je dokončen ve třídě #P . $P(G,t)$

Efektivní algoritmy

Pro některé základní třídy grafů jsou známy explicitní vzorce pro chromatické polynomy. To platí například pro stromy a kliky, jak je uvedeno v tabulce výše.

Jsou známy polynomiální časové algoritmy pro výpočet chromatického polynomu pro širokou třídu grafů, která zahrnuje akordické grafy [8] a grafy s omezenou šířkou kliky [9] [10] . Druhá z těchto tříd zase zahrnuje cography a grafy s omezenou šířkou stromu , jako jsou vnější rovinné grafy .

Na internetu jsou lidé, kteří se snaží problém řešit kolektivně a pomáhají jim aktivní autonomní pomocníci, zejména u vysokostupňových chromatických polynomů [11] .

Odstranění - kontrakce

Rekurzivní způsob výpočtu chromatického polynomu je založen na kontrakci hrany - pro dvojici vrcholů a graf se získá sloučením dvou vrcholů a odstraněním hrany mezi nimi. Chromatický polynom splňuje rekurzivní vztah $u$ $proti$ $fotr$

P(G,k)=P(G-uv,k)-P(G/uv,k)

kde a jsou sousední vrcholy a je graf s odstraněnou hranou . ekvivalentně, $u$ $proti$ $G-uv$ $UV$

P(G,k)=P(G+uv,k)+P(G/uv,k)

jestliže a nejsou sousedící a je graf s přidanou hranou . V první formě se rekurze zastaví na množině prázdných grafů. Tyto rekurentní vztahy se také nazývají základní redukční teorém [12] . Tuttova otázka , jaké další vlastnosti grafu splňují stejné rekurentní vztahy, vedla k objevu dvouproměnného zobecnění chromatického polynomu, Tuttova polynomu . $u$ $proti$ $G+uv$ $UV$

Výrazy poskytují rekurzivní proceduru zvanou algoritmus odstranění-kontrakce , který je základem mnoha algoritmů pro barvení grafů. Funkce ChromaticPolynomial v systému počítačové algebry Mathematica používá druhý rekurzivní vzorec, pokud je graf hustý, a první, pokud je graf řídký [13] . Nejhorší doba běhu pro oba vzorce splňuje recidivační vztah pro Fibonacciho čísla , takže v nejhorším případě algoritmus běží v čase (do nějakého polynomiálního faktoru)

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

na grafu s n vrcholy a m hranami [14] . Analýzu doby běhu lze zlepšit na polynomiální faktor počtu kostry vstupního grafu [15] . V praxi se k eliminaci rekurzivních volání používá strategie větvení a ohraničení spolu s isomorphic graph dropping , přičemž čas závisí na heuristice použité při výběru páru vrcholů (pro drop-pull). $t(G)$

Metoda kostky

K vybarvování grafů existuje přirozený geometrický přístup, pokud si všimnete, že když každému vrcholu přiřadíte přirozená čísla, vybarvení grafů je vektor celočíselné mřížky. Protože přiřazení dvou vrcholů a stejné barvy je ekvivalentní rovnosti souřadnic a ve vektoru zbarvení, může být každá hrana spojena s nadrovinou formuláře . Množina takových nadrovin pro daný graf se nazývá jeho grafická konfigurace nadroviny . Správné zbarvení grafu je takové zbarvení, jehož vektor se nevyskytuje v zakázané rovině. Body mřížky jsou omezeny mnoha barvami a spadají do krychle . V tomto kontextu chromatický polynom počítá body mřížky v -kostce, které nespadají do grafické konfigurace. $i$ $j$ $i$ $j$ $\{x\in R^{d}:x_{i}=x_{j}\}$ $k$ ${\displaystyle [0,k]^{n))$ $[0,k]$

Výpočetní složitost

Problém výpočtu počtu 3-zabarvení daného grafu je kanonickým příkladem #P -úplného problému, takže problém výpočtu koeficientů chromatického polynomu je #P-těžký. Podobně je výpočet pro daný graf G #P-úplný. Na druhou stranu je snadné počítat pro , takže odpovídající problémy mají polynomiální časovou složitost. U celých čísel je problém #P-hard, což je stanoveno podobně jako v případě . Ve skutečnosti je známo, že je #P-tvrdé pro všechna x (včetně záporných celých čísel a dokonce všech komplexních čísel), kromě tří „prvobodů“ [16] . Složitost výpočtu chromatického polynomu je tedy zcela pochopitelná. $P(G,3)$ $k=0,1,2$ $P(G,k)$ $k>3$ $k=3$ $P(G,x)$

V polynomu

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

koeficient je vždy 1 a jsou známy i některé další vlastnosti koeficientů. To vyvolává otázku, zda lze některé koeficienty vypočítat jednodušeji. Problém výpočtu a r pro pevné r a daný graf G je však #P-těžký [17] . $a_n$

Pro žádné x není znám žádný přibližný výpočetní algoritmus , kromě tří jednoduchých bodů. V celočíselných bodech je odpovídající problém řešitelnosti určení, zda lze daný graf obarvit k barvami , NP-těžký . Takové problémy nelze aproximovat žádným faktorem s omezeným chybovým polynomickým pravděpodobnostním algoritmem, s výjimkou NP = RP, protože jakákoli multiplikativní aproximace by rozlišovala mezi 0 a 1, což by bylo efektivním řešením problému s omezeným chybovým polynomickým pravděpodobnostním algoritmem v forma problému řešitelnosti . Zejména to za určitých předpokladů vylučuje možnost plně polynomiálního randomizovaného aproximačního schématu (FPRAS) . U ostatních bodů je zapotřebí komplexnější úvaha a problém je v centru pozornosti aktivního výzkumu. Od roku 2008 je známo, že neexistuje žádné schéma FPRAS pro výpočet pro libovolné x > 2, kromě NP = RP [18] . $P(G,x)$ $k=3,4,\tečky$ $P(G,x)$

Poznámky

↑ Biggs, 1993 , str. Některé kapitoly.
↑ Stanley, 1973 .
↑ Hurá, 2012 .
↑ Chao, Whitehead, 1978 .
↑ Jackson, 1993 .
↑ Sokal, 2004 .
↑ Helme-Guizon, Rong, 2005 .
↑ Naor, Naor, Schaffer, 1987 .
↑ Giménez, Hliněny, Noy, 2005 .
↑ Makowsky, Rotics, Averbouch, Godlin, 2006 .
↑ Shirado, Christakis, 2017 , str. 370–374.
↑ Dong, Koh, Teo, 2005 .
↑ Pemmaraju, Skiena, 2003 .
↑ Wilf, 1986 .
↑ Sekine, Imai, Tani, 1995 .
↑ Jaeger, Vertigan a Welsh ( Jaeger, Vertigan, Welsh 1990 ), založené na Linialově míchání ( Linial 1986 ).
↑ Oxley, Wales, 2002 .
↑ Goldberg, Jerrum, 2008 .

Literatura

A. Yu, Evnin. Chromatický polynom grafu v úlohách // Matematická výchova . - 2014. - č. 4 (72) . - S. 9-15 . (Ruština)
Biggs N. Algebraická teorie grafů. - Cambridge University Press, 1993. - ISBN 0-521-45897-8 .
Hirokazu Shirado, Nicholas A. Christakis. Lokálně hluční autonomní agenti zlepšují globální lidskou koordinaci v síťových experimentech // Nature. - 2017. - T. 545 , č.p. 7654 . — S. 370–374 . - doi : 10.1038/příroda22332 .
Chao C.-Y., Whitehead EG O chromatické ekvivalenci grafů // Teorie a aplikace grafů. - Springer, 1978. - T. 642. - S. 121-131. — (Poznámky z matematiky). - ISBN 978-3-540-08666-6 .
Dong FM, Koh KM, Teo KL Chromatické polynomy a barevnost grafů. - 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. práce. Graf-teoretické koncepty v informatice (WG 2005). - Springer-Verlag, 2005. - T. 3787. - S. 59–68. - doi : 10.1007/11604686_6 .
Goldberg LA, Jerrum M. Neaproximovatelnost Tutteho polynomu // Informace a výpočty. - 2008. - T. 206 , č. 7 . - S. 908 . - doi : 10.1016/j.ic.2008.04.003 .
Laure Helme-Guizon, Yongwu Rong. Kategorizace chromatického polynomu // Algebraická a geometrická topologie. - 2005. - V. 5 , čís. 4 . - S. 1365-1388 . - doi : 10.2140/agt.2005.5.1365 .
Huh J. Milnor čísla projektivních hyperploch a chromatický polynom grafů. — arXiv:1008.4749v3, 2012.
Jackson B. Zero-Free Interval for Chromatic Polynomials of Graphs // Combinatorics, Probability and Computing. - 1993. - T. 2 . — S. 325–336 . - doi : 10.1017/S0963548300000705 .
Jaeger F., Vertigan DL, Welsh DJA O výpočetní složitosti Jonesových a Tutteových polynomů // Mathematical Proceedings of the Cambridge Philosophical Society. - 1990. - T. 108 . — s. 35–53 . - doi : 10.1017/S0305004100068936 .
Linial N. Tvrdé výčtové problémy v geometrii a kombinatorice // SIAM J. Algebraické diskrétní metody. - 1986. - T. 7 , no. 2 . — S. 331–335 . - doi : 10.1137/0607036 .
Makowsky JA, Rotics U., Averbouch I., Godlin B. Computing graph polynomials on graphs of bounded clique-width // Proc. 32nd Int. práce. Graf-teoretické koncepty v informatice (WG 2006). - Springer-Verlag, 2006. - T. 4271. - S. 191-204. — (Poznámky z informatiky). - doi : 10.1007/11917496_18 .
Naor J., Naor M., Schaffer A. Rychlé paralelní algoritmy pro akordické grafy // Proc. 19. ACM Symp. Theory of Computing (STOC '87). - 1987. - S. 355-364. doi : 10.1145 / 28395.28433 .
Oxley JG, Welsh DJA Chromatické, průtokové a spolehlivostní polynomy: Složitost jejich koeficientů. // Kombinatorika, pravděpodobnost a výpočetní technika . - 2002. - T. 11 , no. 4 . — S. 403–426 .
Pemmaraju S., Skiena S. sekce 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 graf of medium size // Algorithms and Computation, 6th International Symposium, Lecture Notes in Computer Science 1004. — Cairns, Australia, 4.–6. prosince 1995: Springer, 1995, s. 224–233.
Chromatické kořeny Sokal AD jsou husté v celé komplexní rovině // Kombinatorika, pravděpodobnost a výpočetní technika . - 2004. - T. 13 , no. 2 . — S. 221–261 . - doi : 10.1017/S0963548303006023 .
Stanley R.P. Acyklické orientace grafů // Disk. Matematika. . - 1973. - V. 5 , čís. 2 . — S. 171–178 . - doi : 10.1016/0012-365X(73)90108-8 .
Vitalij I Vološin. Barvení smíšených hypergrafů: Teorie, algoritmy a aplikace.. - Americká matematická společnost, 2002. - ISBN 0-8218-2812-6 .
Wilf H.S. Algoritmy a složitost. - Prentice-Hall, 1986. - ISBN 0-13-021973-8 .

Odkazy

Weisstein, Eric W. Chromatický polynom (anglicky) na webu Wolfram MathWorld .
PlanetMath Chromatický polynom
Kód pro výpočet Tutteových, chromatických a průtokových polynomů Gary Haggard, David J. Pearce a Gordon Royle: [1] (nedostupný odkaz)