Kromatiskt polynom

Ett kromatiskt polynom är ett polynom som studeras i algebraisk grafteori och som representerar antalet färger i en graf som en funktion av antalet färger. Ursprungligen definierad av George Birkhoff som ett försök att lösa fyrfärgsproblemet . Generaliserad och systematiskt studerad av Hassler Whitney , generaliserade Tutt det kromatiska polynomet till Tutt-polynomet genom att relatera det till Potts modell statistisk fysik .

Historik

George Birkhoff introducerade det kromatiska polynomet 1912 och definierade det endast för plana grafer i ett försök att bevisa fyrafärgssatsen . Om betecknar antalet korrekta färgningar av grafen G med k färger, så skulle man kunna bevisa fyrafärgssatsen genom att visa att för alla plana grafer G . På detta sätt hoppades han kunna använda kraften hos kalkyl och algebra för att studera polynomens rötter för att studera det kombinatoriska färgproblemet. $P(G,k)$ $P(G,4)>0$

Hassler Whitney generaliserade Birkhoff-polynomet från det plana fallet till allmänna grafer 1932. 1968 tog Reed upp frågan om vilka polynom som är kromatiska polynom för vissa grafer (problemet förblir öppet), och introducerade begreppet kromatiskt ekvivalenta grafer. För närvarande är kromatiska polynom de centrala föremålen för algebraisk grafteori [1] .

Definition

Det kromatiska polynomet i en graf G räknar antalet korrekta vertexfärgningar . Ett polynom betecknas vanligtvis som , , eller . Den senare notationen kommer att användas i resten av artikeln. $P_{G}(k)$ $\chi _{G}(k)$ $\pi _{G}(k)$ $P(G,k)$

Till exempel kan en bana med 3 hörn inte färgas med 0 färger eller 1 färg. Med 2 färger kan grafen färgläggas på två sätt. Med hjälp av 3 färger kan grafen färgläggas på 12 sätt. $P_{3}$

Tillgängliga färger $k$	0	ett	2	3
Antal målarbok $P(P_{3},k)$	0	0	2	12

Givet en graf G med n hörn definieras ett kromatiskt polynom som ett unikt interpolerande polynom med högst n grad som passerar genom punkterna

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

Om grafen G inte innehåller några hörn med slingor, är det kromatiska polynomet ett reducerat polynom med grad exakt n . I själva verket har vi för exemplet ovan

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

Ett kromatiskt polynom innehåller minst lika mycket information om färgbarheten hos grafen G som det kromatiska talet. Dessutom är det kromatiska talet det minsta positiva heltal för vilket det kromatiska polynomet inte försvinner,

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

Exempel

Kromatiska polynom för vissa grafer

Triangel $K_{3}$	$t(t-1)(t-2)$
Komplett graf $K_n$	$t(t-1)(t-2)\cdots (t-(n-1))$
Väg $P_{n}$	$t(t-1)^{{n-1}}$
Vilket träd som helst med n hörn	$t(t-1)^{{n-1}}$
Cykel $C_{n}$	$(t-1)^{n}+(-1)^{n}(t-1)$
Greve av Petersen	$t(t-1)(t-2)\left(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{ 2}+775t-352\höger)$

Egenskaper

För en fast graf G med n hörn är det kromatiska polynomet i själva verket ett polynom av grad n . Per definition ger beräkningen av polynomets värde antalet k -färgningar av grafen G för . Detsamma gäller för k > n . $P(G,t)$ $P(G,k)$ $k=0,1,\cdots ,n$

Uttryck

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

ger antalet acykliska orienteringar av grafen G [2] .

Värdet på derivatan av polynomet vid punkt 1 är lika, upp till ett tecken, med den kromatiska invarianten . $P'(G,1)$ $\theta (G)$

Om en graf G har n hörn, m kanter och c komponenter , då $G_{1},\cdots ,G_{c}$

