Coloriamo?
Tiziana Calamoneri
Roma, 21 Settembre 2009
Elenco dei coautori
(in questa ricerca)
• Italiani:
–
–
–
–
–
–
• Stranieri:
S. Caminiti
I. Finocchi
E. Fusco
R. Petreschi
B. Sinaimeri
P. Vocca (U. di Lecce)
–
–
–
–
S. Olariu (Old Dominion Univ.)
G. Fertin (Univ. de Nantes)
A. Pelc (Univ. du Québec)
R.B. Tan (Utrecht & Oklahoma Univ.)
Un problema di colorazione (1)
• Dato un grafo G, colorare tutti i suoi nodi in
modo che nodi adiacenti ricevano colori
diversi e minimizzando il numero di colori.
• Teorema dei quattro colori (cong. 1852 Guthrie studente
di
De
Morgan;
pubbl.
1879
Cayley)
data una carta geografica politica, sono
sufficienti quattro colori per colorare ogni
regione facendo in modo che regioni
adiacenti non abbiano lo stesso colore.
Due regioni sono dette adiacenti se hanno
almeno un segmento di confine in
comune.
Un problema di colorazione (2)
Un problema di colorazione (3)
• regione della mappa  nodo;
• due regioni corrispondenti sono confinanti 
arco.
• Teorema dei quattro colori: I nodi di ciascun
grafo planare possono essere colorati
utilizzando al massimo quattro colori, in
modo tale che due nodi adiacenti non
ricevano mai lo stesso colore.
Altre applicazioni (1)
• Problemi di scheduling
In un orario dei corsi, corsi tenuti dallo
stesso docente o previsti per lo stesso
anno non possono avere lo stesso
orario.
Minimo numero di ore.
• Corsi  nodi
• Restrizioni che forzano orari diversi  archi
• Orari  colori
Altre applicazioni (2)
• Assegnazione di frequenze alle stazioni radio di una
rete
senza
fili
Ogni stazione trasmette con una frequenza.
Minimizzare il numero di frequenze evitando collisioni…
Messaggi trasmessi con frequenze “simili” nella stessa
area (collisioni dirette) o più messaggi in ricezione sulla
stessa frequenza vengono persi (collisioni nascoste).
Altre applicazioni (3)
• Grafo dei conflitti:
• antenne  nodi
• possibili comunicazioni (e quindi conflitti)  archi
• frequenze  colori
• La semplice colorazione dei
garantisce un risultato corretto.
nodi
• Generalizzazione del problema…
non
L(2,1)-etichettatura (1)
• Una L(2,1)-etichettatura di un grafo G è una funzione
che assegna colori dall’insieme 0, … , ai nodi di G
tale che nodi a distanza 2 abbiano colori diversi e nodi
adiacenti abbiano colori a distanza 2.
• Problema della L(2,1)-etichettatura: minimizzare 
0
2
4
0
2 …
0
2
4
4
2
0
0
3
=4
2
1
4
L(2,1)-etichettatura (2)
• Il problema della L(2,1)-etichettatura è, in
generale, NP-arduo.
• Diverse vie di ricerca:
– trovare classi di grafi per cui il problema si risolve
polinomialmente (ad es. grafi completi, alberi, griglie, ecc.)
– trovare algoritmi di approssimazione per le altre classi
– trovare limitazioni superiori ed inferiori al numero di colori
necessari
L(2,1)-etichettatura (3)
9
2
8
• Osservazione: +1
0
7
6
3
4
5
• Esistono grafi che richiedono (
(ad es. il grafo di incidenza di un piano proiettivo
(n) di ordine n)
L(2,1)-etichettatura (4)

•





+2Griggs & Yeh ‘92)
Congettura: per ogni grafo
+2-4 (Jonas ‘93)
+ Chang & Kuo ‘96
+ Kràl’ & Skrekovski ‘03
+ Gonçalves ‘08
 Havet, Reed and Sereni ‘08
circa 1069!!
se >0, ma 0 è
L(h,k)-etichettatura
h k
L(2,1)-etichettatura
• Applicazioni:
– problemi di assegnazione di canali, dove il canale
è definito come frequenza, tempo, o codice di
controllo, equivalente ad L(h,k) per valori
opportuni di h e k
– assegnazione di canali in reti ottiche basate sui
clusters equivalente a L(0,1) o L(1,1) a seconda
del fatto che i clusters contengano uno o più nodi
– assegnazione di un codice di controllo nelle reti
radio per evitare collisioni nascoste, equivalente a
L(0,1)
L(2,1)-etichettatura orientata (1)
• Generalizzazione della L(2,1)-etichettatura.
• Una L(2,1)-etichettatura orientata di un grafo orientato G è
una funzione che assegna colori dall’insieme 0, … , ai
nodi di G tale che nodi a distanza 2 abbiano colori a
distanza 1 e nodi adiacenti abbiano colori a distanza 2.
• Problema della L(2,1)-etichettatura orientata: minimizzare

• N.B. il minimo valore di  può essere molto diverso che nel
caso non orientato. Ad es. alberi…
L(2,1)-etichettatura orientata (2)
• Per alberi non orientati,   , ed è linearmente
decidibile qual è il valore esatto (Chang & Kuo ‘96,
Hasunama et al. 2008)
• Per alberi orientati,   (Chang & Liaw ‘03)
0
2 2 2
4 4
4 4
0 0
0
Conclusioni (1)
Nella vita reale ci sono tanti problemi che
possono essere modellati come un problema
di colorazione.
Allora…
Conclusioni (2)
… coloriamo!
Altre applicazioni (2)
• Allocazione
di
registri
Le (molte) variabili in uso vanno assegnate
ad un numero (limitato) di registri. Quando
una variabile non è più usata, il suo registro
può essere riallocato. Le variabili sono in
conflitto se una è usata sia prima che dopo
un’altra. Minimizzare il numero di variabili
non memorizzate in registri.
• Variabili  nodi
• Conflitti tra variabili  archi
• Registri  colori
Un problema di colorazione (3)
• È immediato trovare mappe per le quali tre
soli colori non sono sufficienti.
• Non è eccessivamente difficile dimostrare
che bastano al più cinque colori.
• Per dimostrare che siano strettamente
necessari almeno quattro colori:
•
•
•
•
•
1879: Alfred Kempe. Prima dim.
1880: Peter Tait. Dim. alternativa
1890: Percy Heawood. Errore in Kempe
1891: Julius Petersen. Errore in Tait
1977: Kenneth Appel e Wolfgang Haken: dim.
L(h,k)-etichettatura (1)
• Generalizzazione della L(2,1)-etichettatura.
• Una L(h,k)-etichettatura di un grafo G è una funzione che
assegna colori dall’insieme 0, … , ai nodi di G tale che
nodi a distanza 2 abbiano colori a distanza k e nodi
adiacenti abbiano colori a distanza h.
• Problema della L(h,k)-etichettatura: minimizzare 