Colorazione golosa

Due colorazioni golose dello stesso grafo che usano ordini diversi dei vertici. L'esempio di destra generalizza ai grafi 2-colorabili con n vertici, dove l'algoritmo goloso spende $n/2$ colori.

Nello studio dei problemi della colorazione dei grafi in matematica e in informatica, una colorazione golosa (in inglese greedy coloring) è una colorazione dei vertici di un grafo formata da un algoritmo goloso (greedy algorithm) che considera i vertici del grafo in sequenza e assegna a ciascun vertice il suo primo colore disponibile. Le colorazioni golose in generale non usano il numero minimo di colori possibili; tuttavia, sono state usate in matematica come tecnica per dimostrare altri risultati sulle colorazioni e in informatica come euristica per trovare le colorazioni con pochi colori.

La golosità non è sempre buona

Un grafo a corona (un grafo bipartito completo K_n,n, con gli spigoli di un accoppiamento perfetto eliminato) è un caso particolarmente sbagliato di colorazione golosa: se l'ordinamento dei vertici pone due vertici consecutivamente ogni volta che appartengono a una delle coppie dell'accoppiamento eliminato, allora una colorazione golosa userà n colori, mentre il numero ottimale di colori per questo grafo è due. Esistono anche i grafi come quello con alta probabilità che un ordinamento dei vertici scelto a caso conduce a un numero di colori molto più grande del minimo Perciò, è di qualche importanza nella colorazione golosa scegliere l'ordinamento dei vertici con attenzione.

È NP-completo determinare, per un dato grafo G e un dato numero k, se esista un ordinamento dei vertici G che forzi l'algoritmo goloso a usare k o altri colori. In particolare, questo significa che è difficile trovare l'ordinamento peggiore per G.

Ordinamento ottimale

I vertici di qualsiasi grafo possono essere sempre ordinati in modo tale che l'algoritmo goloso produca una colorazione ottimale. Poiché, data una qualsiasi colorazione ottimale in cui il più piccolo insieme di colori è massimale, il secondo insieme di colori è massimale rispetto al primo insieme di colori, ecc., si possono ordinare i vertici in base ai loro colori. Allora quando si usa un algoritmo goloso con questo ordine, la colorazione risultante è automaticamente ottimale. In modo più forte, i grafi perfettamente ordinabili (che includono i grafi cordali, i grafi di comparabilità e i grafi ereditari per le distanze) hanno un ordinamento che è ottimale sia per il grafo stesso che per tutti i suoi sottografi indotti. Tuttavia, trovare un ordinamento ottimale per un grafo arbitrario è NP-difficile (perché potrebbe essere usato per risolvere il problema NP-completo della colorazione dei grafi), e anche riconoscere i grafi perfettamente ordinabili è NP-completo. Per questa ragione, sono state usate euristiche che tentano di ridurre il numero di colori pur non garantendo un numero ottimale di colori.

Strategie euristiche di ordinamento

Un ordinamento comunemente usato per la colorazione golosa è di scegliere un vertice v di grado minimo, ordinare i vertici rimanenti e poi porre v all'ultimo posto nell'ordinamento. Se ogni sottografo di un grafo G contiene un vertice al massimo di grado d, allora la colorazione golosa per questo ordinamento userà al massimo d + 1 colori. Il più piccolo di tali d è noto comunemente come degenerazione del grafo.

Per un grafo di grado massimo Δ, qualsiasi colorazione golosa userà al massimo Δ + 1 colori. Il teorema di Brooks afferma che con due eccezioni (cricche e cicli dispari) sono richiesti al massimo Δ colori. Una prova del teorema di Brooks implica di trovare un ordinamento dei vertici nel quale i primi due vertici sono adiacenti al vertice finale ma non adiacenti tra loro, e ogni vertice successivo ha almeno un vertice anteriore. Per un ordinamento con questa proprietà, l'algoritmo della colorazione golosa usa al massimo Δ colori.

Schemi alternativi di selezione dei colori

È possibile definire un algoritmo della colorazione golosa nel quale i vertici del grafo dato sono colorati in una data sequenza, ma nel quale il colore scelto per ogni vertice non è necessariamente il primo colore disponibile; le strategie alternative di selezione dei colori sono state studiate all'interno della cornice degli algoritmi in linea ("algoritmi online"). Nel problema della colorazione dei grafi in linea, i vertici di un grafo sono presentati uno alla volta in un ordine arbitrario a un algoritmo di colorazione; l'algoritmo deve scegliere un colore per ciascun vertice, basato soltanto sui colori dei e sulle adiacenze tra i vertici già processati. In questo contesto, si misura la qualità di una strategia di selezione di colori mediante il suo rapporto competitivo, il rapporto tra il numero di colori che esso usa e il numero ottimale di dolori per il grafo dato.

Se non sono date restrizioni aggiuntive al grafo, il rapporto competitivo ottimale è soltanto lievemente sublineare. Tuttavia, per i grafi d'intervallo, è possibile un rapporto competitivo costante, mentre per i grafi bipartiti e per i grafi sparsi si può ottenere un rapporto logaritmico. In realtà, per i grafi sparsi, la strategia normale di colorazione golosa di scegliere il primo colore disponibile ottiene questo rapporto competitivo, ed è possibile dimostrare un limite inferiore corrispondente sul rapporto competitivo di qualsiasi algoritmo di colorazione in linea.

Bibliografia

• Václav Chvátal, Perfectly orderable graphs, in Claude Berge e Václav Chvátal (a cura di), Topics in Perfect Graphs, Annals of Discrete Mathematics, vol. 21, Amsterdam, North-Holland, 1984, pp. 63–68. Come citata da Maffrah (2003).
• Sandy Irani, Coloring inductive graphs on-line, in Algorithmica, vol. 11, n. 1, 1994, pp. 53–72, DOI:10.1007/BF01294263.
• H. A. Kierstead e W. A. Trotter, An extremal problem in recursive combinatorics, in Congress. Numer., vol. 33, 1981, pp. 143–153. Come citato da Irani (1994).
• Luděk Kučera, The greedy coloring is a bad probabilistic algorithm, in Journal of Algorithms, vol. 12, n. 4, 1991, pp. 674–684, DOI:10.1016/0196-6774(91)90040-6.
• D. S. Johnson, Worst case behavior of graph coloring algorithms, in Proc. 5th Southeastern Conf. Combinatorics, Graph Theory and Computation, Winnipeg, Utilitas Mathematica, 1979, pp. 513–527. Come citato da Maffray (2003).
• L. Lovász, Three short proofs in graph theory, in Journal of Combinatorial Theory, Series B, vol. 19, n. 3, 1975, pp. 269–271, DOI:10.1016/0095-8956(75)90089-1.
• L. Lovász, M. E. Saks e W. A. Trotter, An on-line graph coloring algorithm with sublinear performance ratio, in Discrete Mathematics, vol. 75, 1–3, 1989, pp. 319–325, DOI:10.1016/0012-365X(89)90096-4.
• Frédéric Maffray, On the coloration of perfect graphs, in Bruce A. Reed e Cláudia L. Sales (a cura di), Recent Advances in Algorithms and Combinatorics, CMS Books in Mathematics, vol. 11, Springer-Verlag, 2003, pp. 65–84, DOI:10.1007/0-387-22444-0_3, ISBN 0-387-95434-1.
• Matthias Middendorf e Frank Pfeiffer, On the complexity of recognizing perfectly orderable graphs, in Discrete Mathematics, vol. 80, n. 3, 1990, pp. 327–333, DOI:10.1016/0012-365X(90)90251-C.
• Maciej M. Sysło, Sequential coloring versus Welsh-Powell bound, in Discrete Mathematics, vol. 74, 1–2, 1989, pp. 241–243, DOI:10.1016/0012-365X(89)90212-4.
• S. Vishwanathan, Randomized online graph coloring, in Proc. 31st IEEE Symp. Foundations of Computer Science (FOCS '90), vol. 2, 1990, pp. 464–469, DOI:10.1109/FSCS.1990.89567, ISBN 0-8186-2082-X.
• D. J. A Welsh e M. B. Powell, An upper bound for the chromatic number of a graph and its application to timetabling problems, in The Computer Journal, vol. 10, n. 1, 1967, pp. 85–86, DOI:10.1093/comjnl/10.1.85.
• Manouchehr Zaker, Results on the Grundy chromatic number of graphs, in Discrete Mathematics, vol. 306, 2–3, 2006, pp. 3166–3173, DOI:10.1016/j.disc.2005.06.044.