Kromatikus polinom

A kromatikus polinom az algebrai gráfelméletben vizsgált polinom , amely a gráf színeinek számát a színek számának függvényében ábrázolja. Eredetileg George Birkhoff a négy szín probléma megoldására tett kísérletként határozta meg . Hassler Whitney által általánosított és szisztematikusan tanulmányozott , Tutt a kromatikus polinomot a statisztikai fizika Potts-modelljéhez a Tutt -polinomra általánosította .

Történelem

George Birkhoff 1912-ben vezette be a kromatikus polinomot, és csak síkgráfokra definiálta, a négy szín tételének bizonyítására . Ha a G gráf helyes színezéseinek számát jelöli k színnel, akkor a négy szín tételt be lehetne bizonyítani úgy, hogy megmutatjuk, hogy minden G síkgráfra . Ily módon azt remélte, hogy a számítás és az algebra erejét felhasználhatja a polinomok gyökereinek tanulmányozására a kombinatorikus színezési probléma tanulmányozására. $P(G,k)$ $P(G,4)>0$

Hassler Whitney 1932-ben általánosította a Birkhoff-polinomot a sík esetről az általános gráfokra. 1968-ban Reed felvetette a kérdést, hogy egyes gráfoknál mely polinomok kromatikus polinomok (a probléma továbbra is nyitott), és bevezette a kromatikusan ekvivalens gráfok fogalmát. Jelenleg a kromatikus polinomok az algebrai gráfelmélet központi tárgyai [1] .

Definíció

A G gráf kromatikus polinomja a helyes csúcsszínezések számát számolja . A polinomokat általában , , vagy jelöléssel jelölik . Ez utóbbi jelölést használjuk a cikk további részében. $P_{G}(k)$ $\chi _{G}(k)$ $\pi _{G}(k)$ $P(G,k)$

Például egy 3 csúcsú útvonalat nem lehet színezni 0 vagy 1 színnel. 2 szín használatával a grafikon kétféleképpen színezhető. 3 szín használatával a grafikon 12 féleképpen színezhető. $P_{3}$

Elérhető színek $k$	0	egy	2	3
Színező oldalak száma $P(P_{3},k)$	0	0	2	12

Adott egy n csúcsú G gráf, a kromatikus polinom a pontokon áthaladó , legfeljebb n fokos egyedi interpoláló polinom.

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

Ha a G gráf nem tartalmaz ciklusos csúcsokat, akkor a kromatikus polinom egy pontosan n fokú redukált polinom . Valójában a fenti példa esetében megvan

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

Egy kromatikus polinom legalább annyi információt tartalmaz a G gráf színezhetőségéről, mint amennyit a kromatikus szám tartalmaz. Ezenkívül a kromatikus szám az a legkisebb pozitív egész szám, amelynél a kromatikus polinom nem tűnik el,

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

Példák

Kromatikus polinomok egyes gráfokhoz

Háromszög $K_{3}$	$t(t-1)(t-2)$
Teljes grafikon $K_n$	$t(t-1)(t-2)\cdots (t-(n-1))$
Pálya $P_{n}$	$t(t-1)^{{n-1}}$
Bármely fa , amelynek n csúcsa van	$t(t-1)^{{n-1}}$
Ciklus $C_{n}$	$(t-1)^{n}+(-1)^{n}(t-1)$
Petersen grófja	$t(t-1)(t-2)\left(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{ 2}+775t-352\jobbra)$

Tulajdonságok

Egy n csúcsú rögzített G gráf esetén a kromatikus polinom valójában egy n fokú polinom . Definíció szerint a polinom értékének kiszámítása megadja a G gráf k színezéseinek számát -re . Ugyanez igaz k > n -re is . $P(G,t)$ $P(G,k)$ $k=0,1,\cdots ,n$

Kifejezés

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

megadja a G gráf aciklikus orientációinak számát [2] .

A polinom deriváltjának értéke az 1. pontban egy előjelig egyenlő a kromatikus invariánssal . $P'(G,1)$ $\theta (G)$

Ha egy G gráfnak n csúcsa, m éle és c komponense van , akkor $G_{1},\cdots ,G_{c}$