Koefficienterna för är lika med noll. ${\displaystyle t^{0},\cdots ,t^{c-1))$
Koefficienterna för är alla icke-noll. ${\displaystyle t^{c},\cdots ,t^{n))$
Koefficienten vid är lika med 1. $t^{n}$ $P(G,t)$
Koefficienten vid är lika med . $t^{n-1}$ $P(G,t)$ $-m$
Koefficienterna för ett kromatiskt polynom är teckenalternerande.
De absoluta värdena av koefficienterna för ett kromatiskt polynom bildar en logaritmiskt konkav sekvens [3] .
$P(G,t)=P(G_{1},t)P(G_{2},t)\cdots P(G_{c},t)$

En graf G med n hörn är ett träd om och endast om

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

Kromatisk ekvivalens

Två grafer sägs vara kromatiskt ekvivalenta om de har samma kromatiska polynom. Isomorfa grafer har samma kromatiska polynom, men icke-isomorfa grafer kan vara kromatiskt ekvivalenta. Till exempel, alla träd med n hörn har samma kromatiska polynom:

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

Särskilt,

(x-1)^{3}x

är ett kromatiskt polynom för både klo- och 4-vertexbanan .

Kromatisk unikhet

En graf är kromatiskt unik om den definieras av ett kromatiskt polynom upp till isomorfism. Med andra ord, om grafen G är kromatiskt unik, följer det att G och H är isomorfa. $P(G,t)=P(H,t)$

Alla cykler är kromatiskt unika [4] .

Kromatiska rötter

Roten (eller noll ) av ett kromatiskt polynom (kallad "kromatisk rot") är ett x -värde för vilket . Kromatiska rötter är väl studerade. Faktum är att Birkhoffs ursprungliga motiv för att introducera det kromatiska polynomet var att visa att det för plana grafer för x ≥ 4. Detta skulle bevisa fyrfärgssatsen . $P(G,x)=0$ $P(G,x)>0$

Ingen graf kan färgas med 0 färger, så 0 är alltid en kromatisk rot. Endast grafer utan kanter kan vara enfärgade, så 1 är den kromatiska roten av en graf med minst en kant. Å andra sidan, med undantag för dessa två fall, kan ingen graf ha ett reellt tal som sin kromatiska rot mindre än eller lika med 32/27 [5] . Tattas resultat relaterar det gyllene snittet till studiet av kromatiska rötter, vilket visar att kromatiska rötter finns mycket nära - om är en plan triangulering av en sfär, då $\phi$ $\phi ^{2}$ $G_{n}$

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

Medan den verkliga linjen alltså har stora bitar som inte innehåller några kromatiska rötter för någon graf, är varje punkt på det komplexa planet godtyckligt nära en kromatisk rot i den meningen att det finns en oändlig familj av grafer vars kromatiska rötter är täta på det komplexa planet plan [6] .

Kategorisering

Det kromatiska polynomet kategoriseras med hjälp av homologiteori, nära besläktad med Khovanovs homologi [7] .

Algoritmer

Kromatiskt polynom
Ingång	Graf G med n hörn.
Utgång	Odds $P(G,t)$
Arbetstimmar	$O(2^{n}n^{r})$ för någon konstant $r$
Komplexitet	#P är svårt
Minskad från	#3 SAT

#k-färgning
Ingång	Graf G med n hörn.
Utgång	$P(G,k)$
Arbetstimmar	Tillhör P för . för . Annat $k=0,1,2$ $O(1{,}6262^{n})$ $k=3$ $O(2^{n}n^{r})$ för någon konstant $r$
Komplexitet	#P är svårt än så länge $k=0,1,2$
Närrbarhet	Ingen FPRAS för $k>2$

Beräkningsproblem relaterade till kromatiska polynom

hitta ett kromatiskt polynom för en given graf G ; $P(G,t)$
beräkning vid en fast punkt k för en given graf G . $P(G,k)$

