Paesi
Confini
Colori usati
Conflitti

Di più sul teorema dei quattro colori

Teorema dei quattro colori: mappa da colorare

Per quanto complicata sia una mappa, quattro colori bastano sempre per colorarla in modo che i paesi con un confine in comune non abbiano mai lo stesso colore. L'enunciato è così semplice che un bambino può metterlo alla prova con i pastelli, eppure ci sono voluti più di un secolo e un computer per dimostrarlo. Colora tu stesso una mappa casuale, guarda quali confini sono in conflitto e poi osserva tre metodi all'opera, da una rapida regola greedy che a volte ha bisogno di un quinto colore a una ricerca con backtracking che se la cava sempre con quattro. Scegli un colore e clicca sui paesi per colorarli; un confine diventa rosso quando due vicini hanno lo stesso colore. I paesi che si toccano solo in un angolo possono avere lo stesso colore. Oppure lascia fare al computer: scegli un metodo e premi Risolvi per guardarlo lavorare, o Passo per seguire una mossa alla volta. Minimo di colori verifica se a questa mappa potrebbero bastare tre colori, o persino due. Nuova mappa disegna un'altra mappa, e Mostra i vicini disegna la rete dei paesi che hanno un confine in comune.

Come funziona

  1. Scegli il numero di paesi e premi Nuova mappa, oppure inizia con la mappa mostrata.
  2. Scegli un colore e clicca sui paesi per colorarli, facendo attenzione ai confini rossi dove i vicini sono in conflitto.
  3. Scegli un metodo e premi Risolvi o Passo per guardarlo colorare la mappa, e premi Minimo di colori per vedere quanti colori servono a questa mappa.

Dalle mappe ai grafi

Metti un punto in ogni paese e collega due punti quando i loro paesi hanno un confine in comune. La mappa diventa un grafo, e colorare la mappa equivale a colorare i punti in modo che i punti collegati siano diversi. Poiché le mappe sono disegnate su un foglio piano, questi grafi sono planari: si possono disegnare senza linee che si incrociano. I paesi che si incontrano in un solo punto, come quattro quadrati in un angolo, non sono vicini. Il teorema dei quattro colori afferma che ogni grafo planare può essere colorato con quattro colori. Attiva Mostra i vicini per vedere il grafo della mappa attuale.

Tre modi di colorare

La colorazione greedy prende i paesi uno alla volta, prima quelli con più vicini, e assegna a ciascuno il primo colore che i suoi vicini non hanno usato. È veloce ma miope, e su alcune mappe ricorre a un quinto o persino a un sesto colore. DSATUR, inventato da Daniel Brélaz nel 1979, sceglie sempre come prossimo il paese i cui vicini mostrano già il maggior numero di colori diversi, il che di solito evita quella trappola. Il backtracking prova i colori a turno e, quando per un paese non ne resta nessuno, annulla le scelte più recenti e riprova; trova sempre una colorazione con quattro colori, a volte dopo essere tornato indietro molte volte.

Domande frequenti

Perché quattro colori bastano sempre?

Nessuno ha trovato una ragione breve. La dimostrazione di Kenneth Appel e Wolfgang Haken del 1976 ha mostrato che ogni mappa deve contenere una di 1.936 piccole configurazioni e che ciascuna di esse può essere rimossa e la colorazione ripristinata in seguito; verificarle tutte ha richiesto più di mille ore di calcolo al computer. Una dimostrazione al computer più semplice di Neil Robertson, Daniel Sanders, Paul Seymour e Robin Thomas del 1996 richiede 633 configurazioni, e nel 2005 Georges Gonthier ha verificato completamente una dimostrazione con l'assistente di dimostrazione Coq.

Alcune mappe hanno bisogno di tutti e quattro i colori?

Sì. Quattro paesi che toccano ciascuno gli altri tre, come un paese circondato da un anello di altri tre, ne richiedono quattro. Molte mappe, però, se la cavano con tre, e Minimo di colori lo scopre per la mappa sullo schermo. Decidere in generale se una mappa può essere colorata con tre colori è un problema difficile, NP-completo, anche se quattro colori bastano sempre.

Perché il metodo greedy a volte usa cinque colori?

Colora ogni paese una sola volta e non cambia mai idea. Una scelta iniziale può lasciare un paese successivo circondato da tutti e quattro i colori, e l'unica via d'uscita è un quinto. Il backtracking invece tornerebbe indietro e cambierebbe le scelte precedenti.

Il teorema vale su altre superfici?

Su una sfera sì: è la stessa cosa del piano. Su un toro, la superficie di una ciambella, alcune mappe richiedono sette colori, e sette bastano sempre, come ha dimostrato Percy Heawood. Se i paesi possono essere formati da più parti separate, come una nazione con colonie, quattro colori non bastano più.

Viene inviato qualcosa a un server?

No. La mappa, i metodi di colorazione e la verifica vengono eseguiti nel tuo browser. Le tue impostazioni restano nella memoria locale di questo browser.

Pronto a provarlo?

Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

Vai all'editor