Teoria cromatica dei grafi



Il polinomio cromatico

Il polinomio cromatico è una funzione P(G,t) che, dato un grafo G e un numero t, determina il numero delle possibili colorazioni di G utilizzando t colori.
Per colorazione intendiamo uno dei possibili modi di assegnare un colore ad ogni vertice del grafo in maniera tale che due nodi adiacenti (cioè aventi un arco che li collega) non abbiano lo stesso colore.

Casi semplici


Grafo totalmente sconnesso
Posso colorare ogni vertice con t colori. Quindi:
p(G,t) = t n ;n = |V(G)|


Grafo totalmente connesso (completo) Kn
Si considera un vertice a caso (è possibile scegliere un vertice a caso perché tutti i vertici sono tra loro connessi, quindi non fa nessuna differenza una scelta casuale) che è possibile colorare con t colori; consideriamo poi un secondo vertice (connesso al primo necessariamente): questo può essere colorato con t-1 colori; scegliamo poi un terzo vertice: questo è certamente connesso al primo e al secondo, quindi è possibile colorarlo con t-2 colori; e così via. Quindi:
p(Kn,t) = t(t-1)(t-2)...(t-n+1)

Cammino di n vertici Pn
Il primo nodo può essere colorato in t modi diversi, il secondo vertice in t-1 modi, il terzo vertice in t-1 modi, e così via. Quindi:
p(Pn,t) = t(t-1) n-1


In generale il polinomio cromatico di un grafo G connesso con n nodi sarà:
Definizione di polinomio cromatico
Dove dn,k rappresentano il numero di sottoinsiemi di lati di ordine n-k non contenenti un circuito spezzato; le radici del polinomio invece rappresentano il numero di colori che non sono sufficienti per la colorazione del grafo.

Note:

Il grado del polinomio è pari al numero di nodi del grafo G.
Il coefficiente del termine di grado massimo è uno.
Il coefficiente di grado n-1, dove n è il massimo grado è uguale al numero di lati del grafo.
Se il polinomio ha radici razionali, queste sono intere
I coefficienti hanno segni alterni.
Il polinomio è senza buchi: i coefficienti sono nulli da un certo punto in poi, mai prima.
È un polinomio senza termine noto.
Il polinomio cromatico non identifica univocamente un grafo: grafi diversi possono avere lo stesso polinomio cromatico.
Vale sempre la proprietà: dn,k ( |E(G)| )
n-k

Alcune interpretazioni dei coefficienti del polinomio cromatico:

  1. Scrivendo il polinomio cromatico come combinazione lineare di fattoriali decrescenti:

    n
    p(G,t) = Ln,k · (t)k
    k=0

    dove (t)k = t(t-1)(t-2)...(t-k+1)

    Si ha che i coefficienti di tale combinazione sono il numero di partizioni G-compatibili degli n nodi di G in k blocchi.

    Nota: Una partizione G-compatibile è una partizione dei vertici del grafo tale che nessun blocco contiene vertici adiacenti.

  2. Scrivendo il polinomio cromatico come combinazione lineare di fattoriali crescenti:

    n
    p(G,t) = Ln,k · <t>k
    k=0

    dove <t>k = t(t+1)(t+2)...(t+k-1)

    si ha che i coefficienti di tale combinazione sono il numero di modi di mettere n palle in k scatole tenendo conto dell'ordine e delle adiacenze del grafo.
    (le palle i,j sono nella stessa scatola se (i,j) è un arco del grafo o se j>i).

  3. Scrivendo il polinomio cromatico come combinazione lineare di coefficienti binomiali:

    n
    p(G,t) = Ln,k · ( t )
    k=0 k

    si ha che i coefficienti di tale combinazione sono il numero di colorazioni esatte del grafo, cioè i modi di colorare i nodi del grafo con esattamente k colori.

  4. Scrivendo il polinomio cromatico nel seguente modo:

    n
    p(G,t) = Ln,k · t (t-1) k-1
    k=0

    si ha che Ln,k corrispondono al numero di alberi con K nodi ottenuti attraverso la Tutte decomposition di G.

Vediamo ora tre semplici metodi per la determinazione del polinomio cromatico di un grafo.

Metodo di William Tutte.

Sia G un grafo e supponiamo sia composto da due sottografi H,K la cui intersezione è una cricca di ordine n. Allora il polinomio cromatico di G è:
P(G,t)= P(H,t) P(K,t)
P(H K,t)

Metodo di decomposizione degli archi

Scelto un arco qualsiasi e E(G), si ha che il polinomio cromatico del grafo G è uguale alla differenza dei polinomi cromatici del grafo delezionato e contratto dell'arco scelto:

p(G,t)=p(G-e,t)-p(G\e,t)

Questo metodo fornisce il polinomio cromatico di G attraverso quello di grafi più semplici. Riapplicando il metodo a tali grafi si giunge inevitabilmente a grafi totalmente connessi.

Esempio di applicazione dei metodi visti: Tutte Decomposition Formula (TDF)

