Colorazione di grafi
Colora un grafo con il minor numero possibile di colori
Informazioni su questo calcolatore
Il Calcolatore di colorazione di grafi trova il numero cromatico χ(G), cioè il minimo numero di colori necessario per colorare i vertici di un grafo in modo che nessun lato unisca due vertici dello stesso colore, e mostra una colorazione ottimale. Inserisci il numero di vertici e un elenco di lati: calcola χ esattamente con una ricerca branch-and-bound, riporta il grado massimo Δ e la cricca massima ω (un limite inferiore per χ), segnala i grafi bipartiti e completi e disegna il grafo colorato. Utile per la pianificazione, l'allocazione dei registri, la colorazione di mappe e lo studio dei numeri cromatici.
Come colorare un grafo
- Inserisci il numero di vertici; sono numerati da 1 a n.
- Elenca i lati come coppie del tipo 1-2, 2-3, una coppia per ogni collegamento.
- Leggi il numero cromatico χ(G) e il colore assegnato a ogni vertice.
- Confronta χ con la cricca massima ω per capire perché servono proprio quei colori, oppure carica una preimpostazione per esplorare.
Esempi comuni
- Un triangolo (K₃) richiede 3 colori: ogni coppia di vertici è adiacente.
- I cicli pari sono bipartiti e richiedono solo 2 colori; i cicli dispari come C₅ ne richiedono 3.
- Il grafo completo Kₙ richiede esattamente n colori.
- Una cricca massima di dimensione ω richiede almeno ω colori, quindi χ(G) ≥ ω.
- Il grafo di Grötzsch richiede 4 colori pur non contenendo triangoli, quindi χ può superare il numero di cricca.
Domande frequenti
Che cos'è il numero cromatico?
Il numero cromatico χ(G) è il minimo numero di colori necessario per colorare i vertici di un grafo in modo che nessun lato colleghi due vertici dello stesso colore.
Come viene trovato il numero minimo di colori?
Poiché il grafo è piccolo, il calcolatore esegue una ricerca esatta: prova con 1 colore, poi con 2 e così via, restituendo il primo numero per cui esiste una colorazione propria. Quel numero è garantito essere il vero minimo.
Che cosa sono il grado massimo e la cricca massima?
Il grado massimo Δ è il maggior numero di lati che si incontrano in un singolo vertice. La cricca massima ω è il più grande insieme di vertici tutti adiacenti tra loro; poiché devono avere colori tutti diversi, χ(G) è almeno ω.
Perché un grafo senza triangoli può comunque richiedere molti colori?
Una cricca grande richiede molti colori, ma non è l'unico motivo. I cicli dispari e grafi come quello di Grötzsch richiedono colori aggiuntivi anche senza alcun triangolo, quindi χ(G) può essere maggiore del numero di cricca.
C'è un limite alla dimensione del grafo?
Sì. La colorazione esatta dei grafi è computazionalmente difficile, quindi il calcolatore limita il grafo a 12 vertici per mantenere i risultati immediati e rigorosi.