Det första problemet är mer generellt, eftersom vi, genom att känna till koefficienterna , kan beräkna värdet på polynomet när som helst i polynomtiden. Beräkningskomplexiteten för det andra problemet beror starkt på värdet av k . När k är ett naturligt tal, kan problemet ses som att beräkna antalet k -färgningar i en given graf. Till exempel inkluderar problemet att räkna 3-färgningar som ett kanoniskt problem för att studera räknekomplexitet. Denna uppgift är klar i klass #P . $P(G,t)$

Effektiva algoritmer

För vissa grundläggande klasser av grafer är explicita formler för kromatiska polynom kända. Detta gäller till exempel för träd och klick som visas i tabellen ovan.

Det finns kända polynomtidsalgoritmer för att beräkna det kromatiska polynomet för en bred klass av grafer, som inkluderar ackordsgrafer [8] och grafer med begränsad klickbredd [9] [10] . Den andra av dessa klasser inkluderar i sin tur kografer och grafer med avgränsad trädbredd , såsom ytterplanära grafer .

Det finns människor på Internet som försöker lösa problemet kollektivt, och de får hjälp av aktiva autonoma hjälpare, speciellt för höggradiga kromatiska polynom [11] .

Borttagning - sammandragning

Det rekursiva sättet att beräkna ett kromatiskt polynom är baserat på kantkontraktion - för ett par hörn , och grafen erhålls genom att slå samman två hörn och ta bort kanten mellan dem. Det kromatiska polynomet uppfyller det rekursiva förhållandet $u$ $v$ $g/uv$

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

där och är angränsande hörn och är en graf med den borttagna kanten . På motsvarande sätt, $u$ $v$ $G-uv$ $UV$

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

om och är inte intilliggande och är en graf med en extra kant . I den första formen stannar rekursionen vid uppsättningen tomma grafer. Dessa återkommande relationer kallas också för fundamentalreduktionssatsen [12] . Tutts fråga om vilka andra grafegenskaper som uppfyller samma återkommande relationer ledde till upptäckten av en tvåvariabel generalisering av det kromatiska polynomet, Tutts polynom . $u$ $v$ $G+uv$ $UV$

Uttrycken ger en rekursiv procedur som kallas borttagnings-kontraktionsalgoritmen , som är grunden för många graffärgningsalgoritmer. ChromaticPolynomial - funktionen i Mathematicas datoralgebrasystem använder den andra rekursiva formeln om grafen är tät, och den första om grafen är gles [13] . Den sämsta körtiden för båda formlerna uppfyller upprepningsrelationen för Fibonacci-tal , så att i värsta fall körs algoritmen i tid (upp till någon polynomfaktor)

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

på en graf med n hörn och m kanter [14] . Körtidsanalysen kan förbättras till en polynomfaktor av antalet spännande träd i ingångsgrafen [15] . I praktiken används en förgrening-och-bunden- strategi, tillsammans med isomorfisk grafsläppning , för att eliminera rekursiva anrop, och tiden beror på den heuristik som används för att välja ett vertexpar (för drop-pull). $t(G)$

Cube Method

Det finns ett naturligt geometriskt tillvägagångssätt för graffärgning, om du märker att när du tilldelar naturliga tal till varje vertex, är färgningen av grafer en vektor av ett heltalsgitter. Eftersom att tilldela två hörn och samma färg är ekvivalent med likheten mellan koordinater och i färgningsvektorn, kan varje kant associeras med ett hyperplan av formen . Uppsättningen av sådana hyperplan för en given graf kallas dess grafiska hyperplanskonfiguration . En korrekt graffärgning är en färgning vars vektor inte visas på det förbjudna planet. Begränsad av många färger faller gitterpunkterna in i en kub . I detta sammanhang räknar det kromatiska polynomet rutnätspunkterna i -kuben som inte faller in i den grafiska konfigurationen. $i$ $j$ $i$ $j$ $\{x\in R^{d}:x_{i}=x_{j}\}$ $k$ ${\displaystyle [0,k]^{n))$ $[0,k]$

Beräkningskomplexitet

