Топ-100
Indietro

ⓘ Polinomio cromatico. Il polinomio cromatico è un polinomio studiato nella teoria algebrica dei grafi, una branca della matematica. Esso conta il numero di color ..




Polinomio cromatico
                                     

ⓘ Polinomio cromatico

Il polinomio cromatico è un polinomio studiato nella teoria algebrica dei grafi, una branca della matematica. Esso conta il numero di colorazioni dei grafi come funzione del numero dei colori e fu definito originariamente da George David Birkhoff per affrontare il problema dei quattro colori. Fu generalizzato al polinomio di Tutte da H. Whitney e W. T. Tutte, legandolo al modello di Potts della fisica statistica.

                                     

1. Storia

George David Birkhoff introdusse il polinomio cromatico nel 1912, definendolo soltanto per i grafi planari, in un tentativo di dimostrare il teorema dei quattro colori. Se P G, k {\displaystyle PG,k} denota il numero di colorazioni esatte di G con k colori, allora si potrebbe enunciare il teorema dei quattro colori mostrando P G, 4 > 0 {\displaystyle PG,4> 0} per tutti i grafi planari G. In questo modo egli sperava di applicare i potenti strumenti dellanalisi e dellalgebra per lo studio delle radici dei polinomi al problema combinatorio delle colorazioni.

Hassler Whitney generalizzò il polinomio di Birkhoff dal caso planare ai grafi generali nel 1932. Nel 1968 Read chiese che polinomi siano i polinomi cromatici di un determinato grafo, una domanda che rimane aperta, e introdusse il concetto di grafi cromaticamente equivalenti. Oggi, i polinomi cromatici sono uno degli oggetti centrali della teoria algebrica dei grafi.

                                     

2. Definizione

Il polinomio cromatico di un grafo G conta il numero delle sue colorazioni esatte dei vertici. È denotato comunemente P G k {\displaystyle P_{G}k}, χ G k {\displaystyle \chi _{G}k}, π G k {\displaystyle \pi _{G}k}, e P G, k {\displaystyle PG,k} che è la notazione che useremo dora in avanti.

Per esempio, il grafo lineare P 3 {\displaystyle P_{3}} su 3 vertici non può essere colorato affatto con 0 o 1 colori. Con 2 colori, può essere colorato in 2 modi. Con 3 colori, può essere colorato in 12 modi.

Per un grafo G con n vertici, il polinomio cromatico è definito come lunico polinomio interpolante di grado al massimo n attraverso i punti

{ 0, P G, 0), 1, P G, 1), ⋯, n, P G, n) }. {\displaystyle \left\{0,PG,0),1,PG,1),\cdots,n,PG,n)\right\}.}

Se G non contiene alcun vertice con un autocappio, allora il polinomio cromatico è un polinomio monico di grado esattamente n. Infatti per lesempio di sopra abbiamo:

P 3, t = t − 1 2, P 3, 3 = 12. {\displaystyle PP_{3},t=tt-1^{2},\qquad PP_{3},3=12.}

Il polinomio cromatico include almeno altrettante informazioni sulla colorabilità di G del numero cromatico. In effetti, il numero cromatico è il più piccolo intero positivo che non sia una radice del polinomio cromatico,

χ G = min { k: P G, k > 0 }. {\displaystyle \chi G=\min\{k:PG,k> 0\}.}
                                     

3. Proprietà

Per G fisso su n vertici, il polinomio cromatico P G, t {\displaystyle PG,t} è in realtà un polinomio di grado n. Per definizione, stimare il polinomio cromatico in P G, k {\displaystyle PG,k} produce il numero di k -colorazioni di G per k = 0, 1, ⋯, n {\displaystyle k=0.1,\cdots,n}. Lo stesso vale per k > n.

Lespressione

− 1 | V G | P G, − 1 {\displaystyle -1^{|VG|}PG 1}

produce il numero di orientazioni acicliche di G.

La derivata stimata a 1, P ′ G, 1 {\displaystyle PG,1} uguaglia linvariante cromatica, θ G {\displaystyle \theta G}, fino al segno.

Se G ha n vertici, m spigoli e c componenti G 1, ⋯, G c {\displaystyle G_{1},\cdots,G_{c}}, allora

  • Il coefficiente di t n {\displaystyle t^{n}} in P G, t {\displaystyle PG,t} è 1.
  • I coefficienti di ogni polinomio cromatico presentano alternanza di segni.
  • Il coefficiente di t n − 1 {\displaystyle t^{n-1}} in P G, t {\displaystyle PG,t} è − m {\displaystyle -m}.
  • I valori assoluti dei coefficienti di ogni polinomio cromatico formano una sequenza logaritmicamente concava.
  • I coefficienti di t c, ⋯, t n {\displaystyle t^{c},\cdots,t^{n}} sono tutti diversi da zero.
  • P G, t = P G 1, t P G 2, t ⋯ P G c, t {\displaystyle \scriptstyle PG,t=PG_{1},tPG_{2},t\cdots PG_{c},t}
  • I coefficienti di t 0, ⋯, t c − 1 {\displaystyle t^{0},\cdots,t^{c-1}} sono zeri.