Sia G H = Km, allora il polinomio cromatico di H è: p(H,t) = (t-m) p(G,t)

Dimostrazione 1:
siano e1...em gli archi che connettono la m-cricca al vertice v.
p(H,t) = p(H - e1) - p(H \ e1) = p(H - e1) - p(G)
= p(H - e1 - e2) - p(H - e1 \ e2) - p(G) = p(H - e1 - e2) - p(G) - p(G)
= ... = t p(G) - m p(G) = (t - m) p(G)

Dimostrazione 2:
sia F = Km v.
p(H,t) = p(F,t) p(G,t) / p(Km) = (t)m+1 p(G,t) / (t)m = (t-m) p(G,t)

Espansione cromatica di un grafo.

L'espansione cromatica di un grafo G è data introducendo un nuovo vertice v e collegandolo a tutti i vertici di G.
Si ha: p(ECH(G);t) = t p(G;t-1).

Dimostrazione:
Supponiamo di conoscere il polinomio cromatico di G con t-1 colori. Se coloriamo il nuovo vertice v con uno dei t colori, il restante grafo è colorabile in tanti modi quanti sono dati da p(G;t-1).
Dato che il t-esimo colore per v è scelto a caso, devo moltiplicare p(G;t-1) per t.


Osservazione:

la Tutte Decomposition Formula consente di dare una definzione alternativa di grafo cordale.
Un grafo si dice cordale (triangolato, supersolubile) se è possibile dare un etichettatura ai suoi nodi (da 1 a n) in maniera tale da poter eseguire il seguente algoritmo (sequenza perfetta di eliminazione): si toglie il nodo n-esimo (il quale deve essere collegato ad una cricca Ka, di ordine a), poi si toglie il nodo (n-1)-esimo (anche esso collegato ad una cricca Kb, di ordine b), e così via fino ad ottenere un grafo che contiene un unico vertice.

(Si dice triangolato perché se il grafo è anche planare, tutte le sue regioni sono triangolari).

I grafi ottenuti ad ogni passo dell'algoritmo precedente costituiscono la cosiddetta sequenza persistente di grafi che andiamo a definire:

Una sequenza persistente di grafi è una famiglia di grafi cordali { Gn } dove

  1. Il numero di vertici di Gn è n, per ogni n=1,2,3...
  2. Gn contiene un vertice vn tale che il suo insieme di adiacenza è una cricca e Gn-1 = Gn - vn.

