Kromatikus polinom

A Wikipédiából, a szabad enciklopédiából
Jump to navigation Jump to search
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: ; egy él és egy független csúcs: ; a 3-út: ; a 3-klikk: .

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.

Történet[szerkesztés]

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 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 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]

Definíció[szerkesztés]

A 3 csúcsú gráfok k színnel történő összes jó színezése -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 , , vagy amit a szócikk a továbbiakban használni fog.

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

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ő:

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:

Példák[szerkesztés]

Néhány gráf kromatikus polinomja
háromszög
teljes gráf
n csúcsú fagráf
körgráf
Petersen-gráf

Tulajdonságok[szerkesztés]

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

A

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

Az 1 helyen kiértékelt derivált, előjel erejéig megegyezik a kromatikus invariánssal.

Ha a G gráfnak n csúcsa, m éle és között c összefüggő komponense van, akkor

  • A együtthatói nullák.
  • A együtthatói nem nullák.
  • A együtthatója -ben 1.
  • A együtthatója -ben .
  • 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]

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

Kromatikus ekvivalencia[szerkesztés]

A három gráf, melynek kromatikus polinomja .

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:

ezen belül az,

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

Kromatikus egyediség[szerkesztés]

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

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

Kromatikus gyökök[szerkesztés]

Egy kromatikus polinom gyöke (vagy zérushelye), azaz a „kromatikus gyök” olyan x érték, ahol . 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 , sem a intervallumban[5], Jackson pedig az 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 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 , , intervallumokban és hogy , az eredeti sejtést azonban nem sikerült igazolniuk. Woodall javított eredménye szerint[7] nincs zérushely a intervallumban sem, mely utóbbi szám az oktaéder kromatikus polinomjának () 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.[9]

Tutte egy eredménye összeköti -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 -hez: Ha egy gömb síkháromszögelése, akkor

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.[10]

Kategorifikáció[szerkesztés]

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

Algoritmusok[szerkesztés]

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

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

Az első probléma általánosabb, hiszen ha ismerjük 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[szerkesztés]

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

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

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

amennyiben és nem szomszédosak és az é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.[14] 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.[15] 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:

egy n csúccsal és m éllel rendelkező gráf esetén.[16] Az analízis javítható a bemeneti gráf feszítőfáinak számának polinom faktoráig.[17] 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[szerkesztés]

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

Számítási bonyolultság[szerkesztés]

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

kifejtésben az 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 ar kiszámítása továbbra is #P-nehéz.[19]

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

Fordítás[szerkeszté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.

Jegyzetek[szerkesztés]

További információk[szerkesztés]