Kromatikus polinom

A matematikai gráfelmélet területén a kromatikus polinom az algebrai gráfelmélet által tanulmányozott gráfpolinom. A felhasználható színek számának függvényében számolja meg a lehetséges gráfszínezéseket. A kromatikus polinomot eredetileg George David Birkhoff definiálta a négyszín-probléma megoldása érdekében. Később H. Whitney és W. T. Tutte Tutte-polinom néven általánosították, ami a statisztikus fizika Potts-modelljéhez kapcsolja a kromatikus polinomot.

A 3 csúcson megrajzolható összes, nem izomorf gráf és kromatikus polinomjaik. Felülről az óra járásával megegyező irányban, a független 3-halmaz: $k^{3}$; egy él és egy független csúcs: $k^{2}(k-1)$; a 3-út: $k(k-1)^{2}$; a 3-klikk: $k(k-1)(k-2)$.

Történet

George David Birkhoff 1912-ben vezette be a kezdetben csak síkbarajzolható gráfokra definiált kromatikus polinomot a négyszíntétel bizonyítása érdekében. Ha $P(G,k)$ G k színnel való jó színezéseinek számát jelöli, akkor a négyszíntétel bizonyítható annak megmutatásával, hogy $P(G,4)>0$ minden G síkbarajzolható gráfra. Azt tervezte, hogy az analízis és algebra a polinomok gyökeire vonatkozó jól fejlett eszköztárát alkalmazza a kombinatorikus színezési problémára.

Hassler Whitney a Birkhoff-polinomot 1932-ben általánosította síkbarajzolható gráfokról általános gráfokra. 1968-ban Read feltette a máig nyitott kérdést, hogy adott polinom vajon kromatikus polinomja-e valamely gráfnak, és bevezette a kromatikusan egyenértékű gráfok fogalmát. Jelenleg a kromatikus polinomok az algebrai gráfelmélet központi témái közé tartoznak.

Definíció

A 3 csúcsú gráfok k színnel történő összes jó színezése $k=0,1,2,3$-ra. Minden gráf kromatikus polinomja a jó színezések számát interpolálja.

A G gráf kromatikus polinomja a gráf jó csúcsszínezéseinek számát adja meg. Gyakori jelölései $P_{G}(k)$, $\chi _{G}(k)$, $\pi _{G}(k)$ vagy $P(G,k),$ amit a szócikk a továbbiakban használni fog.

Tekintsük a három csúcsú $P_{3}$ útgráfot, ami 0 vagy 1 színnel nem színezhető, kétféleképpen 2-színezhető, és tizenkétféle 3-színezése van.

Rendelkezésre álló színek $k$	0	1	2	3
Színezések száma $P(P_{3},k)$	0	0	2	12

Az n csúcsú G gráf kromatikus polinomja definíciója szerint a legfeljebb n-edfokú, egyedi interpolációs polinom a következő pontok között:

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

Ha G egyik csúcsában sincs hurokél, akkor a kromatikus polinom pontosan n-edfokú monikus polinom. A fenti példában a következő:

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

A kromatikus polinom legalább a kromatikus számmal megegyező információt hordoz G színezhetőségéről. A kromatikus szám továbbá a legkisebb pozitív egész szám, ami nem zérushelye a kromatikus polinomnak:

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

Példák

Néhány gráf kromatikus polinomja

$K_{3}$ háromszög	$t(t-1)(t-2)$
$K_{n}$ teljes gráf	$t(t-1)(t-2)\cdots (t-(n-1))$
n csúcsú fagráf	$t(t-1)^{n-1}$
$C_{n}$ körgráf	$(t-1)^{n}+(-1)^{n}(t-1)$
Petersen-gráf	$t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)$
Üres csúcshalmazú gráf	konstans 1

Megjegyzés: A matematikában nincs konszenzus arról, hogy lehet-e egy gráf csúcshalmaza üres. Ha eme elfajuló esetet megengedjük, akkor e gráf kromatikus polinomja célszerűen konstans 1-nek tekintendő, így őrződik meg az, hogy a csúcsszámmal megegyező fokú, 1 főegyütthatójú polinom a kromatikus polinom.

Tulajdonságok