Az együtthatók nullával egyenlőek. ${\displaystyle t^{0},\cdots ,t^{c-1))$
Az együtthatók mindegyike nem nulla. ${\displaystyle t^{c},\cdots ,t^{n))$
Az at együttható egyenlő 1-gyel. $t^{n}$ $P(G,t)$
A at együttható egyenlő . $t^{n-1}$ $P(G,t)$ $-m$
Bármely kromatikus polinom együtthatói előjel-alternatívak.
Bármely kromatikus polinom együtthatóinak abszolút értékei logaritmikusan konkáv sorozatot alkotnak [3] .
$P(G,t)=P(G_{1},t)P(G_{2},t)\cdots P(G_{c},t)$

Egy n csúcsú G gráf akkor és csak akkor fa

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

Kromatikus ekvivalencia

Két gráfot kromatikusan egyenértékűnek mondunk, ha azonos kromatikus polinomokkal rendelkeznek. Az izomorf gráfok kromatikus polinomjai azonosak, de a nem izomorf gráfok kromatikusan egyenértékűek lehetnek. Például minden n csúcsú fának ugyanaz a kromatikus polinomja:

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

Különösen,

{\megjelenítési stílus (x-1)^{3}x}

egy kromatikus polinom mind a karom , mind a 4 csúcsú útvonal számára .

Kromatikus egyediség

Egy gráf kromatikusan egyedi, ha egy kromatikus polinom határozza meg egészen izomorfizmusig. Más szóval, ha a G gráf kromatikusan egyedi, akkor ebből az következik, hogy G és H izomorf. $P(G,t)=P(H,t)$

Minden ciklus kromatikusan egyedi [4] .

Kromatikus gyökerek

Egy kromatikus polinom gyöke (vagy nulla ) (ezt "kromatikus gyökérnek" nevezik) egy x -érték , amelyre . A kromatikus gyökereket jól tanulmányozták. Valójában Birkhoff eredeti motivációja a kromatikus polinom bevezetésére az volt, hogy bemutassa, hogy síkgráfok esetén x ≥ 4. Ez bizonyítaná a négyszín tételt . $P(G,x)=0$ $P(G,x)>0$

Egy gráfot sem lehet színezni 0 színnel, így a 0 mindig kromatikus gyök. Csak az él nélküli gráfok lehetnek egyszínűek, így 1 bármely legalább egy éllel rendelkező gráf kromatikus gyöke. Másrészt e két eset kivételével egyetlen gráfnak sem lehet 32/27-nél kisebb vagy egyenlő valós szám a kromatikus gyöke [5] . Tatta eredménye az aranymetszést a kromatikus gyökök tanulmányozásával hozza összefüggésbe, megmutatva, hogy a kromatikus gyökök nagyon közel léteznek - ha egy gömb síkbeli háromszögelése, akkor $\phi$ $\phi ^{2}$ $G_{n}$

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

Míg így a valódi egyenesnek nagy darabjai vannak, amelyek egyetlen gráfhoz sem tartalmaznak kromatikus gyököket, a komplex sík bármely pontja tetszőlegesen közel van egy kromatikus gyökhöz abban az értelemben, hogy létezik egy végtelen gráfcsalád, amelynek kromatikus gyökei sűrűek a komplex síkon. sík [6] .

Kategorizálás

A kromatikus polinomot a homológiaelmélet segítségével kategorizálják , amely szorosan kapcsolódik Khovanov homológiájához [7] .

Algoritmusok

Kromatikus polinom
Bejárat	n csúcsú G gráf .
Kijárat	Esély $P(G,t)$
Munkaórák	$O(2^{n}n^{r})$ valamilyen állandónak $r$
Bonyolultság	#P nehéz
Csökkentett től	#3SAT

#k-színezés
Bejárat	n csúcsú G gráf .
Kijárat	$P(G,k)$
Munkaórák	P -hez tartozik a számára . számára . Másképp $k=0,1,2$ $O(1{,}6262^{n})$ $k=3$ $O(2^{n}n^{r})$ valamilyen állandónak $r$
Bonyolultság	#P eddig nehéz $k=0,1,2$
Megközelíthetőség	Nincs FPRAS ehhez $k>2$

