Il numero cromatico dei vertici in un grafo
Il numero cromatico $ \chi(G) $ di un grafo G = (V, E) è il minimo numero di colori necessario per colorare i vertici del grafo in modo tale che nessun vertice adiacente abbia lo stesso colore.
In altre parole, è il numero minimo di colori che garantisce che non ci siano due vertici "vicini" con lo stesso colore.
Una colorazione del grafo G è una funzione f: V → C che assegna un colore ad ogni vertice.
Il numero cromatico di G si indica con χ(G) ed è il minimo numero di colori necessari per una colorazione valida del grafo.
Calcolare il numero cromatico di un grafo può rivelarsi un compito complesso dal punto di vista computazionale. Esistono vari algoritmi volti a stimare o identificare il numero cromatico. Tuttavia, per certi grafi, il problema della colorazione si classifica come NP-completo.
Esempio
Ad esempio, in questo grafo bipartito il numero cromatico del grafo è $ \chi(G) = 2 $.
Si può notare che nel grafo precedente nessun vertice è adiacente a un altro vertice con lo stesso colore.
Dove per "vertice adiacente" si intende un vertice direttamente collegato con uno spigolo a un altro vertice.
Nel contesto dei grafi bipartiti il numero cromatico dei vertici è sempre 2, poiché per definizione non esistono spigoli che collegano due vertici all'interno dello stesso insieme. Quindi, è possibile colorare tutti i vertici di un insieme indipendente con lo stesso colore.
Esempio 2
Per fare un esempio di un grafo che richiede 3 colori per essere colorato in modo che nessun due vertici adiacenti abbiano lo stesso colore, possiamo utilizzare il grafo del triangolo, noto anche come \(C_3\), un ciclo semplice su 3 vertici.
Questo è uno dei grafi più semplici tra quelli non bipartiti.
In questo caso il numero cromatico del grafo è $ \chi(G) = 3 $.
Per colorare questo grafo, abbiamo bisogno di 3 colori diversi perché ogni vertice è adiacente a tutti gli altri vertici.
L'assegnazione dei colori potrebbe essere: A-rosso, B-Blu, C-Verde. Questo assicura che ogni vertice adiacente abbia colori diversi.
Esempio 3
Questo è un altro esempio di grafo con numero cromatico $ \chi(G) = 3 $
Anche in questo caso tutti i vertici adiacenti hanno un colore diverso.
Quali sono le applicazioni del numero cromatico
Il numero cromatico ha diverse applicazioni in vari campi.
In cartografia è utilizzato per la colorazione di mappe in modo da evitare confusione tra regioni adiacenti.
Può essere impiegato anche nella teoria della computazione per l'analisi di algoritmi o nella risoluzione di problemi di scheduling e di assegnazione di risorse.
