Una scuola deve fissare le date degli esami scritti. Due esami non possono stare nello stesso giorno se c'è almeno uno studente iscritto a entrambi. Qual è il numero minimo di giorni necessari? Chi organizza una rete radio deve assegnare le frequenze ai trasmettitori in modo che due trasmettitori vicini non interferiscano. Un compilatore deve decidere quali variabili mettere negli stessi registri del processore.
Tre problemi lontani tra loro, con un'unica struttura: la colorazione dei grafi.
Il problema
Si costruisce un grafo in cui i vertici sono gli oggetti da sistemare (esami, trasmettitori, variabili) e gli archi collegano le coppie in conflitto. Una colorazione assegna a ogni vertice un colore in modo che due vertici adiacenti abbiano colori diversi. I colori rappresentano le risorse: giorni, frequenze, registri.
Il minimo numero di colori sufficiente si chiama numero cromatico, indicato con χ(G). Minimizzare i colori significa minimizzare le risorse.
Qualche caso noto:
- un grafo senza archi ha χ = 1;
- un grafo bipartito con almeno un arco ha χ = 2, e verificarlo è facile con una visita in ampiezza;
- un ciclo con un numero dispari di vertici richiede 3 colori;
- un grafo completo con n vertici, dove tutti sono in conflitto con tutti, richiede n colori.
Perché è difficile
Decidere se un grafo si può colorare con 3 colori è un problema NP-completo: non si conoscono algoritmi che lo risolvano in tempo polinomiale nel caso generale. Per grafi di qualche decina di vertici una ricerca esaustiva ben potata funziona; per centinaia o migliaia di vertici, come negli orari reali, si usano euristiche che danno buone colorazioni senza garanzia di ottimo.
Un limite inferiore utile: se il grafo contiene una cricca di k vertici, tutti in conflitto tra loro, servono almeno k colori. Se un'euristica trova una colorazione con lo stesso numero di colori della cricca più grande trovata, si ha la certezza di aver raggiunto l'ottimo.
L'algoritmo greedy
Il metodo più semplice: si prendono i vertici in un certo ordine e a ciascuno si assegna il colore più basso non usato dai vicini già colorati.
def colora_greedy(adj, ordine):
colore = {}
for v in ordine:
usati = {colore[u] for u in adj[v] if u in colore}
c = 0
while c in usati:
c += 1
colore[v] = c
return colore
Garantisce al massimo Δ + 1 colori, dove Δ è il grado massimo del grafo. Il risultato, però, dipende moltissimo dall'ordine. Esistono grafi bipartiti, colorabili con 2 colori, per cui un ordine sfortunato porta il greedy a usarne quanti sono i vertici di un lato.
Due ordini che funzionano meglio di quello casuale:
- grado decrescente (Welsh-Powell): prima i vertici con più conflitti, che sono i più difficili da sistemare;
- ordine di degenerazione: si toglie ripetutamente il vertice di grado minimo e si colora nell'ordine inverso; garantisce al massimo d + 1 colori, dove d è la degenerazione, spesso molto più piccola di Δ.
DSatur
L'euristica DSatur (grado di saturazione) sceglie dinamicamente il prossimo vertice da colorare: quello con il maggior numero di colori diversi già presenti tra i vicini. A parità, quello con più vicini non colorati. L'idea è affrontare per primi i vertici più vincolati, prima che restino senza opzioni.
Su molti grafi pratici DSatur dà risultati nettamente migliori del greedy semplice, con un costo comunque contenuto. Sui grafi bipartiti trova sempre una colorazione con 2 colori.
Esempio: orario degli esami
| Esame | In conflitto con |
|---|---|
| Analisi | Fisica, Chimica, Informatica |
| Fisica | Analisi, Chimica |
| Chimica | Analisi, Fisica, Biologia |
| Informatica | Analisi |
| Biologia | Chimica |
Analisi, Fisica e Chimica formano una cricca di tre vertici: servono almeno 3 giorni. DSatur colora Analisi (giorno 1), poi Chimica (giorno 2), poi Fisica (giorno 3), poi Biologia (giorno 1, non è in conflitto con Analisi) e Informatica (giorno 2). Tre giorni bastano, e la cricca dimostra che non si può fare meglio.
Applicazioni oltre gli orari
- Allocazione dei registri: il compilatore costruisce un grafo di interferenza tra variabili vive nello stesso momento; con k registri disponibili cerca una k-colorazione e, se non la trova, sposta alcune variabili in memoria.
- Frequenze: trasmettitori vicini ricevono canali diversi; nella pratica le reti Wi-Fi in un edificio si pianificano proprio così, con i pochi canali non sovrapposti come colori.
- Mappe: colorare le regioni di una cartina in modo che regioni confinanti abbiano colori diversi. Per le mappe piane il teorema dei quattro colori garantisce che quattro bastano sempre.
- Sudoku: ogni cella è un vertice, collegato alle celle della stessa riga, colonna e riquadro; risolverlo significa completare una 9-colorazione a partire da quella parziale data.
Varianti utili nella realtà
Gli orari veri raramente sono una colorazione pura. Ci sono aule con capienza limitata, docenti non disponibili in certi giorni, preferenze per distanziare esami dello stesso corso. In genere si parte da una buona colorazione e la si migliora con una ricerca locale o con metaeuristiche, trattando i vincoli rigidi come obbligatori e quelli morbidi come penalità da minimizzare.
In sintesi
- La colorazione assegna risorse a oggetti in conflitto: giorni, frequenze, registri.
- Trovare il numero cromatico è difficile in generale, ma le cricche danno limiti inferiori.
- Il greedy è semplice e veloce; il suo risultato dipende fortemente dall'ordine dei vertici.
- DSatur colora per primi i vertici più vincolati e dà spesso risultati migliori.
- Negli orari reali la colorazione è il punto di partenza, rifinito con vincoli e penalità.