Kromatikus polinomokkal kapcsolatos számítási problémák

kromatikus polinom keresése adott G gráfhoz ; $P(G,t)$
számítás egy fix pontban egy adott G gráfhoz . $P(G,k)$

Az első probléma általánosabb, hiszen az együtthatók ismeretében a polinom értékét a polinomidő bármely pontján ki tudjuk számítani. A második probléma számítási bonyolultsága erősen függ k értékétől . Ha k természetes szám, akkor a feladat úgy is felfogható, mint egy adott gráf k színezéseinek számának kiszámítása. Például a probléma magában foglalja a 3 színezések kanonikus problémaként való megszámlálását a számolás bonyolultságának tanulmányozására. Ez a feladat a #P osztályban befejeződött . $P(G,t)$

Hatékony algoritmusok

A gráfok néhány alapvető osztályához ismertek a kromatikus polinomok explicit képletei. Ez például igaz a fákra és a klikkekre, amint az a fenti táblázatban látható.

Ismertek polinomiális idő algoritmusok a kromatikus polinom kiszámítására a gráfok széles osztályára, beleértve az akkordgráfokat [8] és a korlátozott klikk szélességű gráfokat [9] [10] . A második osztályba tartoznak a kográfok és a korlátozott faszélességű gráfok , például a külső síkbeli gráfok .

Az interneten vannak olyanok, akik kollektíven próbálják megoldani a problémát, és aktív autonóm segítők segítik őket, különösen a magas fokú kromatikus polinomoknál [11] .

Eltávolítás - összehúzódás

A kromatikus polinom kiszámításának rekurzív módja az élösszehúzódáson alapul - egy csúcspár esetén , és a gráfot úgy kapjuk meg, hogy két csúcsot egyesítünk, és eltávolítjuk a köztük lévő élt. A kromatikus polinom kielégíti a rekurzív relációt $u$ $v$ $tulaj$

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

ahol és a szomszédos csúcsok és egy gráf az eltávolított éllel . Ezzel egyenértékűen $u$ $v$ $G-uv$ $UV$

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

ha és nem szomszédosak, és egy gráf hozzáadott éllel . Az első formában a rekurzió az üres gráfok halmazánál megáll. Ezeket az ismétlődő összefüggéseket alapvető redukciós tételnek is nevezik [12] . Tutt azon kérdése , hogy milyen más gráftulajdonságok elégítik ki ugyanazokat az ismétlődési relációkat, a kromatikus polinom kétváltozós általánosításának, a Tutt -polinomnak a felfedezéséhez vezetett . $u$ $v$ $G+uv$ $UV$

A kifejezések egy rekurzív eljárást adnak, amelyet eltávolítás-összehúzó algoritmusnak neveznek , amely számos gráfszínező algoritmus alapja. A Mathematica számítógépes algebrarendszerben a ChromaticPolynomial függvény a második rekurzív képletet használja, ha a gráf sűrű, és az elsőt, ha a gráf ritka [13] . Mindkét képlet legrosszabb futási ideje kielégíti a Fibonacci-számok ismétlődési relációját , így a legrosszabb esetben az algoritmus időben fut (valamilyen polinomiális tényezőig)

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

n csúcsú és m élű gráfon [14] . A futási idő elemzés a bemeneti gráf feszítőfáinak számának polinomiális tényezőjére javítható [15] . A gyakorlatban a rekurzív hívások kiküszöbölésére egy elágazó és kötött stratégiát használnak az izomorf gráf eldobásával együtt , és az idő a csúcspár kiválasztásához használt heurisztikától függ (a drop-pull esetében). $t(G)$

Kocka módszer

A gráfszínezésnek létezik egy természetes geometriai megközelítése, ha észreveszi, hogy amikor minden csúcshoz természetes számokat rendelünk, a gráfok színezése egy egész rács vektora. Mivel két csúcs és azonos szín hozzárendelése ekvivalens a koordináták egyenlőségével és a színezővektorban, minden él társítható egy formájú hipersíkhoz . Az ilyen hipersíkok halmazát egy adott gráfhoz grafikus hipersík konfigurációjának nevezzük . A megfelelő gráfszínezés olyan színezés, amelynek vektora nem jelenik meg a tiltott síkon. A sok szín által korlátozva a rácspontok egy kockába esnek . Ebben az összefüggésben a kromatikus polinom azokat a rácspontokat számolja a -kockában, amelyek nem tartoznak a grafikus konfigurációba. $én$ $j$ $én$ $j$ $\{x\in R^{d}:x_{i}=x_{j}\}$ $k$ ${\displaystyle [0,k]^{n))$ $[0,k]$