Un grafo G con n vertici è un albero se e solo se

P G, t = t − 1 n − 1. {\displaystyle PG,t=tt-1^{n-1}.}


                                     

3.1. Proprietà Equivalenza cromatica

Si dice che due grafi sono cromaticamente equivalenti se hanno lo stesso polinomio cromatico. I grafi isomorfi hanno lo stesso polinomio cromatico, ma i grafi non isomorfi possono essere cromaticamente equivalenti. Ad esempio, tutti gli alberi su n vertici hanno lo stesso polinomio cromatico:

x − 1 n − 1 x, {\displaystyle x-1^{n-1}x,}

in particolare,

x − 1 3 x {\displaystyle x-1^{3}x}

è il polinomio cromatico sia del grafo a stella che del grafo lineare su 4 vertici.

                                     

3.2. Proprietà Unicità cromatica

Un grafo è cromaticamente unico se è determinato dal suo polinomio cromatico, fino allisomorfismo. In altre parole, se G fosse cromaticamente unico, allora P G, t = P H, t {\displaystyle PG,t=PH,t} implicherebbe che G ed H sono isomorfi.

Tutti i grafi ciclo sono cromaticamente unici.

                                     

3.3. Proprietà Radici cromatiche

Una radice o zero di un polinomio cromatico, chiamata "radice cromatica", è un valore x dove P G, x = 0 {\displaystyle PG,x=0}. Le radici cromatidfhe sono state molto ben studiate, infatti, la motivazione originaria di Birkhoff per definire il polinomio cromatico era di mostrare che per i grafi planari, P G, x > 0 {\displaystyle PG,x> 0} per x ≥ 4. Ciò avrebbe condotto allenunciazione del teorema dei quattro colori.

Nessun grafo può essere 0-colorato, perciò 0 è sempre una radice cromatica. Solo i grafi senza vertici possono essere 1-colorati, così 1 è la radice cromatica per ogni grafo con almeno uno spigolo. Daltro canto, eccetto per questi due punti, nessun grafo può avere una radice cromatica in un numero reale minore di o uguale a 32/27. Un risultato di Tutte connette la sezione aurea ϕ {\displaystyle \phi } con lo studio delle radici cromatiche, mostrando che le radici cromatiche esistono molto vicino a ϕ 2 {\displaystyle \phi ^{2}}: Se G n {\displaystyle G_{n}} è una triangolazione planare di una sfera allora

P G n, ϕ ≤ ϕ 5 − n. {\displaystyle PG_{n},\phi\leq \phi ^{5-n}.}

Anche se la linea reale così ha grandi parti che non contengono radici cromatiche per qualsiasi grafo, ogni punto nel piano complesso è arbitrariamente vicino a una radice cromatica nel senso che esiste una famiglia infinita di grafi le cui radici cromatiche sono dense nel piano planare.



                                     

4. Algoritmi

I problemi computazionali associati al polinomio cromatico includono

  • trovare il polinomio cromatico P G, t {\displaystyle PG,t} di un dato grafo G ;
  • stimare P G, k {\displaystyle PG,k} in un punto fisso k per G dato.

Il primo problema è più generale perché se conosciamo i coefficienti di P G, t {\displaystyle PG,t} potremmo stimarlo in qualsiasi punto nel tempo polinomiale perché il grado è n. La difficoltà del secondo tipo di problema dipende fortemente dal valore di k ed è stato intensamente studiato nella complessità computazionale. Quando k è un numero naturale, questo problema è visto normalmente come computo del numero di k -colorazioni di un dato grafo. Ad esempio, questo comprende il problema #3-colorazione di contare il numero delle 3-colorazioni, un problema canonico nello studio della complessità del calcolo, completo per la classe di calcolo #P.

                                     

4.1. Algoritmi Algoritmi efficienti

Per alcune classi di grafi basilari, le formule chiuse per il polinomio cromatico sono conosciute. Ad esempio questo è vero per gli alberi e per le cricche, come elencati nella tabella di sopra.

Gli algoritmi del tempo polinomiale sono noti per il computo del polinomio cromatico per le classi di grafi più ampie, compresi i grafi cordali e i grafi con unampiezza della cricca limitata. Questultima classe comprende i cografi e i grafi con unampiezza dellalbero limitata, come i grafi planari esterni.

                                     

4.2. Algoritmi Cancellazione-contrazione

Un modo di computare il polinomio cromatico si basa sulla contrazione sugli spigoli: per una coppia di vertici u {\displaystyle u} e v {\displaystyle v} il grafo G / u v {\displaystyle G/uv} si ottiene fondendo i due vertici e rimuovendo qualsiasi spigolo tra di essi. Allora il polinomio cromatico soddisfa la relazione di ricorrenza

P G, k = P G − u v, k − P G / u v, k {\displaystyle PG,k=PG-uv,k-PG/uv,k}