Dalla definizione così data di grafo cordale, segue che:

  1. Ad ogni grafo cordale è associata almeno una famiglia di polinomi persistenti: quella dei polinomi cromatici dei grafi ottenuti smaltellando il grafo originale secondo l'algoritmo visto.
    Più precisamente:
    Proposizione:
    Sia { Gn } una sequenza persistente di grafi e pn(t) il polinomio cromatico di Gn. Allora si ha che { pn(t) } è una famiglia persistente di polinomi, dove la sequenza delle radici associate a { pn(t) } è ottenibile dalla sequenza perfetta di eliminazione.

  2. Il polinomio cromatico dei grafi cordali ha radici intere: t (t-a) (t-b)...
  3. Esprimiamo il polinomio cromatico del cordale G in termini di fattoriali decrescenti.
    Chiamo partizione di tipo x una delle partizioni G-compatibili dei nodi di un grafo G tale che il nodo più alto (nell'ordinamento dato ai nodi di G) sta in un blocco da solo.

    Chiamo partizione di tipo y una delle partizioni G-compatibili dei nodi di un grafo G tale che il nodo più alto sta insieme ad uno o più nodi in un blocco.

    Dato che in questo caso i coefficienti del polinomio cromatico Ln,k sono le partizioni G-compatibili, indichiamo con xLn,k e yLn,k rispettivamente le partizioni di tipo x e di tipo y.

    Consideriamo ora la Master Recurrence:

    Ln,n-1 = Ln-1,n-2 + (rn-sn) · Ln-1,n-1

    Vale a dire che le partizioni G-compatibili di n nodi in n-1 blocchi si ottengono sommando alle partizioni G-compatibili di n-1 nodi in n-2 blocchi alcune delle partizioni G-compatibili di n-1 nodi in n-1 blocchi.

    Tuttavia le partizioni G-comp. di n nodi in n-1 blocchi sono facili da determinare:
    ogni blocco avrà dimensione 1, tranne uno che avrà dimensione 2.
    Ma allora per determinare le Ln,n-1 posso per prima cosa utilizzare le Ln-1,n-2 aggiungendo ad ogni partizione un blocco contenente un unico elemento (l'n-esimo); e queste sono proprio le xLn,n-1.
    Quindi si ha che esiste una corrispondenza biunivoca fra Ln-1,n-2 e xLn,n-1.

    A queste partizioni devo poi sommare alcune delle yLn,n-1: quelle in cui il nodo n-esimo si trova in compagnia in uno dei blocchi di Ln,n-1 (vedi rn · Ln-1,n-1), togliendo poi le partizioni non consentite (vedi - sn · Ln-1,n-1), che corrispondono alle partizioni in cui il nodo n-esimo si trova insieme ai nodi che nel grafo sono ad esso collegati (sn rappresenta infatti la radice utile per andare dall' n-1-esimo grafo all' n-esimo nella sequenza perfetta di eliminazione di G).

    Es.

    Sia n=5.

    L4,3: 13/2/4
    14/2/3
    24/1/3
    L5,4: 13/2/4/5
    14/2/3/5
    24/1/3/5
    -------- xL5,4
    15/2/3/4
    25/1/3/4
    -------- alcune partizioni fra le yL5,4
    Fra tutte le yL5,4 non abbiamo considerato 35/1/2/4 e 45/1/2/3, poiché nel grafo il nodo 5 è collegato ai nodi 3 e 4.

    Quanto detto si riassume in un teorema utile per determinare se un grafo è cordale:

    Teorema:

    Sia C un grafo cordale, con n-1 nodi,e G un grafo qualsiasi, con n nodi.
    Supponiamo che p(G,t)=(t-sn) · p(C,t) ; C contenuto in G-vn.
    Se:

    1) le x-partizioni G-compatibili in V(G) in n-1 blocchi sono in corrispondenza biunivoca con tutte le partizioni di V(C) in n-2 blocchi,

    oppure

    2) ci sono (n-1-sn) y-partizioni G-compatibili in V(G) in n-1 blocchi

    allora G è cordale.

    Nota:

    Un controesempio a questo teorema è dato dal grafo di Tutte T, che infatti non è un grafo cordale.

    L7,6 = L6,5 + (r7-s7) · L6,6 = L6,5 + (6-4) · L6,6 = 5

    Le x-partizioni G-compatibili in V(T), che ha 7 nodi, in 6 blocchi non sono in corrispondenza biunivoca con le partizioni dei 6 nodi del pre-Tutte (=grafo di Tutte che ha tutte le radici del grafo di Tutte meno l' n-esima, e quindi corrisponde al grafo di Tutte a cui è stato tolto il nodo 7 e gli archi che collegano il nodo 7 ai nodi 5 e 6 e gli archi che collegano i nodi 5 e 6 al nodo 4) in 5 blocchi.

    Quest'ultime infatti sono

    56/1/2/3/4
    46/1/2/3/5
    45/1/2/3/6

    e non basta aggiungere il nodo 7 in un blocco unico, ottenendo le partizioni

    56/1/2/3/4/7
    46/1/2/3/5/7
    45/1/2/3/6/7

    per avere le x-partizioni in V(T) in 6 blocchi, che si riducono alla sola 56/1/2/3/4/7.
    (questo perché la nuova radice sn = 5 non corrisponde al grado del nodo n, che è 2)

    Le y-partizioni G-compatibili in V(T), che ha 7 nodi, in 6 blocchi:

    17/2/3/4/5/6
    27/1/3/4/5/6
    37/1/2/4/5/6
    47/1/2/3/5/6
    56/1/2/3/4/7

    ma n-1-sn = 7-1-4 = 2 5

    Lemma:

    Siano C e G due grafi tali che C = G-v, con |V(G)| = n.
    Sia s = d(v) = grado di v.
    Se p(G,t) = (t-s) · p(C,t) allora il sottografo di G indotto dall'insieme di adiacenza di v è una cricca.

  4. Esprimiamo il polinomo cromatico del cordale Gn nel seguente modo:

    n
    p(G,t) = Ln,k · t (t-1) k-1
    k=0

    dove gli Ln,k sono gli alberi di ordine k estraibili da Gn.

    Essendo Gn un grafo cordale, questi alberi possono essere generati ricorsivamente usando il seguente procedimento:

    ricordiamo che per ogni arco e incidente su vn, Gn/e non è nient'altro che Gn-1.
    Sia f un altro arco incidente su vn; (Gn-e)/f coincide con Gn-1.
    Allora applicando la Tutte decomposition d(vn) volte si ha:

    p(Gn,t) = t · p(Gn-1,t) - d(vn) · p(Gn-1,t).

    Questa relazione suggerisce che per un dato k, il numero di alberi di ordine k estraibili da Gn possono essere ottenuti sommando al numero di alberi di ordine k-1 estraibili da Gn-1 il numero di alberi di ordine k estraibili da Gn-1 moltiplicato per d(vn)-1:

    p(Gn,t) = (t-1) · p(Gn-1,t) - (1 - d(vn)) · p(Gn-1,t).

    Da quanto detto scaturisce una nuova relazione di ricorrenza:

    Ln,k = Ln-1,k-1 + (1-d(vn)) · Ln-1,k.
    Così gli alberi di ordine k estraibili da Gn possono essere ottenuti facendo |1-d(vn)| copie degli alberi di ordine k estraibili da Gn-1 e attacando il nodo vn a tutti gli alberi di ordine k-1 estraibili da Gn-1.


Torna all'indice