Colora il grafo

Il problema della colorazione di un grafo

Vogliamo dare un colore a ogni nodo in modo che due nodi collegati non abbiano lo stesso colore, usando il minor numero di colori. In pratica significa assegnare risorse diverse a elementi che si interferiscono: ad esempio scegliere canali Wi-Fi diversi per router vicini, mettere lezioni che condividono aula/docente in orari diversi, o colorare le regioni di una mappa con pochi pennarelli senza che due confinanti abbiano lo stesso colore. Meno colori ⇒ uso più efficiente delle risorse.

Trovare il numero minimo di colori è un problema NP-difficile. Nella pratica si usano euristiche (rapide, non garantiscono l’ottimo) e, su grafi piccoli, algoritmi esatti (ottimi ma più lenti).

Istruzioni di gioco

Seleziona un livello e premi Carica.
Clicca un nodo per assegnare il colore selezionato nella tavolozza.
Shift + Click rimuove il colore dal nodo.
Vince chi ottiene 0 conflitti usando ≤ – colori.

Tavolozza

Suggerimento: inizia dai nodi con più vicini.