Problemet med att beräkna antalet 3-färgningar av en given graf är ett kanoniskt exempel på ett #P -komplett problem, så problemet med att beräkna koefficienterna för ett kromatiskt polynom är #P-hårt. På liknande sätt är beräkningen för en given graf G #P-komplett. Å andra sidan är det lätt att beräkna för , så att motsvarande problem har polynom tidskomplexitet. För heltal är problemet #P-hard, vilket är etablerat på samma sätt som fallet . Det är faktiskt känt att det är #P-hårt för alla x (inklusive negativa heltal och till och med alla komplexa tal), förutom tre "primtalspunkter" [16] . Således är komplexiteten i att beräkna ett kromatiskt polynom helt förståeligt. $P(G,3)$ $k=0,1,2$ $P(G,k)$ $k>3$ $k=3$ $P(G,x)$

I ett polynom

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

koefficienten är alltid 1, och några andra egenskaper hos koefficienter är också kända. Detta väcker frågan om några koefficienter kan beräknas enklare. Problemet med att beräkna a r för ett fast r och en given graf G är dock #P-hårt [17] . $en$

Ingen ungefärlig beräkningsalgoritm är känd för något x , förutom tre enkla punkter. Vid heltalspunkter är det motsvarande lösbarhetsproblemet att avgöra om en given graf kan färgas med k färger NP-hårt . Sådana problem kan inte approximeras av någon faktor med en polynomisk probabilistisk algoritm med begränsat fel, förutom NP = RP, eftersom varje multiplikativ approximation skulle skilja mellan 0 och 1, vilket skulle vara en effektiv lösning på problemet med en polynomisk probabilistisk algoritm med begränsat fel i form av lösbarhetsproblemet . I synnerhet, under vissa antaganden, utesluter detta möjligheten av ett helt polynomiskt randomiserat approximationsschema (FPRAS) . För andra punkter behövs mer komplexa resonemang och frågan är i fokus för aktiv forskning. Från och med 2008 är det känt att det inte finns något FPRAS-schema för beräkning av någon x > 2, förutom NP = RP [18] . $P(G,x)$ $k=3,4,\dots$ $P(G,x)$

Anteckningar

↑ Biggs, 1993 , sid. Några kapitel.
↑ Stanley, 1973 .
↑ Va, 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 , sid. 370–374.
↑ Dong, Koh, Teo, 2005 .
↑ Pemmaraju, Skiena, 2003 .
↑ Wilf, 1986 .
↑ Sekine, Imai, Tani, 1995 .
↑ Jaeger, Vertigan och Welsh ( Jaeger, Vertigan, Welsh 1990 ), baserat på Linials blandning ( Linial 1986 ).
↑ Oxley, Welsh, 2002 .
↑ Goldberg, Jerrum, 2008 .

Litteratur