Az n csúcsú G gráfhoz tartozó $P(G,t)$ kromatikus polinom valóban egy n-edfokú polinom. A definíció alapján a kromatikus polinomot a $P(G,k)$ helyen kiértékelve megkapjuk G k-színezéseinek számát $k=0,1,\cdots ,n$-re. Ugyanaz igaz akkor is, ha k > n.

A

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

kifejezés megadja G körmentes orientációinak számát.

Az 1 helyen kiértékelt derivált, $P'(G,1)$ előjel erejéig megegyezik a $\theta (G)$ kromatikus invariánssal.

Ha a G gráfnak n csúcsa, m éle és $G_{1},\cdots ,G_{c}$ között c összefüggő komponense van, akkor

• A $t^{0},\cdots ,t^{c-1}$ együtthatói nullák.
• A $t^{c},\cdots ,t^{n}$ együtthatói nem nullák, speciálisan $t^{n}$ együtthatója 1.
• A $t^{n}$ együtthatója $P(G,t)$-ben 1.
• A $t^{n-1}$ együtthatója $P(G,t)$-ben $-m$.
• Minden kromatikus polinom együtthatói váltakozó előjelűek.
• Bármely kromatikus polinom együtthatóinak abszolút értékei log-konkáv sorozatot alkotnak.
• $\scriptstyle P(G,t)=P(G_{1},t)P(G_{2},t)\cdots P(G_{c},t)$

Az n csúcsú G gráf pontosan akkor fa, ha

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

Kromatikus ekvivalencia

A három gráf, melynek kromatikus polinomja $(x-2)(x-1)^{3}x$.

Két gráf akkor kromatikusan egyenértékű, ha ugyanaz a kromatikus polinom tartozik hozzájuk. Izomorf gráfok kromatikus polinomjai természetesen megegyeznek, de nem izomorf gráfok is lehetnek kromatikusan ekvivalensek. Például az összes n csúcsú fának ugyanaz a kromatikus polinomja:

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

ezen belül az,

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

a mancsgráf és a 4 csúcsú útgráf kromatikus polinomja is.

Kromatikus egyediség

Egy gráf kromatikusan egyedi, ha izomorfizmus erejéig meghatározza kromatikus polinomja. Más szavakkal, ha G kromatikusan egyedi, akkor ha $P(G,t)=P(H,t)$, akkor G és H izomorf.

Az összes körgráf kromatikusan egyedi.

Kromatikus gyökök

Egy kromatikus polinom gyöke (vagy zérushelye), azaz a „kromatikus gyök” olyan x érték, ahol $P(G,x)=0$. A kromatikus gyököket behatóan tanulmányozták. Jól ismert, hogy egyetlen gráf kromatikus polinomjának sincs gyöke sem a $[-\infty ,0)$, sem a $(0,1)$ intervallumban, Jackson pedig az $(1,{\frac {32}{27}}\sim 1,185)$ intervallumot zárta ki, melynek felső határa éles.

Birkhoff eredeti célja a kromatikus polinom bevezetésével az volt, hogy síkbarajzolható gráfok esetében igazolja az $P(G,x)>0$ egyenlőtlenséget az x ≥ 4 esetre. Ez bizonyította volna a négyszín-tételt. Birkhoff és Lewis bebizonyította, hogy ezen kromatikus polinomoknak nincs zérushelye a $[-\infty ,0)$, $(0,1)$, $(1,2)$ $[5,\infty )$ intervallumokban és hogy $P(G,4)\neq 0$, az eredeti sejtést azonban nem sikerült igazolniuk. Woodall javított eredménye szerint nincs zérushely a $(2,\sim 2,546602)$ intervallumban sem, mely utóbbi szám az oktaéder kromatikus polinomjának ($x^{3}-9x^{2}+29x-32=0$) valós gyöke.

Egyetlen gráf se 0-színezhető, ezért 0 mindig kromatikus gyök. Csak az élmentes gráfok 1-színezhetők, ezért az 1 kromatikus gyöke minden olyan gráfnak, ami legalább egy élt tartalmaz. Ezen a két ponton kívül tehát csak 32/27-nél nagyobb valós gyökök létezhetnek.

Tutte egy eredménye összeköti $\phi$-t, az aranymetszés arányát a kromatikus gyökök tanulmányozásával, megmutatva, hogy a kromatikus gyökök igen közel esnek $\phi ^{2}$-hez: Ha $G_{n}$ egy gömb síkháromszögelése, akkor

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

