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.

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 ${\displaystyle 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 ${\displaystyle 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.^[1]

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

Tekintsük a három csúcsú ${\displaystyle 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 ${\displaystyle k}$	0	1	2	3
Színezések száma ${\displaystyle 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:

${\displaystyle \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ő:

${\displaystyle 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:

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

Néhány gráf kromatikus polinomja

${\displaystyle K_{3}}$ háromszög	${\displaystyle t(t-1)(t-2)}$
${\displaystyle K_{n}}$ teljes gráf	${\displaystyle t(t-1)(t-2)\cdots (t-(n-1))}$
n csúcsú fagráf	${\displaystyle t(t-1)^{n-1}}$
${\displaystyle C_{n}}$ körgráf	${\displaystyle (t-1)^{n}+(-1)^{n}(t-1)}$
Petersen-gráf	${\displaystyle 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.

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

A

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

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

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

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

• A ${\displaystyle t^{0},\cdots ,t^{c-1}}$ együtthatói nullák.
• A ${\displaystyle t^{c},\cdots ,t^{n}}$ együtthatói nem nullák, speciálisan ${\displaystyle t^{n}}$ együtthatója 1.
• A ${\displaystyle t^{n}}$ együtthatója ${\displaystyle P(G,t)}$-ben 1.
• A ${\displaystyle t^{n-1}}$ együtthatója ${\displaystyle P(G,t)}$-ben ${\displaystyle -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.^[3]
• ${\displaystyle \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

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

Egy gráf egyértelműen színezhető, ha minimális számú színnel színezve a színosztályok egyértelműen meghatározottak. Egy gráf pontosan akkor egyértelműen k-színezhető, ha ${\displaystyle P(G,k)=k!}$ és ${\displaystyle P(G,k-1)=0.}$

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:

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

ezen belül az,

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

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

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

Az összes körgráf kromatikusan egyedi.^[4]

Egy kromatikus polinom gyöke (vagy zérushelye), azaz a „kromatikus gyök” olyan x érték, ahol ${\displaystyle 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 sem negatív, sem 0 és 1 közti gyöke,^[5] Jackson pedig az ${\displaystyle (1,{\frac {32}{27}}\sim 1,185)}$ intervallumot zárta ki, melynek felső határa éles.^[6]

Birkhoff eredeti célja a kromatikus polinom bevezetésével az volt, hogy síkbarajzolható gráfok esetében igazolja az ${\displaystyle 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 az 1-en és a 0-n kívül a ${\displaystyle [-\infty ,2)}$ és ${\displaystyle [5,\infty )}$ intervallumokban, továbbá ${\displaystyle P(G,4)\neq 0}$, az eredeti sejtést azonban nem sikerült igazolniuk. Woodall javított eredménye szerint^[7] nincs zérushely a ${\displaystyle (2,\sim 2,546602)}$ intervallumban sem, mely utóbbi szám az oktaéder kromatikus polinomjának (${\displaystyle x^{3}-9x^{2}+29x-32=0}$) valós gyöke.^[8]

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.^[6]

Tutte egy eredménye összeköti ${\displaystyle \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 ${\displaystyle \phi ^{2}}$-hez: Ha ${\displaystyle G_{n}}$ egy gömb síkháromszögelése, akkor

${\displaystyle 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.^[9]

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

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

• adott G gráf ${\displaystyle P(G,t)}$ kromatikus polinomjának megkeresése;
• adott G gráf ${\displaystyle 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 ${\displaystyle 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.

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^[11] és a korlátos klikkszélességű gráfok.^[12] 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.

A kromatikus polinom kiszámításának rekurzív módja az élösszehúzáson alapul: az ${\displaystyle u}$ és ${\displaystyle v}$ csúcspár esetén a ${\displaystyle 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:

${\displaystyle P(G,k)=P(G-uv,k)-P(G/uv,k),}$

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

${\displaystyle P(G,k)=P(G+uv,k)+P(G/uv,k),}$

amennyiben ${\displaystyle u}$ és ${\displaystyle v}$ nem szomszédosak és ${\displaystyle G+uv}$ az ${\displaystyle 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.^[13] 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.^[14] 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:

${\displaystyle \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.^[15] Az analízis javítható a bemeneti gráf feszítőfáinak ${\displaystyle t(G)}$ számának polinom faktoráig.^[16] 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.

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ű ${\displaystyle i}$ és ${\displaystyle j}$ csúcsok úgy tekinthetők, hogy a színezési vektor ${\displaystyle i}$-edik és ${\displaystyle j}$-edik koordinátája megegyezik, ezért a gráf egyes éleihez ${\displaystyle \{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 ${\displaystyle k}$ szín áll rendelkezésre, a rácspontok a ${\displaystyle [0,k]^{n}}$ hiperkockán belül találhatók. Ebben a kontextusban a kromatikus polinom azokat a ${\displaystyle [0,k]}$-kockán belüli rácspontokat számolja, amik elkerülik a gráf elrendezését.

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 ${\displaystyle P(G,3)}$ kiszámítása adott G-re #P-teljes. Másrészről, a ${\displaystyle k=0,1,2}$ esetekre könnyű kiszámolni ${\displaystyle P(G,k)}$-t, tehát a hozzájuk tartozó problémák polinom időben megoldhatók. A ${\displaystyle k>3}$ egészekre a probléma #P-nehéz, ami a ${\displaystyle k=3}$ esethez hasonlóan látható be. Valójában bizonyított tény, hogy ${\displaystyle 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”.^[17] Í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

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

kifejtésben az ${\displaystyle 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.^[18]

Nem ismerünk a ${\displaystyle P(G,x)}$ kiszámítására közelítő algoritmust semmilyen x-re, a három könnyű pontot kivéve. A ${\displaystyle 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 ${\displaystyle P(G,x)}$ kiszámítására bármely x > 2 helyen, hacsaknem NP = RP igaz.^[19]

• 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.

• 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