L’angolo matematico di Stefano Leonesi: lo strano teorema dei quattro colori

L’angolo matematico di Stefano Leonesi

Lo strano teorema dei quattro colori

Quanti colori per una cartina geografica?

Tutti noi siamo abituati ad osservare carte geografiche che rappresentano regioni o stati. Il fatto che aree confinanti abbiano colori diversi ci aiuta a distinguerli meglio a colpo d’occhio, come nella qui presente mappa delle regioni italiane (fig. 1).

Si tenga presente che se il confine tra due regioni fosse rappresentato da un solo punto o più punti isolati in comune, si potrebbe utilizzare per esse anche lo stesso colore senza pericolo di confusione, come si può vedere nelle regioni A e B della fig. 2.

Ma vi siete mai chiesti quanti colori vengono usati in genere per dipingere una cartina? Per rispondere alla domanda facciamo un salto indietro nel tempo. Era l’ottobre del 1852 quando Francis Guthrie, uno studente di Matematica dello University College di Londra, si accorse che per colorare la mappa delle contee inglesi bastavano quattro colori. Non solo, notò anche che i cartografi di allora riuscivano in effetti a pitturare una qualunque mappa usando non più di quattro tinte. Guthrie si chiese allora quale fosse il minimo numero di colori necessario per pitturare una qualsiasi mappa e, in particolare, se ne bastassero proprio quattro come lui ipotizzava; oppure potevano esistere delle cartine, reali o immaginarie, che necessitavano di più di quattro colori?

Da allora numerosi matematici e informatici hanno tentato di dimostrare la congettura di Guthrie, senza però riuscire nell’intento fino al 1977, oltre 120 anni dopo!

Come può la matematica essere stata utile in tutto ciò? Be’, intanto se si tratta di “dimostrare”, questo è il terreno prediletto della regina delle scienze. Ma vediamo più in dettaglio come si può affrontare la questione sotto il profilo matematico. Il fatto è che una mappa geografica si può rappresentare in maniera semplice attraverso uno schema, detto grafo, costituito da punti e da linee che li uniscono: ad ogni regione si associa un punto, magari collocato sul capoluogo o sulla capitale (ma non è fondamentale), si traccia poi una linea tra due punti solo se le due regioni sono confinanti, nel senso che abbiamo descritto prima, dunque se hanno un tratto di frontiera comune – non bastano punti isolati – come in fig. 3.

Il problema di colorare gli stati della mappa si riconduce allora a quello di colorare i punti del grafo corrispondente in modo che punti collegati da una linea ricevano colori diversi. Pertanto la teoria matematica dei grafi (introdotta dal grande matematico Eulero nel 1736) ha fornito il supporto più adeguato e naturale per affrontare e risolvere il problema della colorabilità di una mappa. È anzitutto evidente che per alcune cartine sono sufficienti solo tre o addirittura due colori; ad esempio, nella prima mappa della fig. 4 ne bastano 2, nella seconda, con 3 regioni schematizzata insieme al relativo grafo, ne occorrono tre.

Ma già una mappa con 4 regioni del tipo illustrato – insieme al rispettivo grafo – in fig. 5 necessita di quattro colori distinti, se non vogliamo che regioni confinanti assumano la medesima tinta.

Anche la cartina dell’Italia di fig. 1 può essere ricolorata usando solo quattro colori, ad esempio come in fig. 6, ma non con meno a causa della presenza dell’Umbria che, insieme a Toscana, Marche e Lazio, riproduce la situazione descritta nella fig. 5.

Il fatto sorprendente è che nel 1977 K. Appel, W. Haken e J. Koch, lavorando appunto sulle proprietà dei grafi, provarono che effettivamente per colorare una qualunque cartina, “piana e connessa”, non servono più di quattro colori.

La dimostrazione originale del teorema, oggi chiamato “Teorema dei quattro colori”, era di impressionante lunghezza (addirittura 139 pagine!) e godeva di una notevole peculiarità: visto che si dovevano ridurre le infinite mappe possibili ad un numero finito di configurazioni; nel loro caso riuscirono a ridurle fino a 1476, una quantità comunque troppo elevata per poter analizzare a mano ogni singolo caso. Per cui, per la prima volta nella storia di una dimostrazione matematica, si fece ricorso all’aiuto massiccio di un computer, proprio per velocizzare i tempi delle verifiche del teorema per ognuna delle 1476 configurazioni. Tuttavia, questo stesso uso del computer sollevò nell’ambiente dei matematici numerose critiche dovute alla difficoltà di poter controllare poi la correttezza dei passi della lunghissima prova, se non coinvolgendo in alcune fasi nuovamente un calcolatore e dunque prescindendo in parte dalle capacità umane di analisi e verifica. Oggi, a seguito di profonde e accurate verifiche incrociate, i dubbi e le riserve sono rientrati e la dimostrazione del “Teorema dei quattro colori” è universalmente accettata e, anzi, ritenuta una pietra miliare della matematica moderna in grado di miscelare aspetti logici e informatici.

Ebbene, cartografi di oggi e del futuro potete stare tranquilli: con solo quattro tinte potete colorare tutte le mappe geografiche che volete! A patto che le regioni siano connesse e vengano disegnate su una superficie piana o un mappamondo perché per altre superfici particolari, come una ciambella, be’ la matematica ci fornisce altre sorprendenti risposte. Ma questa è un’altra storia.