Colorazione dei grafi — Numero cromatico e applicazioni

La colorazione dei grafi di solito significa colorazione dei vertici: assegnare un colore a ogni vertice in modo che vertici adiacenti non condividano lo stesso colore. Il più piccolo numero di colori che funziona è il numero cromatico, indicato con $\chi(G)$.

Se vuoi l'idea intuitiva in breve, i colori sono semplicemente etichette senza conflitti. Due vertici possono riutilizzare lo stesso colore esattamente quando non c'è un arco tra loro.

Definizione di colorazione dei grafi in un minuto

In una colorazione propria, ogni arco collega due vertici colorati in modo diverso. Questa è l'unica regola.

Quindi, se $\chi(G)=3$, due fatti sono veri allo stesso tempo:

• esiste una colorazione propria con $3$ colori
• non esiste una colorazione propria con soli $2$ colori

Per questo il numero cromatico è un minimo, non semplicemente il numero di colori che hai usato in un certo disegno.

A meno che non si dica diversamente, in un corso introduttivo la colorazione dei grafi significa colorare i vertici di un grafo semplice non orientato. La colorazione degli archi è un problema diverso con regole diverse.

Che cosa misura davvero il numero cromatico

I nomi dei colori non contano. Puoi usare rosso, blu e verde, oppure le etichette $1$, $2$ e $3$.

Quello che conta è il raggruppamento. Tutti i vertici con lo stesso colore formano un insieme senza archi al suo interno, quindi quel gruppo non ha conflitti.

Questo punto di vista è ciò che rende utile la colorazione dei grafi nei problemi di pianificazione e allocazione. Un colore spesso significa "questi elementi possono condividere lo stesso intervallo."

Esempio svolto: perché un ciclo di lunghezza 5 richiede 3 colori

Considera il grafo ciclo $C_5$ con archi $AB, BC, CD, DE,$ ed $EA$.

Prova prima con $2$ colori. Assegna ad $A$ il colore $1$ e a $B$ il colore $2$. Poi la colorazione è forzata lungo il ciclo:

$$A=1,\quad B=2,\quad C=1,\quad D=2$$

Ora guarda $E$. È adiacente sia a $D$ sia ad $A$, quindi non può usare il colore $2$ a causa di $D$, e non può usare il colore $1$ a causa di $A$.

Quindi $2$ colori non bastano.

Ma $3$ colori funzionano. Una colorazione propria è

$$A=1,\quad B=2,\quad C=1,\quad D=2,\quad E=3$$

quindi

$$\chi(C_5)=3$$

Vale la pena ricordare questo esempio perché mostra uno schema importante: per i grafi ciclo, un ciclo pari può essere colorato con $2$ colori, mentre un ciclo dispari richiede $3$ colori.

Come ragionare sulla colorazione dei grafi piccoli

Due controlli rapidi aiutano.

Per prima cosa, cerca un conflitto forzato. Nell'esempio sopra, alternare due colori lungo un ciclo dispari fa sì che l'ultimo vertice entri in conflitto con entrambe le scelte disponibili.

Secondo, cerca un limite inferiore. Se un grafo contiene un triangolo, allora quei tre vertici sono adiacenti a coppie, quindi richiedono già $3$ colori diversi. Questo non dà sempre la risposta esatta, ma dimostra che il numero cromatico è almeno $3$.

Errori comuni nei problemi di colorazione dei grafi

Un errore comune è trattare due vertici come adiacenti solo perché sono disegnati vicini. Solo un arco reale crea un vincolo di colorazione.

Un altro errore è supporre che ogni vertice abbia bisogno del proprio colore. I vertici non adiacenti possono riutilizzare un colore, e le colorazioni efficienti di solito riutilizzano i colori il più possibile.

A volte gli studenti confondono anche la colorazione dei vertici con la colorazione degli archi. In questa pagina, la regola riguarda i vertici adiacenti, non gli archi adiacenti.

Un ultimo errore è riportare il numero di colori che hai usato invece del numero minimo richiesto. Usare $4$ colori su un grafo non dimostra che il numero cromatico sia $4$.

Dove si usa la colorazione dei grafi

Un'applicazione classica è la pianificazione. Supponi che ogni vertice sia un esame, e che un arco significhi che due esami hanno studenti in comune e non possono essere collocati nello stesso momento. Allora un colore può rappresentare una fascia oraria.

In questo modello, il numero cromatico ti dice il minor numero possibile di fasce orarie. Se $\chi(G)=4$, allora non esiste una pianificazione valida con sole $3$ fasce.

La stessa idea compare nella colorazione delle mappe, dove regioni confinanti devono essere diverse, e nella progettazione dei compilatori, dove variabili necessarie nello stesso momento non possono condividere lo stesso registro.

Prova un problema simile di colorazione dei grafi

Disegna un grafo con vertici $P,Q,R,S,T$ e archi $PQ, QR, RS, ST, TP,$ e $PR$.

Inizia trovando un triangolo per ottenere un limite inferiore. Poi prova a colorare il grafo con il minor numero possibile di colori e controlla se qualche coppia di vertici adiacenti ha lo stesso colore. Se vuoi fare un passo in più, prova una tua versione su un grafo più grande e vedi se riesci a dimostrare che la tua colorazione è minima, non solo valida.