Számítási összetettség

Egy adott gráf 3 színezéseinek számának kiszámítása egy #P -teljes probléma kanonikus példája, így a kromatikus polinom együtthatóinak kiszámítása #P-nehéz. Hasonlóképpen, egy adott G gráf számítása #P-teljes. Másrészt könnyen kiszámítható , így a megfelelő problémák polinomiális időbonyolultságúak. Az egész számok esetében a probléma #P-nehéz, amely az esethez hasonlóan állapítható meg . Valójában #P-nehéz minden x -re (beleértve a negatív egészeket és még az összes komplex számot is), kivéve három "prímpontot" [16] . Így a kromatikus polinom kiszámításának bonyolultsága teljesen érthető. $P(G,3)$ $k=0,1,2$ $P(G,k)$ $k>3$ $k=3$ $P(G,x)$

Polinomban

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

az együttható mindig 1, és az együtthatók egyéb tulajdonságai is ismertek. Ez felveti a kérdést, hogy egyes együtthatók kiszámíthatók-e egyszerűbben. Azonban az r kiszámítása fix r és adott G gráf esetén #P-nehéz [17] . $a_n$

Egyik x - re sem ismert hozzávetőleges számítási algoritmus , kivéve három egyszerű pontot. Egész pontoknál a megfelelő megoldhatósági probléma annak meghatározására, hogy egy adott gráf színezhető-e k színnel, NP-nehéz . Az ilyen problémák nem közelíthetők egyetlen tényezővel sem korlátozott hibapolinom valószínűségi algoritmussal, kivéve NP = RP, mivel bármilyen multiplikatív közelítés különbséget tesz 0 és 1 között, ami hatékony megoldás lenne a probléma megoldására korlátos hibapolinom valószínűségi algoritmussal. a megoldhatósági probléma formája . Ez különösen bizonyos feltételezések szerint kizárja egy teljesen polinomiális véletlenszerű közelítési séma (FPRAS) lehetőségét . Más pontokhoz összetettebb érvelésre van szükség, és a kérdés az aktív kutatás fókuszában van. 2008-tól ismert, hogy nincs FPRAS séma bármely x > 2 kiszámítására , kivéve NP = RP [18] . $P(G,x)$ $k=3,4,\pontok$ $P(G,x)$

Jegyzetek

↑ Biggs, 1993 , p. Néhány fejezet.
↑ Stanley, 1973 .
↑ Hú, 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 , p. 370–374.
↑ Dong, Koh, Teo, 2005 .
↑ Pemmaraju, Skiena, 2003 .
↑ Wilf, 1986 .
↑ Sekine, Imai, Tani, 1995 .
↑ Jaeger, Vertigan és Welsh ( Jaeger, Vertigan, Welsh 1990 ), Linial keverése alapján ( Linial 1986 ).
↑ Oxley, walesi, 2002 .
↑ Goldberg, Jerrum, 2008 .

Irodalom