A valós számegyenes nagy része ilyenformán nem tartalmazza egyetlen gráf kromatikus gyökeit sem, ellenben a komplex számsík minden pontja tetszőlegesen közel van egy kromatikus gyökhöz abban az értelemben, hogy létezik olyan végtelen gráfcsalád, melynek kromatikus gyökei a komplex számsíkon sűrűek.

Kategorifikáció

A kromatikus polinomot kategorifikáló homológiaelmélet szorosan kapcsolódik a Khovanov-homológiához.

Algoritmusok

A kromatikus polinommal összefüggő számítási problémák közé tartozik:

• adott G gráf $P(G,t)$ kromatikus polinomjának megkeresése;
• adott G gráf $P(G,k)$kromatikus polinomjának kiértékelése rögzített k pontban.

Az első probléma általánosabb, hiszen ha ismerjük $P(G,t)$ együtthatóit, bármely függvényérték polinom időben kiszámítható, mivel a fokszám n. A második probléma nehézsége nagyban függ k értékétől, és a bonyolultságelmélet behatóan tanulmányozta. Ha k természetes szám, akkor a probléma egyenértékű adott gráf k-színezéseinek leszámlálásával. Például idetartozik a #3-színezés probléma, avagy a 3-színezések leszámlálása, ami a számlálásbonyolultság tanulmányozásának kanonikus problémája, a számlálási problémák #P osztályára teljes.

Hatékony algoritmusok

Néhány egyszerűbb gráfosztály esetén ismert a kromatikus polinom zárt alakjának képlete. Igaz ez például a fák és klikkek esetére, ahogy a fenti táblázatban is olvasható.

A kromatikus polinom kiszámítására a gráfok szélesebb körére léteznek polinom idejű algoritmusok; ebbe a körbe tartoznak a merev körű gráfpl és a korlátos klikkszélességű gráfok. Ez utóbbiak közé tartoznak a kográfok és a korlátos favastagságú gráfok, mint például a külsíkgráfok.

Törlés-összehúzás

A kromatikus polinom kiszámításának rekurzív módja az élösszehúzáson alapul: az $u$ és $v$ csúcspár esetén a $G/uv$ gráf megkapható a két csúcs összeolvasztásával és a köztük lévő esetleges élek eltávolításával. Ekkor a kromatikus polinom a következő rekurrenciarelációnak tesz eleget:

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

ahol $u$ és $v$ szomszédos csúcsok, $G-uv$ pedig az $uv$ él eltávolításával kapott gráf. Ezzel ekvivalens, hogy

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

amennyiben $u$ és $v$ nem szomszédosak és $G+uv$ az $uv$ éllel kiegészített gráf. Az első alak esetén a rekurrencia üres gráfok gyűjteményén ér véget, a második alak esetén teljes gráfok gyűjteményén. Ezeket a rekurrenciákat fundamentális redukciós tételnek (Fundamental Reduction Theorem) is nevezik. Tutte az iránti érdeklődése, hogy milyen egyéb gráftulajdonságok elégítenek ki hasonló rekurrenciákat vezette el a kromatikus polinom kétváltozós általánosításának, a Tutte-polinomnak a felfedezéséhez.

Az előbb említett rekurzív művelet a „törlés–összehúzás-algoritmus” (deletion–contraction algorithm), ami számos gráfszínezési algoritmusnak szolgál alapul. A Mathematica számítógépes algebrarendszerbe épített ChromaticPolynomial függvény a második rekurrenciát használja, ha a gráf sűrű, az elsőt, ha a gráf ritka. A legrosszabb eset futásideje mindkét képletnél a Fibonacci-számok rekurrenciarelációjának felel meg, tehát a legrosszabb esetben az algoritmus a következő kifejezés polinom faktorában fut:

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

egy n csúccsal és m éllel rendelkező gráf esetén. Az analízis javítható a bemeneti gráf feszítőfáinak $t(G)$ számának polinom faktoráig. A gyakorlatban branch and bound („korlátozás és elágazás”) stratégiák és az izomorfizmusok kiküszöbölése segítségével néhány rekurzív hívás kiküszöbölhető. A futásidő a csúcspár kiválasztásának heurisztikáján múlik.

