Calcolatore di Colorazione di Grafi

Calcolatore di Colorazione di Grafi

Il Calcolatore di Colorazione di Grafi calcola il numero cromatico χ(G) e una colorazione dei vertici valida per qualsiasi grafo non orientato. Inserisci il tuo grafo come lista di archi o lista di adiacenza e lo strumento restituirà il numero minimo di colori necessari affinché due vertici adiacenti non condividano lo stesso colore, insieme a una visualizzazione SVG interattiva, una traccia animata DSATUR e una suddivisione colore per colore di quali vertici ricevono quale colore.

Cos'è la colorazione dei grafi?

Una colorazione propria dei vertici di un grafo G = (V, E) assegna un colore a ciascun vertice in modo che ogni arco abbia estremità di colori diversi. Il numero cromatico, indicato con χ(G), è il numero minimo di colori per i quali esiste tale colorazione. Il calcolo di χ(G) è generalmente NP-hard, ma il problema ha una splendida teoria matematica e molte applicazioni pratiche: programmazione degli esami, assegnazione delle frequenze radio, allocazione dei registri nei compilatori e il famoso teorema dei quattro colori per le mappe planari.

Teoremi e limiti principali

• Limiti banali: 1 ≤ χ(G) ≤ |V| per ogni grafo.
• Limite inferiore della clique: χ(G) ≥ ω(G), dove ω(G) è la dimensione della clique più grande.
• Caratterizzazione bipartita: χ(G) ≤ 2 se e solo se G non ha cicli dispari (König).
• Teorema di Brooks: χ(G) ≤ Δ(G), a meno che G non sia un grafo completo o un ciclo dispari, nel qual caso χ(G) = Δ(G) + 1. Qui Δ(G) è il grado massimo.
• Teorema dei quattro colori: Ogni grafo planare è colorabile con 4 colori.
• Limite superiore greedy: Qualsiasi algoritmo greedy utilizza al massimo Δ(G) + 1 colori.

Algoritmi utilizzati da questo calcolatore

DSATUR (Degree of Saturation)

Introdotto da Daniel Brélaz nel 1979, DSATUR è una delle euristiche pratiche più forti per la colorazione dei grafi. Sceglie ripetutamente il vertice non colorato i cui vicini utilizzano già i colori più distinti (la sua saturazione), risolvendo i pareggi in base al grado del vertice, e gli assegna il colore più piccolo non utilizzato dai suoi vicini. DSATUR è dimostrabilmente ottimale sui grafi bipartiti e su molte famiglie di grafi strutturati, e produce colorazioni di alta qualità in millisecondi su grafi con centinaia di vertici.

Welsh-Powell

L'algoritmo Welsh-Powell ordina i vertici in ordine decrescente di grado e poi li colora in modo greedy. Funziona in tempo O(|V|²) e garantisce al massimo Δ(G) + 1 colori. È estremamente veloce e spesso rappresenta una buona prima approssimazione, anche se può essere superato da DSATUR su grafi con strutture locali variabili.

Greedy (ordine di input)

L'algoritmo più semplice: attraversa i vertici nell'ordine di input e assegna a ciascuno il colore più piccolo non utilizzato da un vicino già colorato. L'output è sensibile all'ordinamento di input, ma un ordinamento casuale fornisce una base di riferimento con cui confrontare le euristiche più intelligenti.

Backtracking esatto

Per grafi piccoli (fino a circa 18 vertici), il calcolatore può trovare il vero numero cromatico provando k = 2, 3, 4, ... e tentando di colorare il grafo con k colori tramite backtracking depth-first. La ricerca ordina i vertici per grado decrescente e pota i rami quando non ci sono colori disponibili. Quando l'algoritmo esatto ha successo, il risultato è etichettato come "Esatto".

Formati di input

Lista di archi

Scrivi ogni arco come due etichette di vertice separate da un trattino, uno spazio o una freccia. Separa gli archi con virgole o interruzioni di riga. Le etichette dei vertici possono essere lettere, cifre o underscore. Esempio:

Lista di adiacenza

Scrivi ogni vertice, i due punti e l'elenco dei suoi vicini separati da virgole. Esempio:

Gli auto-anelli (self-loop) vengono rifiutati perché un vertice non può ricevere un colore diverso da se stesso. Gli archi duplicati vengono eliminati silenziosamente e il grafo viene trattato come non orientato.

Come usare questo calcolatore

1. Scegli un formato: Passa dalla lista di archi alla lista di adiacenza con i pulsanti radio.
2. Inserisci il grafo: Incolla i tuoi dati o clicca su uno degli esempi rapidi (triangolo, completo K₅, ruota tipo Petersen, bipartito K₃,₃, programmazione esami).
3. Scegli un algoritmo: Lascia Auto per l'impostazione predefinita migliore, oppure forza Welsh-Powell, greedy, DSATUR o il backtracking esatto.
4. Clicca su "Colora il Grafo": Il numero cromatico, l'elenco colore per colore, un SVG interattivo con nodi trascinabili e una traccia animata appariranno sotto.
5. Esplora: Premi Play per guardare l'algoritmo colorare i vertici uno alla volta, trascina i nodi per riorganizzare il layout e usa Indietro / Avanti per scorrere manualmente la traccia.

Applicazioni pratiche della colorazione dei grafi

Programmazione degli esami