A. Yu. Evnin. Gráf kromatikus polinomja feladatokban // Matematikai oktatás . - 2014. - 4. szám (72) . - S. 9-15 . (Orosz)
Biggs N. Algebrai gráfelmélet. - Cambridge University Press, 1993. - ISBN 0-521-45897-8 .
Hirokazu Shirado, Nicholas A. Christakis. A lokálisan zajos autonóm ágensek javítják a globális emberi koordinációt a hálózati kísérletekben // Nature. - 2017. - T. 545 , sz. 7654 . – S. 370–374 . - doi : 10.1038/nature22332 .
Chao C.-Y., Whitehead EG A gráfok kromatikus ekvivalenciájáról // Theory and Applications of Graphs. - Springer, 1978. - T. 642. - S. 121-131. — (Matematikai előadásjegyzetek). - ISBN 978-3-540-08666-6 .
Dong FM, Koh KM, Teo KL Kromatikus polinomok és gráfok kromatikussága. - 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. 31. Int. worksh. Gráfelméleti fogalmak a számítástechnikában (WG 2005). - Springer-Verlag, 2005. - T. 3787. - S. 59–68. - doi : 10.1007/11604686_6 .
Goldberg LA, Jerrum M. A Tutte-polinom közelíthetetlensége // Információ és számítás. - 2008. - T. 206 , sz. 7 . - S. 908 . - doi : 10.1016/j.ic.2008.04.003 .
Laure Helme-Guizon, Yongwu Rong. A kromatikus polinom kategorizálása // Algebrai és geometriai topológia. - 2005. - V. 5 , sz. 4 . - S. 1365-1388 . - doi : 10.2140/agt.2005.5.1365 .
Huh J. Milnor projektív hiperfelületek számai és gráfok kromatikus polinomja. — arXiv:1008.4749v3, 2012.
Jackson B. Nulla-mentes intervallum gráfok kromatikus polinomjaihoz // Kombinatorika, valószínűség és számítás. - 1993. - T. 2 . – S. 325–336 . - doi : 10.1017/S0963548300000705 .
Jaeger F., Vertigan DL, Welsh DJA A Jones és Tutte polinomok számítási bonyolultságáról // Mathematical Proceedings of the Cambridge Philosophical Society. - 1990. - T. 108 . – 35–53 . - doi : 10.1017/S0305004100068936 .
Linial N. Nehéz felsorolási problémák a geometriában és a kombinatorikában // SIAM J. Algebrai diszkrét módszerek. - 1986. - T. 7 , sz. 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. 32. Int. worksh. Gráfelméleti fogalmak a számítástechnikában (WG 2006). - Springer-Verlag, 2006. - T. 4271. - S. 191-204. — (Számítástechnikai előadásjegyzetek). - doi : 10.1007/11917496_18 .
Naor J., Naor M., Schaffer A. Gyors párhuzamos algoritmusok akkordgráfokhoz // Proc. 19. ACM Symp. A számítástechnika elmélete (STOC '87). - 1987. - S. 355-364. doi : 10.1145 / 28395.28433 .
Oxley JG, Welsh DJA Kromatikus, áramlási és megbízhatósági polinomok: együtthatóik összetettsége. // Kombinatorika, valószínűségszámítás és számítás . - 2002. - T. 11 , sz. 4 . – S. 403–426 .
Pemmaraju S., Skiena S. 7.4.2 szakasz // Számítási diszkrét matematika: Kombinatorika és gráfelmélet a Mathematicával. - Cambridge University Press, 2003. - ISBN 0-521-80686-0 .
Sekine K., Imai H., Tani S. A közepes méretű gráf Tutte-polinomjának kiszámítása // Algorithms and Computation, 6th International Symposium, Lecture Notes in Computer Science, 1004. – Cairns, Ausztrália, 1995. december 4–6. Springer, 1995, 224–233.
A Sokal AD kromatikus gyökerei sűrűek a teljes komplex síkon // Kombinatorika, valószínűség és számítás . - 2004. - T. 13 , sz. 2 . – S. 221–261 . - doi : 10.1017/S0963548303006023 .
Stanley R.P. Grafikonok aciklikus orientációi // Lemez. Math. . - 1973. - V. 5 , sz. 2 . – S. 171–178 . - doi : 10.1016/0012-365X(73)90108-8 .
Vitalij I. Volosin. Vegyes hipergráfok színezése: elmélet, algoritmusok és alkalmazások.. - American Mathematical Society, 2002. - ISBN 0-8218-2812-6 .
Wilf H.S. Algoritmusok és komplexitás. - Prentice-Hall, 1986. - ISBN 0-13-021973-8 .

Linkek

Weisstein, Eric W. Kromatikus polinom (angol) a Wolfram MathWorld webhelyen .
PlanetMath Kromatikus polinom
Gary Haggard, David J. Pearce és Gordon Royle Tutte, kromatikus és áramlási polinomjainak számítási kódja: [1] (nem elérhető link)