Hiperkocka-módszer

Létezik a gráfszínezéseknek egy természetes, térgeometriai megfeleltetése, amennyiben úgy tekintjük, hogy az összes csúcshoz hozzárendelt természetes számok tulajdonképpen az egész számok térrácsában egy vektort alkotnak. Mivel az egyforma színű $i$ és $j$ csúcsok úgy tekinthetők, hogy a színezési vektor $i$-edik és $j$-edik koordinátája megegyezik, ezért a gráf egyes éleihez $\{x\in R^{d}:x_{i}=x_{j}\}$ alakban leírható hipersík rendelhető. Az adott gráfhoz tartozó ilyen hipersíkok gyűjteményét a gráf elrendezésének (graphic arrangement) nevezik. A gráf jó színezései azok a rácspontok, amik elkerülik a tiltott hipersíkokat. Ha csak $k$ szín áll rendelkezésre, a rácspontok a $[0,k]^{n}$ hiperkockán belül találhatók. Ebben a kontextusban a kromatikus polinom azokat a $[0,k]$-kockán belüli rácspontokat számolja, amik elkerülik a gráf elrendezését.

Számítási bonyolultság

Adott gráf 3-színezéseinek meghatározása a #P-teljes problémák alapesete, tehát a kromatikus polinom együtthatóinak kiszámítása is #P-nehéz. Ugyanígy a $P(G,3)$ kiszámítása adott G-re #P-teljes. Másrészről, a $k=0,1,2$ esetekre könnyű kiszámolni $P(G,k)$-t, tehát a hozzájuk tartozó problémák polinom időben megoldhatók. A $k>3$ egészekre a probléma #P-nehéz, ami a $k=3$ esethez hasonlóan látható be. Valójában bizonyított tény, hogy $P(G,x)$ #P-nehéz minden x-re (a negatív egészeket és még a komplex számokat is ideértve), kivéve a három „könnyű pontot”. Így a #P-nehézség perspektíváját tekintve a kromatikus polinom kiszámításának bonyolultsága teljesen tisztázott.

A

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

kifejtésben az $a_{n}$ együtthatója mindig 1, és az együtthatók számos egyéb tulajdonsága ismert. Ez felveti a kérdést, hogy talán az együtthatók egy részét könnyű lehet kiszámítani. Ennek ellenére a rögzített r-re és adott G gráfra az a_r kiszámítása továbbra is #P-nehéz.

Nem ismerünk a $P(G,x)$ kiszámítására közelítő algoritmust semmilyen x-re, a három könnyű pontot kivéve. A $k=3,4,\dots$ egészekre az az eldöntési probléma, hogy adott gráf k-színezhető-e, NP-nehéz. Az ilyen problémák nem approximálhatók semmilyen multiplikatív faktorral korlátos hibájú valószínűségi algoritmus felhasználásával, hacsak nem NP = RP, mivel bármely multiplikatív approximáció megkülönböztetné a 0 és 1 értékeket, ezzel gyakorlatilag az eldöntési verziót korlátos hibájú valószínűségi polinom időben megoldva. Ez gyakorlatilag kizárja az FPRAS (teljesen polinom idejű randomizált approximációs séma) létezésének lehetőségét. Más pontokon komplikáltabb érvelésre van szükség, a kérdés aktív kutatások fókuszában áll. A 2008-as állapot szerint nincs ismert FPRAS a $P(G,x)$ kiszámítására bármely x > 2 helyen, hacsaknem NP = RP igaz.

Fordítás

• Ez a szócikk részben vagy egészben a Chromatic polynomial című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

• Biggs, N. (1993), Algebraic Graph Theory, Cambridge University Press, ISBN 0-521-45897-8
• Birkhoff, G. D. & Lewis, D. C. (1946), Chromatic Polynomials, pp. 356–451, <https://pdfs.semanticscholar.org/85e7/47e7d2041822d43deb3c3f038029e11df07d.pdf>. Hozzáférés ideje: 2018-04-16 Archiválva 2018. április 17-i dátummal a Wayback Machine-ben
• Brown, Jason I. (1998), On the Roots of Chromatic Polynomials, vol. B 72, pp. 251–256, <https://pdfs.semanticscholar.org/1219/4902a26c75b8732695a4f514a9c07d8167ab.pdf>. Hozzáférés ideje: 2018-04-16 Archiválva 2018. április 17-i dátummal a Wayback Machine-ben
• Chao, C.-Y. & Whitehead, E. G. (1978), "On chromatic equivalence of graphs", Theory and Applications of Graphs, vol. 642, Lecture Notes in Mathematics, Springer, pp. 121–131, ISBN 978-3-540-08666-6
• Dong, F. M.; Koh, K. M. & Teo, K. L. (2005), Chromatic polynomials and chromaticity of graphs, World Scientific Publishing Company, ISBN 981-256-317-2
• Giménez, O.; Hliněný, P. & Noy, M. (2005), "Computing the Tutte polynomial on graphs of bounded clique-width", Proc. 31st Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2005), vol. 3787, Lecture Notes in Computer Science, Springer-Verlag, pp. 59–68, DOI 10.1007/11604686_6
• Goldberg, L.A. & Jerrum, M. (2008), "Inapproximability of the Tutte polynomial", Information and Computation 206 (7): 908, DOI 10.1016/j.ic.2008.04.003
• Helme-Guizon, Laure & Rong, Yongwu (2005), "A categorification of the chromatic polynomial", Algebraic & Geometric Topology 5 (4): 1365–1388, DOI 10.2140/agt.2005.5.1365
• Huh, J. (2012), Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs, arXiv:1008.4749v3
• Jackson, B. (1993), "A Zero-Free Interval for Chromatic Polynomials of Graphs", Combinatorics, Probability and Computing 2: 325–336, DOI 10.1017/S0963548300000705
• Jaeger, F.; Vertigan, D. L. & Welsh, D. J. A. (1990), "On the computational complexity of the Jones and Tutte polynomials", Mathematical Proceedings of the Cambridge Philosophical Society 108: 35–53, DOI 10.1017/S0305004100068936
• Linial, N. (1986), "Hard enumeration problems in geometry and combinatorics", SIAM J. Algebraic Discrete Methods 7 (2): 331–335, DOI 10.1137/0607036
• Makowsky, J. A.; Rotics, U. & Averbouch, I. et al. (2006), "Computing graph polynomials on graphs of bounded clique-width", Proc. 32nd Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2006), vol. 4271, Lecture Notes in Computer Science, Springer-Verlag, pp. 191–204, DOI 10.1007/11917496_18
• Naor, J.; Naor, M. & Schaffer, A. (1987), "Fast parallel algorithms for chordal graphs", Proc. 19th ACM Symp. Theory of Computing (STOC '87), pp. 355–364, DOI 10.1145/28395.28433.
• Oxley, J. G. & Welsh, D. J. A. (2002), "Chromatic, flow and reliability polynomials: The complexity of their coefficients.", Combinatorics, Probability and Computing 11 (4): 403–426
• Pemmaraju, S. & Skiena, S. (2003), Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, Cambridge University Press, section 7.4.2, ISBN 0-521-80686-0
• Sekine, K.; Imai, H. & Tani, S. (1995), "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, pp. 224–233
• Sokal, A. D. (2004), "Chromatic Roots are Dense in the Whole Complex Plane", Combinatorics, Probability and Computing 13 (2): 221–261, DOI 10.1017/S0963548303006023
• Stanley, R. P. (1973), "Acyclic orientations of graphs", Discrete Math. 5 (2): 171–178, DOI 10.1016/0012-365X(73)90108-8
• Voloshin, Vitaly I. (2002), Coloring Mixed Hypergraphs: Theory, Algorithms and Applications., American Mathematical Society, ISBN 0-8218-2812-6
• Wilf, H. S. (1986), Algorithms and Complexity, Prentice–Hall, ISBN 0-13-021973-8
• Woodall, D. R. (1992), "A zero-free interval for chromatic polynomials", Discrete Math. 101: 333–341

További információk

• Weisstein, Eric W.: Chromatic polynomial (angol nyelven). Wolfram MathWorld
• PlanetMath Chromatic polynomial Archiválva 2008. augusztus 20-i dátummal a Wayback Machine-ben
• Code for computing Tutte, Chromatic and Flow Polynomials by Gary Haggard, David J. Pearce and Gordon Royle: [2] Archiválva 2012. december 20-i dátummal az Archive.is-en