A. Yu. Evnin. Kromatiskt polynom av en graf i problem // Matematisk utbildning . - 2014. - Nr 4 (72) . - S. 9-15 . (ryska)
Biggs N. Algebraisk grafteori. - Cambridge University Press, 1993. - ISBN 0-521-45897-8 .
Hirokazu Shirado, Nicholas A. Christakis. Lokalt bullriga autonoma agenter förbättrar global mänsklig koordination i nätverksexperiment // Nature. - 2017. - T. 545 , nr. 7654 . — S. 370–374 . - doi : 10.1038/nature22332 .
Chao C.-Y., Whitehead EG Om kromatisk ekvivalens av grafer // Theory and Applications of Graphs. - Springer, 1978. - T. 642. - S. 121-131. — (Föreläsningsanteckningar i matematik). - ISBN 978-3-540-08666-6 .
Dong FM, Koh KM, Teo KL Kromatiska polynom och kromaticitet av grafer. - World Scientific Publishing Company, 2005. - ISBN 981-256-317-2 .
Giménez O., Hliněný P., Noy M. Beräknar Tutte-polynomet på grafer med begränsad klickbredd // Proc. 31st Int. worksh. Grafteoretiska begrepp i datavetenskap (WG 2005). - Springer-Verlag, 2005. - T. 3787. - S. 59–68. - doi : 10.1007/11604686_6 .
Goldberg LA, Jerrum M. Inapproximability of the Tutte polynomial // Information and Computation. - 2008. - T. 206 , nr. 7 . - S. 908 . - doi : 10.1016/j.ic.2008.04.003 .
Laure Helme-Guizon, Yongwu Rong. En kategorisering av det kromatiska polynomet // Algebraisk och geometrisk topologi. - 2005. - V. 5 , nr. 4 . - S. 1365-1388 . - doi : 10.2140/agt.2005.5.1365 .
Huh J. Milnor antal projektiva hyperytor och det kromatiska polynomet av grafer. — arXiv:1008.4749v3, 2012.
Jackson B. Ett nollfritt intervall för kromatiska polynom av grafer // Combinatorics, Probability and Computing. - 1993. - T. 2 . — S. 325–336 . - doi : 10.1017/S0963548300000705 .
Jaeger F., Vertigan DL, Welsh DJA Om beräkningskomplexiteten hos Jones och Tutte-polynomen // Mathematical Proceedings of the Cambridge Philosophical Society. - 1990. - T. 108 . — s. 35–53 . - doi : 10.1017/S0305004100068936 .
Linial N. Hårda uppräkningsproblem i geometri och kombinatorik // SIAM J. Algebraic Discrete Methods. - 1986. - T. 7 , nr. 2 . — S. 331–335 . - doi : 10.1137/0607036 .
Makowsky JA, Rotics U., Averbouch I., Godlin B. Beräkning av grafpolynom på grafer med begränsad klickbredd // Proc. 32:a Int. worksh. Grafteoretiska begrepp i datavetenskap (WG 2006). - Springer-Verlag, 2006. - T. 4271. - S. 191-204. — (Föreläsningsanteckningar i datavetenskap). - doi : 10.1007/11917496_18 .
Naor J., Naor M., Schaffer A. Snabba parallella algoritmer för ackordsgrafer // Proc. 19:e ACM Symp. Theory of Computing (STOC '87). - 1987. - S. 355-364. doi : 10.1145 / 28395.28433 .
Oxley JG, Welsh DJA Kromatiska, flödes- och tillförlitlighetspolynom: komplexiteten hos deras koefficienter. // Kombinatorik, sannolikhet och beräkning . - 2002. - T. 11 , nr. 4 . — S. 403–426 .
Pemmaraju S., Skiena S. avsnitt 7.4.2 // Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. - Cambridge University Press, 2003. - ISBN 0-521-80686-0 .
Sekine K., Imai H., Tani S. Computing the Tutte polynomial of a graph of moderat size // Algorithms and Computation, 6th International Symposium, Lecture Notes in Computer Science 1004. — Cairns, Australien, 4–6 december 1995: Springer, 1995, s. 224–233.
Sokal AD kromatiska rötter är täta i hela det komplexa planet // Combinatorics, Probability and Computing . - 2004. - T. 13 , nr. 2 . — S. 221–261 . - doi : 10.1017/S0963548303006023 .
Stanley RP Acykliska orienteringar av grafer // Skiva. Matematik. . - 1973. - V. 5 , nr. 2 . — S. 171–178 . - doi : 10.1016/0012-365X(73)90108-8 .
Vitaly I Voloshin. Färgläggning av blandade hypergrafer: teori, algoritmer och tillämpningar.. - American Mathematical Society, 2002. - ISBN 0-8218-2812-6 .
Wilf H.S. Algoritmer och komplexitet. - Prentice-Hall, 1986. - ISBN 0-13-021973-8 .

Länkar

Weisstein, Eric W. Chromatic polynomial (engelska) på Wolfram MathWorld- webbplatsen .
PlanetMath Kromatiskt polynom
Kod för beräkning av Tutte, Chromatic and Flow Polynomials av Gary Haggard, David J. Pearce och Gordon Royle: [1] (inte tillgänglig länk)