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 .
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í.
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] .
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.
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.
Dostupné barvy | 0 | jeden | 2 | 3 |
Počet omalovánek | 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.
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
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í,
Trojúhelník | |
Kompletní graf | |
Cesta | |
Libovolný strom s n vrcholy | |
Cyklus | |
hrabě z Petersenu |
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 .
Výraz
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 .
Pokud má graf G n vrcholů, m hran a c komponent , pak
Graf G s n vrcholy je strom právě tehdy a jen tehdy
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:
Zejména,
je chromatický polynom pro dráp i 4-vrcholovou cestu .
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í.
Všechny cykly jsou chromaticky jedinečné [4] .
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 .
Žá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
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] .
Chromatický polynom je kategorizován pomocí teorie homologie, která je blízce příbuzná Khovanovově homologii [7] .
Chromatický polynom | |
---|---|
Vchod | Graf G s n vrcholy. |
Výstup | Kurzy |
Pracovní doba | za nějakou stálou |
Složitost | #P je těžké |
Sníženo z | #3SAT |
#k-barvení | |
---|---|
Vchod | Graf G s n vrcholy. |
Výstup | |
Pracovní doba |
Patří do P pro . pro . v opačném případě za nějakou stálou |
Složitost |
#P je zatím těžké |
Přibližnost | Žádné FPRAS pro |
Výpočtové problémy související s chromatickými polynomy
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 .
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] .
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
,kde a jsou sousední vrcholy a je graf s odstraněnou hranou . ekvivalentně,
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 .
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)
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).
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.
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á.
V polynomu
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] .
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] .