Ogni esame è un vertice e si traccia un arco tra gli esami che hanno almeno uno studente in comune. Una colorazione propria con k colori fornisce un programma con k fasce orarie in modo che nessuno studente abbia conflitti. Il numero cromatico è il numero minimo di sessioni.

Assegnazione delle frequenze radio

I trasmettitori che si trovano entro il raggio d'interferenza l'uno dall'altro devono trasmettere su frequenze diverse. Il numero cromatico del grafo di interferenza è il numero minimo di frequenze necessarie.

Allocazione dei registri

Nei compilatori, gli intervalli di vita delle variabili sono vertici; se due intervalli si sovrappongono nel tempo, c'è un arco tra loro. Una k-colorazione assegna le variabili a k registri della CPU senza collisioni.

Colorazione delle mappe

I paesi che condividono un confine devono ricevere colori diversi. Il teorema dei quattro colori (Appel-Haken, 1976) dimostra che quattro colori sono sempre sufficienti per qualsiasi mappa planare.

Sudoku e rompicapi a vincoli

Un Sudoku completato è una 9-colorazione di un grafo i cui vertici sono le 81 celle e i cui archi collegano le celle nella stessa riga, colonna o riquadro 3×3. La colorazione dei grafi è il nucleo matematico di molti rompicapi di soddisfazione dei vincoli.

Casi speciali interessanti

• Grafo completo K_n: χ(K_n) = n. Ogni coppia di vertici è adiacente, quindi tutti i colori devono essere distinti.
• Ciclo C_n: χ(C_n) = 2 se n è pari, 3 se n è dispari.
• Albero: Qualsiasi albero con ≥ 2 vertici ha χ = 2 (gli alberi sono bipartiti).
• Grafo bipartito: χ = 2 se il grafo ha almeno un arco.
• Grafo di Petersen: Un famoso grafo 3-regolare con χ = 3.
• Grafo ruota W_n: Un vertice centrale unito a un ciclo di n vertici. χ = 3 se n è pari, 4 se n è dispari.

Domande frequenti

Cos'è il numero cromatico di un grafo?

Il numero cromatico χ(G) è il numero minimo di colori necessari per colorare i vertici di un grafo in modo che due vertici adiacenti non condividano lo stesso colore. I grafi bipartiti hanno un numero cromatico massimo di 2; qualsiasi grafo che contenga un triangolo ha un numero cromatico di almeno 3; e secondo il teorema di Brooks il numero cromatico non supera mai il grado massimo, eccetto per i grafi completi e i cicli dispari.

Quale algoritmo usa questo calcolatore?

Per i grafi piccoli il calcolatore esegue una ricerca di backtracking esatta per trovare il vero numero cromatico. Per i grafi più grandi utilizza l'euristica DSATUR, che colora ripetutamente il vertice non colorato con il maggior numero di vicini già colorati. Puoi anche forzare Welsh-Powell o il semplice greedy dal menu a discesa dell'Algoritmo.

Come devo inserire il mio grafo?

Usa la modalità lista di archi per digitare un arco per riga come A-B, o separati da virgole come A-B, B-C, C-A. Usa la modalità lista di adiacenza per scrivere ogni vertice seguito da due punti e dai suoi vicini, come A: B, C. Gli auto-anelli vengono rifiutati perché un vertice non può essere colorato diversamente da se stesso.

Perché DSATUR non trova sempre il vero numero cromatico?

La colorazione dei grafi è NP-hard, quindi nessun algoritmo veloce noto trova sempre il numero minimo di colori. DSATUR è un'eccellente euristica pratica e spesso coincide con il vero numero cromatico, ma su grafi ostili può usare più colori del necessario. Il calcolatore riporta sia i colori usati che un limite inferiore della clique più grande trovata, così puoi giudicare la precisione della risposta.

Qual è un uso reale della colorazione dei grafi?

La colorazione dei grafi modella la programmazione degli esami (ogni esame è un vertice, i conflitti sono archi, i colori sono fasce orarie), l'assegnazione delle frequenze radio (i vertici sono trasmettitori, gli archi sono interferenze), l'allocazione dei registri nei compilatori, la colorazione delle mappe, la risoluzione di Sudoku e l'assegnazione di compiti alle macchine sotto vincoli di conflitto.

Il numero cromatico è sempre uguale alla clique più grande?

No. Il numero di clique ω(G) è sempre un limite inferiore per il numero cromatico χ(G), e sono uguali per i grafi perfetti come i grafi bipartiti, gli alberi, i grafi di intervallo e i grafi cordali. Per i grafi generali χ(G) può essere strettamente superiore a ω(G); l'esempio classico sono i grafi di Mycielski, che sono privi di triangoli ma richiedono un numero arbitrariamente grande di colori.

Qual è il grafo più grande che questo calcolatore può gestire?

Il calcolatore supporta fino a 60 vertici e 600 archi. Per l'algoritmo esatto, i grafi con più di circa 18 vertici potrebbero passare a DSATUR perché il backtracking diventa troppo lento. Per l'uso pratico, questo copre la maggior parte degli esempi didattici, dei problemi di programmazione degli esami e delle applicazioni di piccole e medie dimensioni.

Ulteriori letture

• Colorazione dei grafi — Wikipedia
• Algoritmo DSATUR — Wikipedia (EN)
• Polinomio cromatico — Wikipedia
• Teorema dei quattro colori — Wikipedia
• Teorema di Brooks — Wikipedia (EN)