dove u {\displaystyle u} e v {\displaystyle v} sono vertici adiacenti e G − u v {\displaystyle G-uv} è il grafo con lo spigolo u v {\displaystyle uv} rimosso. Equivalentemente,

P G, k = P G + u v, k + P G / u v, k {\displaystyle PG,k=PG+uv,k+PG/uv,k}

se u {\displaystyle u} e v {\displaystyle v} non sono adiacenti e G + u v {\displaystyle G+uv} è il grafo con lo spigolo u v {\displaystyle uv} aggiunto. Nella prima forma, la ricorrenza termina in una collezione di grafi vuoti. Nella seconda forma, essa termina in una collezione di grafi completi. Queste ricorrenze sono chiamate anche Teorema delle riduzioni fondamentali. La curiosità di Tutte su quali altre proprietà dei grafi soddisfacessero tali ricorrenze lo portarono a scoprire una generalizzazione bivariata del polinomio cromatico, il polinomio di Tutte.

Le espressioni danno origine a una procedura ricorsiva, chiamata algoritmo di cancellazione-contrazione, che forma la base di molti algoritmi per la colorazione dei grafi. La funzione ChromaticPolynomial nel sistema di algebra informatica Mathematica usa la seconda ricorrenza se il grafo è denso, e la prima ricorrenza se il grafo è sparso. Il peggior tempo di esecuzione di entrambe le formule soddisfa la stessa relazione di ricorrenza della successione di Fibonacci, così, nel caso peggiore, lalgoritmo si svolge nel tempo entro un fattore polinomiale di

ϕ n + m = 1 + 5 2 n + m ∈ O 1.62 n + m, {\displaystyle \phi ^{n+m}=\left{\frac {1+{\sqrt {5}}}{2}}\right^{n+m}\in O\left1.62^{n+m}\right,}

su un grafo con n vertici ed m spigoli. Lanalisi può essere migliorata entro un fattore polinomiale del numero t G {\displaystyle tG} degli alberi ricoprenti del grafo in entrata. In pratica, si impiegano le strategie branch and bound e la reiezione dellisomorfismo dei grafi per evitare alcune chiamate ricorsive, e il tempo di esecuzione dipende dalleuristica usata per cogliere la coppia di vertici.

                                     

4.3. Algoritmi Complessità computazionale

Il problema di computare il numero di 3-colorazioni di un dato grafo è un esempio canonico di un problema #P-completo, perciò il problema di computare i coefficienti del polinomio cromatico è #P-difficile. Similmente, stimare P G, 3 {\displaystyle PG,3} per un dato G è #P-completo. Daltro canto, per k = 0, 1, 2 {\displaystyle k=0.1.2} è facile computare P G, k {\displaystyle PG,k}, perciò i problemi corrispondenti sono computabili in tempo polinomiale. Per gli interi k > 3 {\displaystyle k> 3} il problema è #P-difficile, che è enunciato simile al caso k = 3 {\displaystyle k=3}. Infatti, è noto che P G, x {\displaystyle PG,x} è #P-difficile per tutti gli x inclusi gli interi negativi e perfino tutti i numeri complessi eccetto per i tre "punti facili". Così, dalla prospettiva della #P-difficoltà, si comprende completamente la complessità di computare il polinomio cromatico.

Nellespansione

P G, t = a 1 t + a 2 t 2 + ⋯ + a n t n, {\displaystyle PG,t=a_{1}t+a_{2}t^{2}+\dots +a_{n}t^{n},}

il coefficiente a n {\displaystyle a_{n}} è sempre uguale a 1, e sono note parecchie altre proprietà dei coefficienti. Questo solleva la domanda se alcuni di questi coefficienti siano facili da computare. Tuttavia il problema computazionale di computare a r per un r fisso e un dato grafo G è #P-difficile.

Non si conoscono algoritmi di approssimazione per computare P G, x {\displaystyle PG,x} per qualsiasi x eccetto per i tre punti facili. Ai punti interi k = 3, 4, … {\displaystyle k=3.4,\dots }, il corrispondente problema di decisione di decidere se un dato grafo possa essere k -colorato è NP-difficile. Tali problemi non possono essere approssimati a qualsiasi fattore moltiplicativo da un algoritmo probabilistico a errore limitato a meno che NP = RP, perché qualsiasi approssimazione moltiplicativa distinguerebbe i valori 0 e 1, risolvendo efficacemente la versione della decisione nel tempo polinomiale probabilistico con errore limitato. In particolare, in base alla stessa assunzione, questo esclude la possibilità di uno schema di approssimazione randomizzato in tempo pienamente polinomiale fully polynomial time randomised approximation scheme, FPRAS. Per altri punti, sono necessari argomenti più complicati, e la questione è al centro di ricerche attive. Fino al 2008, non vi era un FPRAS noto per computare P G, x {\displaystyle PG,x} per qualsiasi x > 2, a meno che non valesse NP = RP.