Calcolatore di Colorazione di Grafi

Trova il numero cromatico e una colorazione valida dei vertici per qualsiasi grafo non orientato. Inserisci gli archi o una lista di adiacenza e ottieni il numero minimo di colori, l'assegnazione dei colori, la soluzione animata passo-passo con DSATUR e una visualizzazione interattiva del grafo in SVG.

⚡ Prova un esempio:

Ciclo a 4 C₄ Triangolo K₃ Completo K₅ Pentagono C₅ Ruota W₆ Bipartito K₃,₃ Esempio adiacenza Programmazione esami

Formato input

⬌ Lista degli archi

⧇ Lista di adiacenza

Dati del grafo

Formato archi: A-B o A B, separati da virgole o a capo. Max 60 vertici e 600 archi.

Formato adiacenza: A: B, C, D — un vertice per riga, seguito dai suoi vicini.

Algoritmo

Auto sceglie il backtracking esatto per grafi piccoli e DSATUR per quelli più grandi.

Embed Calcolatore di Colorazione di Grafi Widget

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.

Definizione di numero cromatico

χ(G) = min { k : G ammette una k-colorazione propria }

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:

A-B, B-C, C-D, D-A
A-C

Lista di adiacenza

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

A: B, C, D
B: A, D
C: A
D: A, B

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

Scegli un formato: Passa dalla lista di archi alla lista di adiacenza con i pulsanti radio.
Inserisci il grafo: Incolla i tuoi dati o clicca su uno degli esempi rapidi (triangolo, completo K₅, ruota tipo Petersen, bipartito K₃,₃, programmazione esami).
Scegli un algoritmo: Lascia Auto per l'impostazione predefinita migliore, oppure forza Welsh-Powell, greedy, DSATUR o il backtracking esatto.
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.
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

Cita questo contenuto, pagina o strumento come:

"Calcolatore di Colorazione di Grafi" su https://MiniWebtool.com/it/calcolatore-di-colorazione-di-grafi/ di MiniWebtool, https://MiniWebtool.com/

dal team di miniwebtool. Aggiornato: 20 apr 2026

Puoi anche provare il nostro Risolutore di Matematica AI GPT per risolvere i tuoi problemi matematici attraverso domande e risposte in linguaggio naturale.

Altri strumenti correlati:

Calcolatore di Matrice di AdiacenzaNuovo

Calcolatore del Percorso più Breve di Dijkstra

Validatore di Sequenza di Gradi di Grafo

Verificatore di Cammino HamiltonianoNuovo

Risolutore di Mappa di Karnaugh (K-Map)Nuovo

Risolutore di Equazioni Lineari

Risolutore di Programmazione LineareNuovo

Calcolatrice Matrici

Calcolatore di Moltiplicazione di MatriciNuovo

Calcolatore di Flusso in Rete (Flusso Massimo)Nuovo

Calcolatore di Colorazione di Grafi

Calcolatore di Colorazione di Grafi

Cos'è la colorazione dei grafi?

Teoremi e limiti principali

Algoritmi utilizzati da questo calcolatore

DSATUR (Degree of Saturation)

Welsh-Powell

Greedy (ordine di input)

Backtracking esatto

Formati di input

Lista di archi

Lista di adiacenza

Come usare questo calcolatore

Applicazioni pratiche della colorazione dei grafi

Programmazione degli esami

Assegnazione delle frequenze radio

Allocazione dei registri

Colorazione delle mappe

Sudoku e rompicapi a vincoli

Casi speciali interessanti

Domande frequenti

Cos'è il numero cromatico di un grafo?

Quale algoritmo usa questo calcolatore?

Come devo inserire il mio grafo?

Perché DSATUR non trova sempre il vero numero cromatico?

Qual è un uso reale della colorazione dei grafi?

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

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

Ulteriori letture

Altri strumenti correlati:

Operazioni matematiche avanzate:

Strumenti in primo piano: