M111~IF

0.1" 44110.41.1%4

e .1411~.Inw".• ,411)nn••.*0

uwil~i I "s` f~til• Wet•-•1".4 11 --;-~42~1W-g~

La soluzione del problemadei quattro colori

Quattro colori bastano per colorare ogni carta su un piano o su una sfera inmodo che due regioni adiacenti non abbiano lo stesso colore. Il problemaè stato risolto in modo nuovo, facendo uso di calcolatori ad alta velocità

N

el 1852, pochi mesi dopo avercompletato i suoi studi all'Uni-versity College di Londra, Fran-

cis Guthrie scrisse una lettera al fratello,Frederick, che ancora si trovava in quelcollege come allievo del matematico Au-gustus De Morgan. In quella lettera glisegnalava la sua impressione che unaqualunque carta tracciata su un fogliopotesse essere colorata con quattro colo-ri solamente, in modo tale che regionicon confini in comune non avessero ilmedesimo colore. Guthrie chiedeva se cifosse un metodo matematico per dimo-strarlo e Frederick rispose che non lo sa-peva e non lo sapeva nemmeno De Mor-gan, a cui lo aveva chiesto. Da allora,per 124 anni, il problema di dimostrareche ogni carta richiede al massimo quat-tro colori o, alternativamente, di traccia-re una carta per cui siano necessari cin-que colori, ha affascinato matematici diprofessione, matematici dilettanti e stu-denti universitari convinti che tutti i pro-blemi irrisolti fossero rimasti tali soloa causa dell'incompetenza delle prece-denti generazioni.

Nel 1976 abbiamo risolto il proble-ma dei quattro colori. La congettura diGuthrie è stata dimostrata matematica-mente, ma in modo ben diverso da quel-lo che egli si sarebbe aspettato. Anchefra i matematici di oggi, quanti non sonoa conoscenza degli sviluppi che hannoportato alla dimostrazione, restano piut-tosto perplessi, poiché la dimostrazionesi avvale di un uso senza precedenti deglielaboratori elettronici: i calcoli la rendo-no più lunga di quanto tradizionalmentesi sia considerato accettabile. In effetti,la correttezza della dimostrazione n^npuò essere controllata senza l'ausilio diun elaboratore. Inoltre, alcune delle ideefondamentali della dimostrazione sonostate messe a punto grazie a esperimenticon elaboratori. Ovviamente, è possibileche un giorno qualcuno trovi una dimo-strazione più breve del teorema dei quat-tro colori, magari uno di questi brillanti

di Kenneth Appel e Wolfgang Haken

studenti universitari. E anche pensabileche una tale dimostrazione non sia possi-bile: in tal caso avrebbe fatto la suacomparsa un nuovo e interessante tipo diteorema, un teorema, cioè, che non hauna dimostrazione di tipo tradizionale.

Nonostante gli aspetti insoliti della di-mostrazione, tanto il problema dei quat-tro colori quanto i metodi alla base delladimostrazione stessa hanno radici pro-fonde nella matematica. Cominceremo aesaminarli tornando alla formulazione o-riginale del problema, nella lettera diFrancis Guthrie. Parlando di regioni«confinanti» Guthrie deve aver pensatoa regioni aventi in comune un tratto diconfine che non si riduce a un punto,poiché altrimenti una carta a forma ditorta tagliata a fette richiederebbe tanticolori quante sono le regioni (le fette).Per «regione», poi, certamente dovevaintendere una zona connessa, poiché sesi ammette che una regione possa esserecostituita da più zone separate, non èaffatto difficile costruire un esempio dicarta con cinque regioni, ognuna dellequali sia adiacente a ciascuna delle altrequattro (si veda l'illustrazione in alto apagina 56).

Guthrie e De Morgan si resero sicura-mente conto che è possibile tracciare unacarta con quattro regioni, ciascuna dellequali sia adiacente a tutte le altre (si vedala parte sinistra dell'illustrazione in bas-so a pagina 56). Una tale carta richiedequattro colori e pertanto una congetturadei tre colori è falsa: tre colori non sonosufficienti per colorare qualunque carta.

De Morgan dimostrò che non è possi-bile che cinque regioni siano in posizionetAP• che ciascuna di esse si'. adiacentealle altre quattro, e questo lo portò acredere che cinque colori non fosseromai necessari, e quindi che la congetturafosse vera. Dimostrare che in una cartanon possono esistere cinque regioni mu-tuamente adiacenti non è equivalente,tuttavia, a dimostrare la congettura deiquattro colori (si veda l'illustrazione in

basso a pagina 56). Molti matematici di-lettanti, non comprendendo questo, han-no dimostrato indipendentemente il ri-sultato di De Morgan e hanno così pen-sato di aver dimostrato la congettura deiquattro colori.

Nel 1878 il matematico Arthur Cayley,non riuscendo a dimostrare o a re-

futare la congettura dei quattro colori,presentò il problema alla London Ma-thematical Society. Meno di un anno piùtardi Alfred Bray Kempe, avvocato mem-bro della società, pubblicò un saggio incui pretendeva di dimostrare la veritàdella congettura. L'argomentazione diKempe era estremamente sottile, e ben-ché la sua dimostrazione si sia rivelataincompleta, essa conteneva la maggiorparte delle idee fondamentali che, un se-colo più tardi, hanno condotto alla di-mostrazione corretta. Kempe cercò di di-mostrare la congettura con il classicometodo della reductio ad absurdum: as-sunse che la congettura fosse falsa (che,cioè, esistesse almeno una carta per cuifossero necessari cinque colori) e quindiprocedette a mostrare che tale assunzio-ne porta a una contraddizione. Il rag-giungimento di una contraddizione dimo-stra che l'assunzione originale (qualchecarta richiede cinque colori) è falsa, eche pertanto è vera la congettura deiquattro colori (quattro colori sono sem-pre sufficienti).

Kempe cominciava definendo le cartenormali: una carta è normale se nessunadelle sue regioni include altre regioni e sein un unico punto non concorrono più ditre regioni (si veda l'illustrazione di pagi-na 57). Dimostrava, poi, che, ove esistes-se una carta che richiede cinque colori,una carta «pentacromatica», allora do-vrebbe esistere una carta pentacromaticanormale. Pertanto, per dimostrare la con-gettura dei quattro colori, sarebbe suffi-ciente dimostrare l'impossibilità di unacarta pentacromatica normale. Kempenotava che, se esistesse una carta penta-

cromatica normale, allora dovrebbe esi-sterne una con un numero minimo di re-gioni, una «carta pentacromatica norma-le minimale». (In altre parole: una cartacon un numero di regioni inferiore aquello delle regioni presenti nella penta-cromatica normale minimale può esserecolorata con quattro o meno colori.) Per-tanto, per dimostrare la congettura deiquattro colori, è sufficiente dimostrareche una carta pentacromatica normaleminimale è impossibile, e cioè che postu-

lare l'esistenza di una carta minimalenormale che richiede cinque colori con-duce a una contraddizione.

Kempe raggiunse una contraddizionein questo modo. Prima provò che ognicarta normale deve avere qualche regio-ne con cinque o meno regioni adiacenti.Argomentò quindi che, se una carta mi-nimale normale pentacromatica ha unaregione con meno di sei regioni confi-nanti (cosa che, come aveva appena di-mostrato, accade per ogni carta norma-

le), allora dovrebbe esistere una cartanormale con un numero minore di regio-ni, ancora pentacromatica. Se l'argomen-tazione fosse stata del tutto corretta, inquesto modo si sarebbe raggiunta unacontraddizione. Assumendo l'esistenza diuna carta pentacromatica minimale,Kempe avrebbe dimostrato infatti l'esi-stenza di una carta pentacromatica piùpiccola ancora. Ciò contraddirebbe alladefinizione di carta pentacromatica mi-nimale, quindi una carta siffatta non

na compley,a carta creata da 1.d nn arti I . Muore dell'I niv ersità delWisconsin, colorata con quattro colori al fine di illustrare il teoremadei quattro colori. Benché alcune carte (compresa questa) siano didifficile colorazione con quattro soli colori, nessuno ha mai creatouna carta che richiedesse cinque o più colori. Fino all'anno scorso,tuttavia, tutti gli sforzi compiuti per dimostrare che quattro colori so-no sufficienti per colorare qualunque carta tracciata su una sfera o nelpiano sono falliti. La difficoltà nella colorazione di una carta (li-pende dal modo in cui i vari paesi confinano l'uno con l'altro. Le

«configurazioni», o dispi),iiidni di pac,1 confinanti, all'interno dellacarta di Moore hanno aiutato gli autori a valutare le difficoltà dicalcolo nel migliorare il loro approccio - alla fine coronato dasuccesso - alla dimostrazione del teorema dei quattro colori. Nell'illu-strazione di questa pagina è presentata solo una parte della carta diMoore, che nella sua interezza è una proiezione cilindrica con ottago-ni (paesi, cioè, che confinano con altri otto paesi) ai poli nord e sud.La carta di Moore, che complessivamente è composta di 54 ottagoni,228 ettagoni, 96 esagoni e 408 pentagoni è stata colorata da Tom Burket.

54 55

Il teorema dei quattro colori afferma che quattro colori sono sempre sufficienti per colorare unacarta tracciata nel piano, in modo che due paesi confinanti non abbiano mai lo stesso colore.Perché il teorema sia sensato, una carta deve consistere di paesi contigui. Paesi confinantidebbono essere adiacenti lungo una linea, poiché se paesi adiacenti per un solo punto fosseroconsiderati confinanti, la carta a sinistra necessiterebbe di un colore diverso per ciascuno deisuoi sette paesi. I vari paesi debbono essere costituiti da una singola regione connessa, altrimentila carta a destra, nella quale il paese E è diviso in due pezzi, necessiterebbe di cinque colori.

Tre colori non sono sufficienti per colorare tutte le carte, come è mostrato dalla carta di quattropaesi alla sinistra. Ciascun paese è adiacente agli altri tre, cosicché la carta richiede ovviamentel'uso di quattro colori. D'altra parte, non è corretto assumere che il numero dei colori necessariper una carta sia uguale al massimo numero di paesi mutuamente adiacenti riscontrabile sullacarta stessa. Nella carta a destra, ad esempio, benché non vi siano più di Ire paesi mutuamenteadiacenti. occorrono quattro colori: tre per l'anello esterno e uno per il paese nel centro.

sarebbe possibile. Dal momento che ciòimplica che non esistano affatto cartepentacromatiche, la dimostrazione sareb-be stata completa. Kempe dimostrò cor-rettamente che l'esistenza in una cartapentacromatica minimale di una regionecon due, tre o quattro confinanti condu-ce a una contraddizione, ma la dimostra-zione per il caso della regione con cinqueconfinanti era errata. Nella nostra di-mostrazione del teorema dei quattro co-lori abbiamo corretto l'analisi fallace diKempe per quest'ultimo caso, esaminan-do circa 1500 configurazioni di regioni.Il nostro metodo è stato sostanzialmenteun'estensione delle parti valide della di-mostrazione di Kempe, che è stata og-getto di grande attenzione e di progressi-vi raffinamenti da parte dei matematici,nel corso degli ultimi cento anni.

Kempe aveva dimostrato che in ognicarta normale esiste almeno una regione

con due, tre, quattro o cinque confinan-ti. (In altre parole, non esistono cartenormali su un piano, in cui ogni regioneconfini con sei o più altre regioni.) Que-sto fatto può essere espresso dall'enun-ciato che l'insieme di «configurazioni»consistente di una regione con due con-finanti, una regione con tre confinanti,una regione con quattro confinanti e unaregione con cinque confinanti (si vedal'illustrazione in alto a pagina 59) è «i-ne \ ilabile», che cioè ogni carta normaledeve contenere almeno una di questequattro configurazioni. T èuna delle due idee basilari per la nostradimostrazione del teorema dei quattrocolori.

La seconda idea importante è quella diriducibilità. Intuitivamente, una configu-razione è riducibile se esiste un modo,che faccia uso della semplice ispezionedella configurazione e del modo in cui

catene di regioni possono essere allinea-te, per mostrare che la configurazionenon può apparire in una carta pentacro-matica minimale. Kempe dimostrò chetre delle sue configurazioni sono riduci-bili, ma errò nel dimostrare che una re-gione con cinque confinanti rappresentauna configurazione riducibile. Il metodoper dimostrare la riducibilità delle confi-gurazioni scaturisce dalla dimostrazionedi Kempe dell'impossibilità, per una re-gione con quattro confinanti, di compa-rire in una carta pentacromatica minima-le. L'uso del termine «riducibile» originadalla forma dell'argomento di Kempe:egli infatti dimostrò che se una cartapentacromatica minimale contiene unaregione con, diciamo, quattro confinan-ti, allora esiste una carta pentacromaticacon un numero ridotto di regioni (si vedal'illustrazione in basso a pagina 59 e l'il-lustrazione di pagina 60).

possiamo descrivere l'approccio diKempe alla congettura dei quattro

colori come un tentativo di trovare uninsieme inevitabile di configurazioni ri-ducibili. Trovare un simile insieme sa-rebbe sufficiente per dimostrare la con-gettura dei quattro colori, poiché essomostra come ogni carta contenga unaconfigurazione che non può essere partedi una carta pentacromatica minimale.Quindi non può esistere una carta penta-cromatica minimale e ciò implica, comecorrettamente dimostrò Kempe, che nonesistano affatto carte pentacromatiche.Come Kempe, abbiamo affrontato il pro-blema costruendo un insieme inevitabiledi configurazioni riducibili: solo che, ilnostro insieme consisteva di circa 1500figure complesse e non di sole quattrosemplici configurazioni.

Nel 1890, 11 anni dopo che Kempeaveva pubblicato la sua dimostrazione,Percy John Heawood evidenziò come loargomento di Kempe, secondo cui unacarta pentacromatica minimale non puòcontenere una regione con cinque confi-nanti, fosse errato, e come l'errore nonrisultasse di facile correzione. Nell'af-frontare il problema, Heawood investigòuna generalizzazione della formulazioneoriginale della congettura dei quattro co-lori. Le carte studiate da Guthrie e Kem-pe erano carte su una sfera o sul piano:Heawood, considerando carte su super-fici più complesse, riuscì a ottenere unrisultato elegante, che forniva un confinesuperiore per il numero dei colori richie-sti per colorare carte su tali superfici. Seil metodo da lui usato fosse stato appli-cabile al piano, egli avrebbe 'così fornitouna dimostrazione della congettura deiquattro colori.

Heawood continuò a lavorare sul pro-blem'. per n"n men" cli 4(nnn . Nel cor-so di tale periodo molti altri eminentimatematici profusero grossi sforzi sullacongettura dei quattro colori. Ci si puòmeravigliare che tanti matematici spen-dessero così tanto tempo su quella cheappariva una questione di così poca im-portanza, sul piano pratico. La spiega-zione sta nelle scoperte fatte nel secolo

scorso sulla natura della matematica pu-ra, e negli effetti di tali scoperte sullafede dei matematici nei poteri della lorodisciplina.

Verso la fine del diciannovesimo secoloV i matematici riuscirono a costruire

potenti teorie che li misero in grado ditrovare una soluzione a molti difficiliproblemi. Crebbe la sensazione che ogniproblema che potesse esser posto ragio-nevolmente, nel linguaggio della mate-matica, avrebbe potuto trovare una solu-zione con l'uso di metodi matematici suf-ficientemente potenti. Inoltre, si credevache le risposte a tali problemi potesseroessere di tal fatta che un matematicocompetente potesse controllarne la cor-rettezza entro un lasso ragionevole ditempo. La congettura dei quattro colorisicuramente doveva sembrare uno di que-sti problemi, e se i matematici non riu-scivano a risolvere il problema, la ragio-ne sembrava essere semplicemente nelfatto che non avevano ancora sviluppatogli strumenti matematici opportuni.

Nel corso degli anni trenta del nostrosecolo, tuttavia, nuove scoperte misero adura prova l'ottocentesca fede nella com-pletezza della matematica. Kurt Godei eAlonzo Church ottennero nuovi imba-razzanti risultati nell'ambito della logicaformale, la branca della matematica incui il concetto di dimostrazione è enun-ciato nella forma più precisa. Si dimo-strò che, in quello che sembra il sistemalogico più naturale, esistono enunciati lacui verità (o falsità) non può essere di-mostrata all'interno del sistema stesso.Di più, esistono nel sistema teoremi conenunciati relativamente brevi le cui di-mostrazioni di lunghezza minima sonoancora troppo lunghe per poter esserescritte in un qualunque regionevole lassodi tempo. Ricerche ulteriori, nel corsodegli anni cinquanta, hanno mostratoche anche altre branche della matemati-ca, e non solo la logica, sono afflittedalle stesse difficoltà. Alcuni matematicicominciarono a pensare che la congettu-ra dei quattro colori fosse uno di queglienunciati che non possono essere né di-mostrati né refutati; dopotutto, la con-gettura era stata studiata, senza succes-so, per 80 anni. Altri ricercatori avevanola sensazione che, se pure una dimostra-zione esisteva, sarebbe stata troppo lun-ga per poter essere scritta per intero.Molti, tuttavia, credevano che la malat-tia dell'indecidibilità non potesse diffon-dersi sino in questa zona della matemati-ca, e che si sarebbe trovata un'eleganteargomentazione matematica, per decide-re della verità o falsità della congetturadei quattro colori.

Oggi sappiamo che una dimostrazionepuò essere trovata. Ma ancora non sap-piamo (e forse non lo sapremo mai) seesista una dimostrazione che sia concisa,elegante e del tutto comprensibile a men-te umana. Sono così tante le branchedella matematica implicate nei vari ten-tativi di dimostrare la congettura deiquattro colori, che sarebbe impossibilediscuterli tutti qui. Restringeremo per-

tanto la nostra attenzione ai lavori chehanno condotto direttamente alla dimo-strazione.

Nel 1913 George D. Birkhoff dellaHarvard University apportò dei mi-

glioramenti alla tecnica di riduzione diKempe e riuscì a dimostrare che certeconfigurazioni, di maggiori dimensionidi quelle di Kempe, sono riducibili. Phi-lip Franklin del Massachusetts lnstituteof Technology utilizzò alcuni dei risultatidi Birkhoff per dimostrare che una cartache richiede cinque colori deve avere al-meno 22 paesi, ossia che una carta conmeno di 22 paesi è colorabile con quat-tro colori. Il metodo di Birkhoff fu per-fezionato a opera di diversi matematicinel periodo fra il 1913 e il 1950. Durantetale periodo le configurazioni riducibilifurono utilizzate soprattutto per miglio-rare il risultato di Franklin: nel 1950 si èdimostrato che ogni carta con meno di36 paesi può sempre essere colorata conquattro colori.

Benché le ricerche in questo senso di-mostrassero che molte configurazioni so-no riducibili, l'insieme di tutte le confi-gurazioni di cui fino al 1950 si era dimo-strata la riducibilità non si avvicinavaneanche a un insieme inevitabile. Solopochi matematici avevano costruito in-siemi inevitabili di configurazioni e c'erapoca speranza che il loro lavoro potesseportare a un insieme inevitabile di confi-gurazioni riducibili.

Heinrich Heesch dell'Università diHannover sembra sia stato il primo ma-tematico dopo Kempe ad affermare pub-blicamente che la congettura dei quattrocolori avrebbe potuto essere dimostrataqualora si fosse trovato un insieme inevi-tabile di configurazioni riducibili. Heesch,che cominciò le sue ricerche sulla conget-tura nel 1936, apportò numerosi contri-buti di rilievo alla teoria esistente. Nel1950 egli stimò che le configurazioni ri-ducibili nell'(allora) ipotetico insieme i-nevitabile sarebbero state di certe dimen-sioni ristrette e in numero di 10 000 circa.

Le dimensioni delle configurazionidebbono essere fatte oggetto di attentaconsiderazione, seguendo questo approc-cio al problema dei quattro colori. Nelcorso di un secolo, da quando Kempeper la prima volta introdusse l'idea dellariducibilità, sono stati sviluppati certi me-todi standard per esaminare le configu-razioni, in modo da determinare se essesono riducibili o meno. L'uso dt questimetodi per mostrare la riducibilità diconfigurazioni di grandi dimensioni ri-chiede l'esame di un numero altissimo didettagli, e appare possibile solo da parte diun elaboratore elettronico. Ogni configu-razione è circondata da un anello di confi-nanti; la dimensione dell'anello, ovveroil numero dei paesi che formano l'anellointerno alla configurazione, ha un'in-fluenza diretta sulla difficoltà di dimo-strare la riducibilità della configurazione.Quando si cerca di costruire un insiemeinevitabile di configurazioni riducibili esi scopre che una particolare configura-zione non è riducibile, spesso la si può

Le carte «normali» sono state definite da Al-fred Bray Kempe. che nel 1879 pubblicò unadimostrazione errata del teorema dei quattrocolori. Una carta è normale se in essa nonfigura alcun paese che circondi completamen-te uno o più paesi e se in un punto della cartanon si incontrano mai più di Ire paesi. Lacarta qui disegnata non è normale, poiché ilpaese A racchiude altri tre paesi. Kempe di-mostrò correttamente che, se il teorema fossestato dimostrato per le carte normali, sarebbestato vero anche per tutte le carte, e così gli au-tori, nella loro ricerca sul teorema, hanno pre-so in considerazione solamente carte normali.

sostituire con una o più altre configura-zioni, configurazioni di solito con anellodi maggiori dimensioni. Sostituendo unaconfigurazione con un'altra il cui anellocontiene un vertice in più, tuttavia, siaumenta di molto la difficoltà della pro-cedura di valutazione della riducibilità, ecorrispondentemente aumenta anche iltempo necessario all'elaboratore per e-spletare tale procedura. Questo, in parte,anche perché il numero delle colorazioniproprie distinte dei vertici del nuovo a-nello è circa tre volte superiore al nume-ro delle colorazioni dei vertici nell'anellooriginale. Inoltre, i programmi per valu-tare la riducibilità considerano ogni pos-sibile colorazione più volte. Nel 1950 ledifficoltà di computazione sembravanoescludere la possibilità di produrre un in-sieme inevitabile di configurazioni e didimostrare che ciascuno dei suoi elemen-ti fosse riducibile.

L'introduzione di elaboratori numerici

L' ad alta velocità, tuttavia, rese possi-bile tecnicamente affrontare questi pro-blemi. Heesch formalizzò i metodi notiper dimostrare la riducibilità delle confi-gurazioni, e osservò che almeno uno diessi (una generalizzazione diretta del me-todo usato da Kempe) era in linea diprincipio una procedura sufficientemen-te meccanica per poter essere espletatada un elaboratore. Karl Dúrre, un allie-vo di Heesch, scrisse allora un program-ma per elaboratore che utilizzava talemetodo per dimostrare la riducibilità del-le configurazioni. Quando tale program-ma ha successo, nel dimostrare la riduci-bilità di una configurazione, allora quel-la configurazione è sicuramente riducibi-le, ma un risultato negativo mostra solo

56

57

che quel particolare metodo non è sul li- questo caso il grafo duale è una trian- fatti, invece, progressi analoghi nella ri-ciente per dimostrare la riducibilità dellaconfigurazione che, se esaminata con al-tri metodi, potrebbe anche dimostrarsiriducibile. In alcuni casi, quando fallivail programma di Dtirre, ha avuto succes-so Heesch, che riusciva a dimostrare lariducibilità delle configurazioni sfruttan-do dati generati dall'elaboratore ed ef-fettuando calcoli ulteriori basati su unatecnica più potente, che era stata svilup-pata da Birkhoff.

Heesch descriveva le configurazioni inuna forma opportuna. Cominciava conil trasformare la carta originale in quellache i matematici chiamano una formaduale: un grafo piano in cui ogni verticedel grafo rappresenta un paese e ognisegmento di retta fra due vertici rappre-senta un confine. Per ottenere un grafoduale di una carta, si segna la capitale inciascun paese della carta e quindi, ogni-qualvolta due paesi sono confinanti, siuniscono le loro capitali con una stradache passa attraverso il confine comune(si veda l'illustrazione di pagina 61). Poisi cancella tutto, lasciando solo le capita-li (che si chiamano vertici) e le strade(chiamate lati) che si sono aggiunte. Que-sti vertici e questi lati formano il grafoduale della carta originale. I lati di ungrafo dividono il piano in regioni chesono chiamate facce. Se la carta origina-le è normale (e solo carte normali debbo-no essere prese in considerazione nelladimostrazione del teorema dei quattrocolori), tutte le facce sono triangolari. In

La carta degli stati orientali degli USA è normale, ma la cartacompleta degli USA non lo è: Utah, Colorado, Arizona e New Mexicosi incontrano in un unico punto. (Si noti che neanche i 48 stati

12. Il risultato, un po' sorprendente, di-pende dal fatto che il grafo è tracciatonel piano e dal fatto che si tratta di unatriangolazione. Non è molto importanteil fatto che la somma sia 12 piuttosto cheun altro numero, ma è di estrema impor-tanza, invece, che per ogni triangolazio-ne nel piano la somma delle cariche ri-sulti sempre positiva.

Supponiamo ora che le cariche, in taletriangolazione, vengano ridistribuite, tra-sferite di qua e di là, ma sempre senzache il sistema nel suo complesso perda oguadagni qualche carica. In particolare,supponiamo che una carica positiva siatrasferita da qualcuno dei vertici (di gra-do cinque) a carica positiva, verso qual-cuno dei vertici (principali) a carica ne-gativa. Certamente non è possibile, conqueste operazioni, cambiare la somma(positiva) delle cariche, ma possono cam-biare i vertici a carica positiva; per esem-pio, certi vertici di grado cinque possonoperdere tutta la carica positiva (scarican-dosi), mentre certi vertici principali pos-sono ricevere tante cariche da risultarealla fine, positivi (sovraccaricandosi). Aseconda della procedura di scaricamento,o di ridistribuzione, scelta, risultano sca-richi o sovraccarichi vertici differenti.

Data una procedura di scaricamentocompletamente specificata, su un grafoarbitrario, è tuttavia possibile stendereuna lista finita di tutte le configurazioniche, a scaricamento operato, hanno ver-tici a carica positiva. (Ovviamente, cia-scuna di queste configurazioni può esse-re ripetuta un numero imprevedibile divolte.) In altre parole, cariche positivepossono occorrere solo entro questo in-sieme finito di configurazioni. Dal mo-mento che la carica totale è comunquepositiva, esisteranno sempre vertici a ca-rica positiva. Pertanto, poiché in questoelenco di configurazioni sono inclusi tut-ti i possibili ricettacoli di cariche positi-ve, ogni triangolazione nel piano devecontenere almeno una di queste configu-razioni. Questo processo di generazionedi una lista di configurazioni specificheda una carta arbitraria funziona perché èpossibile determinare l'aspetto di piccolipezzi della carta anche senza sapere laforma della carta nella sua completezza.

Nella dimostrazione del teorema deiquattro colori il fine di questo sca-

ricamento dei vertici positivi è quello ditrovare una procedura che descriva esat-tamente come trasferire le cariche in mo-do tale da assicurarsi che ogni vertice acarica positiva, nella configurazione ri-sultante, debba o appartenere a una con-figurazione riducibile o essere adiacentea una di esse. Dal momento che le confi-gurazioni evidenziate da questa procedu-ra debbono formare un insieme inevita-bile, se esse sono anche riducibili la con-gettura dei quattro colori è dimostrata.Ovviamente, se non tutte le configura-zioni risultanti sono riducibili, allora nonè stato fatto alcun progresso reale. Ineffetti, l'insieme inevitabile di Kempe puòessere considerato come quell'insieme cherisulta dalla procedura «vuota», quella

golazione. Il numero dei lati che concor-rono in un vertice particolare (nel grafoduale) è detto il grado del vertice ed èuguale al numero dei paesi confinanticon il paese (nella carta originale) rap-presentato da quel vertice. Un cammino,costituito da una successione di lati cheparta e arrivi sempre sullo stesso verticesenza mai incrociare se stesso, separa ilgrafo in due parti: l'interno e l'esterno.Tale cammino viene detto circuito.

Nel vocabolario dei grafi duali unaconfigurazione è una parte di una trian-golazione che consiste di un insieme divertici, più tutti i lati che li congiungono.Il circuito di frontiera, che consiste ditutti i vertici adiacenti alla configurazio-ne e dei lati che li congiungono, si defi-nisce come l'anello della configurazione.(L'anello nel grafo corrisponde all'anellodi regioni che limita la configurazionenella carta originale.) Le configurazionisono spesso descritte dalla lunghezza deiloro anelli: una configurazione con anel-lo di dimensione 6, ad esempio, è unaconfigurazione il cui circuito di frontieraha esattamente sei vertici.

Con il lavoro di Heesch la teoria delleconfigurazioni riducibili sembrava assaiben sviluppata. Benché da allora sianostati apportati dei miglioramenti ai me-todi per la dimostrazione di riducibilità,tutte le idee sulla riducibilità necessarieper la dimostrazione del teorema deiquattro colori furono comprese verso lafine degli anni sessanta. Non erano stati

TI lavoro di Kempe dimostra che unatriangolazione, che rappresenti una

carta pentacromatica minimale, non puòincludere vertici con meno di cinque con-finanti. Pertanto nel seguito, per sempli-cità, useremo il termine «triangolazione»per indicare una triangolazione priva divertici di grado inferiore a cinque. Seassegnarno il numero di carica 6 — k aogni vertice di grado k (cioè, con k con-finanti), allora a vertici di grado superio-re a 6 (vertici principali) sono assegnatecariche negative e i soli vertici di gradocinque possiedono carica positiva. Risul-ta dal lavoro di Kempe che la somma deinumeri assegnati ai vari membri di unaqualunque triangolazione è esattamente

cerca di insiemi inevitabili di configura-zioni. Heesch aveva introdotto un meto-do per la ricerca di insiemi inevitabili diconfigurazioni (non necessariamente ri-ducibili) che ha delle analogie con il tra-sferimento di una carica in una rete elet-trica, ma non ha trattato l'idea della ine-vitabilità con lo stesso entusiasmo dell'i-dea di riducibilità. Quel metodo di «sca-ricamento», apparso per la prima volta informa piuttosto rudimentale nel lavorodi Heesch, si è dimostrato tuttavia cru-ciale in tutta la ricerca successiva sugliinsiemi inevitabili. In forma molto piùsofisticata è divenuto l'elemento centralenella dimostrazione del teorema dei quat-tro colori: quindi lo esporremo in modoabbastanza particolareggiato.

contigui costituiscono una carta in senso proprio, poiché il Michigan ècostituito di due regioni che non sono connesse.) Le carte nell'illu-strazione in basso di pagina 56 sono normali, ma non quelle in alto.

Kempe ha dimostrato che questo insieme di quattro configurazioni è «inevitabile»: ogni cartanormale, cioè, include come propria parte almeno uno degli elementi dell'insieme. Le configura-zioni che sono elementi dell'insieme sono: un paese con due confinanti (a), un paese con tre (b);un paese con quattro (c) e un paese con cinque (d). Nessun paese può avere zero o un confi-nante, perché in una carta normale non sono ammesse le isole, né paesi inclusi in un altro.

in cui non si spostano affatto le cariche.Un esempio di procedura di scarica-

mento, piuttosto semplice, con l'insiemeinevitabile a essa associato, può renderepiù chiare queste idee. Si consideri la

procedura che trasferisce 1/5 di unità dicarica da ciascuno dei vertici di gradocinque a ciascuno dei suoi confinantiprincipali (si veda l'illustrazione in alto apagina 62). Il corrispondente insieme i-

A

C

A

C'

Kempe ha mostrato che per dimostrare il teorema dei quattro colori è sufficiente provare chenon può esistere una carta minimale pentacromatica. Una carta pentacromatica minimale è unacarta, con il minimo numero di paesi, che richiede cinque colori, tale cioè che ogni carta piùpiccola (con un minor numero di paesi) può essere colorata con quattro colori o meno. Kempeha cercato di dimostrare l'impossibilità di una carta pentacromatica minimale mostrando chenessuna delle configurazioni nel suo insieme inevitabile può esistere in una carta pentacromaticaminimale. Ogni carta tracciata nel piano contiene una di queste configurazioni, cosicché, setutte le argomentazioni di Kempe fossero state corrette, egli avrebbe dimostrato il teorema. Ladimostrazione (corretta) di Kempe dell'impossibilità. per un paese D con tre confinanti (a sini-

stra) di essere parte di una carta pentacromatica minimale, procede in questo modo. Si combiniD con uno dei suoi confinanti, C, in modo da formare un nuovo paese C (a destra). La nuovacarta ha un numero di paesi minore di quello nell'originale carta pentacromatica minimale epertanto può colorarsi con quattro colori. Si diano a tutti i paesi della carta originale, tranne D,i colori che asrebbero nella colorazione a quattro colori della carta più piccola. D allora può

essere colorato con il colore non usato per A, B e C. Quindi la carta originale può esserecolorata con quattro colori: non si tratta di una carta pentacromatica minimale. Analogamentesi dimostra che un paese con due confinanti non può far parte di una carta pentacromaticaminimale. Per quattro confinanti la dimostrazione è descritta nell'illustrazione della pagina seguente.

58

59

Un grafo duale (in colore) mostra i paesi e i confini della carta origi-nale (a sinistra). Il grafo duale è costruito segnando un vertice all'in-terno di ciascun paese della carta originale e quindi connettendo ivertici di ogni coppia di paesi confinanti con un lato che passa attra-verso il loro confine comune. Questi lati possono sempre essere

tracciati come segmenti di retta, in modo da dividere il piano in faccepoligonali. Se la carta è normale, le facce sono triangoli e il grafo èuna triangolazione del piano. Il numero di lati che si incontrano in unvertice è il grado del vertice ed è uguale al numero dei paesi confi-nanti con il paese (nella carta originale) rappresentato dal vertice.

Una configurazione riducibile è una disposizione di paesi che non può far parte di una cartapentacromatica minimale. Per dimostrare il teorema dei quattro colori, Kempe cercò di mostra-re che le quattro configurazioni nel suo insieme inevitabile sono riducibili. Kempe non ebbesuccesso, perché non riuscì a dimostrare che un paese con cinque confinanti costituisce unaconfigurazione riducibile. Gli autori sono riusciti a dimostrare il teorema costruendo un insiemeinevitabile di circa 1500 configurazioni riducibili. Il concetto di riducibilità è derivato dallacorretta dimostrazione di Kempe dell'impossibilità, per un paese con quattro confinanti(diciamo, E), di essere parte di una carta pentacromatica minimale. Come nel caso di un paesecon tre confinanti (si veda l'illustrazione in basso della pagina precedente) E può essere combi-nato con uno dei suoi confinanti in modo da stabilire una colorazione a quattro colori per tuttigli altri paesi nella carta (in alto). Se i quattro paesi confinanti con E sono stati colorati con me-no di quattro colori, a E può essere assegnato uno dei colori non utilizzati, per dimostrare che lacarta è colorabile con quattro soli colori. Altrimenti si considerino i colori di una coppia di paesida parti opposte rispetto a E. O esiste una successione di paesi, colorati con quei due colori, checonduce dall'uno all'altro, oppure tale successione non esiste. In questo esempio A e C sonoconnessi da una successione di paesi a colore scuro o grigio scuro, ma B e D non sono connessida alcuna successione di paesi colorati in grigio chiaro o in chiaro. Un teorema afferma che, seambedue le coppie di paesi sono connesse da simili successioni, allora le successioni hanno unpaese in comune. Onesto, chiaramente ; è impossibile, poiché paese comune dovrebbe essere

colorato con due colori diversi. Pertanto almeno una coppia di paesi (qui B e D) non sarà legatada un percorso di paesi colorati con i colori della coppia. I paesi colorati in grigio chiaro o inchiaro che formano un percorso a partire da B sono U, V, W e X. Si invertano i colori dei paesidi questo gruppo. In questo caso si faccia diventare di colore chiaro il colore dei paesi in grigiochiaro e di colore grigio chiaro quello dei paesi in chiaro (sotto). Ora il paese privo di colora-zione ha dei vicini colorati con tre soli colori, cosicché a esso può essere assegnato ilquarto colore (grigio chiaro, nel nostro caso), in modo da presentare una colorazione aquattro colori per la carta pentacromatica minimale. In altre parole, si può vedere così cheun paese con quattro confinanti non può essere parte di una carta pentacromatica minimale.

nevitabile consta di due configurazioni.L'una è una coppia di vertici di gradocinque uniti da un lato, e l'altra è for-mata da un vertice di grado cinque unitoda un lato a un vertice di grado sei.

Queste configurazioni sono ottenutenel modo seguente. Un vertice di gradocinque può risultare solo positivo, allafine di questa procedura, se almeno unodei suoi confinanti non è principale, cosìche il vertice inevitabilmente deve con-servare carica positiva; il vertice o ha unconfinante di grado cinque (situazioneche corrisponde alla prima configurazio-ne nell'insieme) o un confinante di gradosei (seconda configurazione).

Un vertice di grado sei parte senzacarica, quindi non ne può ricevere alcu-na. Un vertice di grado sette potrebbediventare positivo solo se avesse almenosei vertici confinanti di grado cinque; seha almeno cinque confinanti di tal fatta,due di essi sono uniti da un lato (pri-ma configurazione dell'insieme inevita-bile). Un vertice di grado otto o supe-riore non può diventare positivo neanchese tutti i vertici con esso confinanti sonodi grado cinque, cosa che si può vedereesaminando un vertice di grado otto. Lasua carica, infatti, è meno due, e lamassima carica positiva che può ricevereè otto volte 1/5, cioè 1 e 3/5. Pertanto ledue configurazioni (non riducibili) for-mano un insieme inevitabile; quindi, datoche questi calcoli si applicano a qualun-que triangolazione nel piano (senza verti-ci di grado inferiore a cinque), un ele-mento dell'insieme delle due configura-zioni si troverà in ogni triangolazione delpiano di tal fatta.

Nel 1970 uno di noi (Haken) venne aconoscenza di certi metodi per mi-

gliorare le procedure di scaricamento, ecominciò a sperare che tali miglioramen-ti potessero portare a una dimostrazionedella congettura dei quattro colori. Ledifficoltà, tuttavia, apparivano ancoraenormi. In primo luogo, si credeva checonfigurazioni molto grandi (con anellidi confinanti contenenti fino a 18 vertici)dovessero essere incluse in qualunque in-sieme inevitabile di configurazioni ridu-cibili. Il che significava che il problemapoteva andare al di là delle possibilitàdegli elaboratori esistenti: su un elabora-tore, infatti, valutare configurazioni dipiccole dimensioni (anelli fino a 11 verti-ci) dal punto di vista della riducibilitàera ragionevolmente semplice, ma il tem-po necessario all'elaboratore andava au-mentando di un fattore quattro per ogniincremento di un'unità nelle dimensionidell'anello. Per peggiorare la situazione,aumentavano con la stessa rapidità lequantità di memoria richieste all'elabo-ratore. Applicato programma di Diirrca una configurazione particolarmente dif-ficile, con un anello di 14 vertici, civollero 26 ore per dimostrare che la con-figurazione non soddisfaceva neanche lapiù meccanica definizione di riducibilità(quella formulata con il minimo numerodi istruzioni di macchina). Anche se iltempo medio richiesto per l'esame di una

configurazione con anello di 14 verticiera solo di 25 minuti, esaminare unaconfigurazione con anello di 18 verticiavrebbe richiesto 4 4 x 25 minuti, cioè piùdi 100 ore di utilizzazione dell'elaborato-re, e una capacità di memoria superiorea quella disponibile su qualunque deglielaboratori esistenti.

Altra grossa difficoltà era che nessunosapeva in realtà quante configurazioniriducibili sarebbero state necessarie performare un insieme inevitabile. Sembra-va verosimile che il numero delle confi-gurazioni fosse nell'ordine delle migliaia,ma non era stato stabilito alcun limitesuperiore. Supponiamo che su un calco-latore con sufficiente capacità di memo-ria siano necessarie 100 ore per dimo-strare che una configurazione con anellodi 18 vertici è riducibile. Se nell'insiemeci sono 1000 configurazioni di tal fat-ta, ci vorrebbero 100 000 ore, cioè piùdi Il anni, su un elaboratore molto gran-de, per dimostrare che sono riducibili. Atutti i fini pratici, se l'insieme fosse statotanto grande, la dimostrazione avrebbedovuto attendere elaboratori molto piùveloci di quelli attualmente disponibili.

Anche se il teorema potesse essere di-mostrato trovando un insieme inevitabiledi configurazioni riducibili, la dimostra-zione non soddisferebbe quanti cercanol'eleganza matematica e, quel che permolti matematici sarebbe ancora peggio,nessuno sarebbe in grado di verificarecon carta e matita la riducibilità delleconfigurazioni dell'insieme esibito. Nel1970, tuttavia, molti esperti del proble-ma dei quattro colori erano del tuttopessimisti sulla possibilità di trovare unadimostrazione breve. Il problema avevaricevuto molta attenzione, dal giorno in

cui era stato formulato, oltre 100 anniprima, e molte strade erano state tentateper risolverlo, ma, benché qualcuna a-vesse portato a risultati importanti inaltre branche della matematica, nessunaaveva mai portato a una dimostrazionedel teorema dei quattro colori.

Quando cominciammo il nostro lavo-ro sul problema, nel 1972, ci sentivamosicuri che le tecniche disponibili non ciavrebbero consentito una dimostrazionesenza l'uso dell'elaboratore. Avevamoanche grossi dubbi che ci potessero por-tare a una dimostrazione qualunque, pri-ma che fossero sviluppati elaboratorimolto più potenti. Pertanto il nostro pri-mo passo, nell'affrontare il problema ditrovare un insieme inevitabile di configu-razioni riducibili, fu quello di determina-re se ci fosse o meno una qualche spe-ranza di trovare un tale insieme con con-figurazioni i cui anelli fossero di dimen-sioni abbastanza piccole perché il temponecessario all'elaboratore per le dimo-strazioni di riducibilità rimanesse entro ilimiti del ragionevole. Per la natura stes-sa della questione, era chiaro che nonavremmo dovuto cominciare a esaminarela riducibilità di tutte le configurazioniconsiderate; altrimenti, il tempo spesoper la stima sarebbe stato superiore altempo atteso, necessario per assolvere ilcompito nella sua totalità.

Qui un'idea di Heesch si è dimostrataestremamente utile. Mentre provava lariducibilità delle configurazioni, Heeschosservò un certo numero di fenomenidistintivi che forniscono indizi della pro-babilità di un successo nella riduzione.Esistono, ad esempio, certe condizioniche coinvolgono i confinanti di vertici diuna configurazione, sotto le quali non è

mai stata trovata una configurazione ri-ducibile. Non si è mai trovata configura-zione riducibile che contenesse, ad esem-pio, almeno due vertici, un vertice adia-cente a quattro vertici dell'anello e nes-suna configurazione riducibile più picco-la. Benché non si conosca dimostrazionedel fatto che configurazioni riducibili conquesti ostacoli alla riduzione non possa-no esistere, sembrava prudente assumereche, se si volevano configurazioni riduci-bili, si dovessero evitare tali configura-zioni. Heesch trovò tre grandi ostacolialla riduzione, incluso quello descrittosopra, che possono essere facilmente de-scritti (si veda l'illustrazione in bassonella pagina seguente). Non è stato maidimostrato che una configurazione con-tenente uno di questi ostacoli fosse inqualche modo riducibile.

E facile determinare se una configura-zione contenga un ostacolo alla riduzio-ne o meno e ci sono buone probabilitàche configurazioni prive di ostacoli allariduzione siano riducibili. Se fosse esisti-to un insieme inevitabile maneggevole diconfigurazioni prive di ostacoli alla ridu-zione, avevamo la sensazione che ce nesarebbe stato uno inevitabile, più o me-no delle stesse dimensioni, contenentesolo configurazioni riducibili.

Decidemmo quindi di studiare in primoluogo certi tipi di procedure di scarica-mento, al fine di determinare i tipi diinsiemi di configurazioni senza ostacoliche potevano verificarsi. Per avere unacomprensione di quel che era necessario,anche per questo studio, restringemmoulteriormente il problema a quelle che sidefiniscono configurazioni geografica-mente buone: configurazioni, cioè, chenon contengono i primi due dei tre osta-

60 61

l A r,h,"rimr‘11n .411~

Questo esempio di triangolazione del piano include un vertice di grado otto (quadratino ingrigio), un vertice di grado sette (cerchio grande in grigio), otto vertici di grado sei (cerchi picco-li in grigio), e 15 vertici di grado cinque (cerchi piccoli in nero). Kempe ha dimostrato che ivertici di grado due, tre e quattro sono riducibili, che, cioè, non possono presentarsi in unacarta pentacromatica minimale. Pertanto, al fine di refutare l'esistenza di una carta pentacro-matica minimale, gli autori hanno dovuto considerare solo quelle triangolazioni con vertici digrado superiore al quattro. La «carica» (cifre in colore) di un vertice si definisce come la diffe-renza fra sei e il grado del vertice. Dal momento che le triangolazioni considerate non hannovertici di grado inferiore al quinto, gli unici vertici a carica positiva sono quelli di grado cinque.Non è difficile dimostrare che in ogni carta normale la carica totale è uguale a 12. Ciò implicache, in qualsiasi triangolazione del piano che possa essere coinvolta nella dimostrazione delteorema dei quattro colori, devono esistere vertici a carica positiva (e, cioè, di grado cinque).

Tre ostacoli alla riduzione, osservati da Heinrich Heesch dell'Univer-sità di Hannover. Queste disposizioni di vertici sembra occorrano soloin configurazioni la cui riducibilità non è dimostrabile. Gli autori,pertanto, hanno potuto usare gli ostacoli per identificare, nella lorodimostrazione, aree potenzialmente problematiche. Nei grafi qui trac-ciati le configurazioni sono le disposizioni di vertici uniti da linee innero. Le linee più sottili connettono i vertici dell'anello, o fascia

esterna della configurazione. Le linee tratteggiate connettono verticidella configurazione a vertici dell'anello. Ogni configurazione contie-ne uno degli ostacoli di Heesch alla riduzione: il vertice V (a sinistra)ha quattro confinanti sull'anello della configurazione; il vertice W (alcentro) ha tre confinanti non consecutivi sull'anello della configura-zione; i vertici X e Y (a destra) sono connessi l'uno all'altro e a verticidell'anello, ma hanno solo un altro confinante nella configurazione.

13. it,O#At

teorema, e così il risultato fornito dalnostro programma non fu un insiemeinevitabile, ma piuttosto un elenco delleconfigurazioni che risultavano dalle si-tuazioni più importanti. Anche se nonc'era da aspettarsi che un programma

per elaboratore procedesse con c, -1 mi-nimo di furbizia che è tipico della menteumana, l'enorme velocità dell'elaborato-re rendeva possibile accettare anche certeinefficienze. In ogni caso il programmaera scritto in modo tale che il suo pro-gramma potesse facilmente essere con-trollato direttamente.

Le prime sperimentazioni del program-ma, verso la fine del 1972, ci fornironouna grande quantità di informazioni pre-ziose. In primo luogo, risultò che configu-razioni geograficamente buone di dimen-sioni ragionevoli (con anelli di dimensioninon superiori a 16) si sarebbero trovate vi-cino alla maggior parte dei vertici con cari-ca finale positiva. In secondo luogo, lestesse configurazioni occorrevano abba-stanza di frequente perché l'elenco delleconfigurazioni potesse essere di lunghezzamaneggevole. In terzo luogo, così comeera organizzata in origine, la proceduraal calcolatore dava un risultato troppogrande per poterci lavorare sopra: casisimilari rimettevano in gioco lo stessoargomento troppe volte. In quarto luo-go, nella procedura esistevano chiaramen-te delle falle, poiché c'erano vertici acarica finale positiva nelle cui vicinanzenon era garantita l'esistenza di configu-razioni geograficamente buone. Infine, ilprogramma generò una quantità enormedi informazione nel giro di poche ore dilavoro dell'elaboratore, così che sapeva-mo che sarebbe stato possibile procederespesso ad esperimenti.

Il programma e certi aspetti della pro-cedura di scaricamento andavano modi-ficati, per superare i problemi evidenziatidalle prime prove all'elaboratore. Dalmomento che potevamo conservare lastruttura di base del programma, non fudifficile apportare le modifiche, e unmese più tardi operammo un secondoinsieme di prove. Corretti i problemi piùgrossi, abbiamo avuto così la possibilitàdi percepire problemi più sottili. Con unpo' di studio trovammo la soluzione an-che a questi problemi e apportammo ul-teriori correzioni al programma.

T l dialogo uomo-macchina andò avantiI per altri sei mesi, fino a che nonavemmo la sensazione che la nostra pro-cedura avrebbe dato un insieme di con-figurazioni geograficamente buone in unragionevole arco di tempo. A questo pun-to decidemmo di dimostrare formalmen-te che la procedura avrebbe fornito uninsieme inevitabile finito di configurazio-ni geograficamente buone: dovevamomettere da parte l'approccio sperimenta-le e andare a descrivere la proceduranella sua totalità. Era necessario dimo-strare che erano stati coperti tutti i casi eche quei casi, che non erano trattati dalprogramma, erano effettivamente tantosemplici quanto apparivano.

Con nostra grande sorpresa il compitosi dimostrò estremamente difficoltoso eci portò via più di un anno. Fu necessa-rio formulare definizioni generali dei ter-mini e dimostrare enunciati astratti su diessi. Fu necessario esaminare casi spe-ciali, anche quelli che era poco probabilesi presentassero in pratica: e questo ri-chiese spesso analisi complesse. Infine,nell'autunno del 1974, abbiamo ottenutouna dimostrazione del fatto che un insie-me inevitabile finito di configurazionigeograficamente buone deve esistere, euna procedura per costruire tale insieme,con limiti precisi (anche se molto piùampi del desiderabile) sulle dimensionidelle configurazioni nell'insieme. La pro-cedura escogitata era molto importanteper noi, poiché intendevamo applicarlanella dimostrazione del teorema dei quat-tro colori. (Poco tempo dopo WalterStromquist, che ha fornito contributi no-tevoli alla teoria della riduzione, e cheallora era studente ad Harvard, ottenneuna elegante dimostrazione dell'esistenzadi insiemi inevitabili di configurazionigeograficamente buone. Poiché la dimo-strazione di Stromquist non forniva unmetodo per costruire effettivamente leconfigurazioni nell'insieme, era tuttaviapoco probabile che essa fosse immedia-tamente applicabile alla stessa congettu-ra dei quattro colori.)

Dimostrato che la nostra procedurafunzionava, per configurazioni geografi-camente buone, ancora non sapevamoquanto sarebbe stato complicato portarea termine la procedura stessa. Decidem-mo di provare sul problema ristretto del-le triangolazioni che non hanno coppiedi vertici adiacenti di grado cinque. Sitratta, ovviamente, di una restrizione pe-sante, ma l'insieme inevitabile di configu-razioni geo graficamente buone che otte-nemmo fu decisamente piccolo: solo 47configurazioni e nessuna con anello didimensioni superiori a 16. Ipotizzammoche la soluzione al problema senza restri-zioni fosse 50 volte più complessa (stimache si è dimostrata un po' ottimistica), edecidemmo che c'erano buone ragioniper andare avanti. Agli inizi del 1975modificammo il programma in modo cheproducesse configurazioni senza ostacolipiuttosto che configurazioni geografica-mente buone, e lo spingemmo a ricercareinsiemi in cui più configurazioni avesse-ro anelli di piccole dimensioni. Inserito il

programma, risultarono evidenti certefalle, ma ci fu anche una sorpresa moltopiacevole: sostituendo alle configurazio-ni geograficamente buone quelle senzaostacoli, le dimensioni dell'insieme inevi-tabile raddoppiavano solamente.

A questo punto il programma, in cui

FOUR COLORS

SUFFICE

erano state profuse le nostre idee e varimiglioramenti, per due anni, ha comin-ciato a sorprenderci. Prima, quando con-trollavamo direttamente le analisi pro-dotte dalle versioni iniziali del program-ma, eravamo sempre in grado di predireil loro corso, ma ora l'elaboratore agiva

Qi,t3 4 :..- =

..,Auz2V/7 :!:- ..... ‹

t «.

.1 3 :

coli alla riduzione visti da Heesch.Nell'autunno del 1972 stendemmo un

programma per elaboratore che dovevaattuare la particolare procedura di scari-camento che ci sembrava più ragionevo-le. Non eravamo pronti per dimostrare il

La procedura di scaricamento genera un insieme inevitabile di configurazioni riducibili ridistri-buendo la carica positiva di una triangolazione arbitraria (priva di '.ertici di grado inferiore alquinto), in modo che la carica positiva si venga a trovare solo in configurazioni riducibili. Dalmomento che in ogni carta si trova una carica positiva, un insieme inevitabile può essereformato scegliendo configurazioni che occorrono in ogni tipo di intorno di carica positiva. Seogni configurazione elemento dell'insieme è riducibile, allora non può esistere una carta penta.cromatica minimale e il teorema dei quattro colori è dimostrato. Un esempio di sempliceprocedura di scaricamento è quello di trasferire 1/5 di unità di carica da ciascun vertice a caricapositiva verso ognuno dei suoi confinanti a carica negativa. Alla fine di questo processo unvertice di grado cinque (cerchi in nero) ha carica positiva solo se ha (a) un confinante di gradocinque o (b) un confinante di grado sei (cerchi in grigio), così che è costretto a conservare lacarica. Un vertice di grado sei non diventa mai positivo, poiché, avendo carica iniziale nulla,non riceve mai cariche positive. Un vertice di grado sette, al termine della procedura, ha caricapositiva solo se ha almeno sei confinanti di grado cinque; allora almeno due di essi sarannoadiacenti (a). Vertici di grado superiore al settimo non possono mai ricevere abbastanza carichepositive da compensare la loro carica negativa iniziale. L'insieme inesitabile generato da questaprocedura di scaricamento consiste di un vertice di grado cinque unito, tramite uno spigolo, aun altro vertice di grado cinque (a) e di un vertice di grado cinque unito da uno spigolo a unvertice di grado sei (b). Queste configurazioni non sono riducibili. Se la procedura viene modi-ficata in modo da trasferire 1/3 di unità di carica da ciascun vertice a carica positiva versociascuno dei suoi confinanti a carica negativa, viene generato un insieme leggermente migliore(c, d). Se si trasferisce 1/2 unità di carica, l'insieme risultante è molto vicino a uno di quelliprodotti da una delle prime versioni della procedura di scaricamento escogitata dagli autori.

-=,

Annullo usato dal dipartimento di matematica dell'Università a Urbana-Champaignper celebrare la soluzione del problema dei quattro colori, a opera di due dei suoi membri.

62

63

BANCO

NAPOLIIstituto di Credito e di diritto pubblicoFondato nel 1593Fondi petrIm. e risme: L. 179.772.915.854

* TUTTE LE OPERAZIONIE I SERVIZI DI BANCA

* Sezioni per ilCredito AgrarioCredito FondiarioCredito Industrialee all'Artigianato

* Monte di Credito su Pegno

* Servizi di RicevitoriaEsattoria e Tesoreria

• Direzione Generale in Napoli

• Ufficio di Rappresentanzadella Direzione Generale in Roma

• Oltre 500 filiali in Italia

• Filiali all'estero: Buenos Aires, New York

• Uffici di Rappresentanza all'estero:Bruxelles, Francoforte s M., LondraNew York, Parigi, Tokio (A.I.C.I.-Holding SA.) Zurigo

• Rappresentante per la Bulgaria:VITOCHA-Sofia

CORRISPONDENTI IN TUTTO IL MONDO

come una macchina giocatrice di scacchi.Elaborava strategie complesse, basate sututti gli artifici imparati, e i nuovi ap-procci erano spesso più astuti di quelliche noi avremmo tentato. In un certosenso il programma si stava dimostrandosuperiore non solo nelle parti meccani-che dell'esecuzione, ma anche in certearee intellettuali.

Nell'estate del 1975 pensavamo che cifosse una buona probabilità di tro-

vare un insieme inevitabile di configura-zioni, ciascuna delle quali fosse priva diostacoli e, con ogni probabilità, riduci-bile. Un insieme simile avrebbe pur sem-pre contenuto qualche configurazioneirriducibile, ma avevamo la sensazioneche sarebbe stato sufficiente qualche pic-colo cambiamento nella procedura perpermetterci di sostituirle con configura-zioni riducibili. A questo punto, per laprima volta, dovevamo sottoporre le con-figurazioni a un test di riducibilità.

Cominciammo con lo scrivere un pro-gramma che provasse la riducibilità piùmeccanica, lavorando con il linguaggioassemblatore per l'elaboratore IBM 360dell'Università dell'Illinois. Nell'autun-no precedente si era unito a noi JohnKoch, studente di scienze dei calcolatori,che aveva scelto di scrivere una disserta-zione sulla riducibilità di configurazionicon anelli di piccole dimensioni. (FrankAllaire dell'Università del Manitoba eEdward Swart della Università della Rho-desia stavano conducendo ricerche simi-li, ma noi non ne eravamo al corrente.)Nell'autunno del 1975 Koch aveva scrit-to programmi per valutare la riducibilitàdi tipo più meccanico in configurazionicon anello di dimensioni fino a 11 edera passato a ricerche più generali. Neipochi mesi successivi, con l'aiuto di Koch,modificammo il suo lavoro sulle confi-gurazioni con anello di dimensione 11per ottenere programmi che valutasserola riducibilità di configurazioni con anel-li di dimensioni 12, 13, 14. Infine modi-ficammo ulteriormente questi program-mi al fine di applicare un procedimentopiù generale di riduzione, che era statosviluppato da Birkhoff.

Allora il nostro lavoro sulla proceduradi scaricamento raggiunse un punto mor-to. Per migliorarè il programma eranonecessarie modificazioni strutturali e nonsemplici aggiustamenti di parametri epiccole aggiunte, il che significava rimet-tere pesantemente le mani nel program-ma. Decidemmo pertanto di scartare ilprogramma stesso e di migliorare diret-tamente la procedura di scaricamento,cosa che ci garantiva una maggiore fles-sibilità e consentiva di modificare la pro-cedura localmente ogni volta che fossenecessario. Una scoperta, nel dicembre1975, venne a incoraggiarci: una delleregole che definivano la nostra procedu-ra di scaricamento era troppo rigida ebastava renderla un po' più flessibile peraumentare considerevolmente l'efficaciadi tutta la procedura.

Con la nuova procedura di scarica-mento sembrava che si potesse costruire

64

un insieme inevitabile le cui configura-zioni riducibili fossero più piccole diquelle prodotte dalle procedure preceden-ti. Il tempo richiesto per la dimostrazio-ne sarebbe stato, probabilmente, inferio-re a quello indicato dalle precedenti sti-me. Era del tutto evidente, tuttavia, chesarebbe stato comunque necessario unconsiderevole sforzo di calcolo, per otte-nere anche il migliore insieme inevitabiledi configurazioni riducibili. Edward F.Moore, dell'Università del Wisconsin a-veva sviluppato un metodo potente, percostruire carte che non contenessero pic-cole configurazioni riducibili. Aveva crea-to, per esempio, una carta in cui la di-mensione dell'anello della più piccolaconfigurazione riducibile era 12 (si vedal'illustrazione a pagina 55). Pertanto,qualunque insieme inevitabile di confi-gurazioni riducibili deve avere almenouna configurazione con anello di dimen-sione 12. Il lavoro di Moore stabilisce unlimite inferiore alla dimensione dell'anel-lo, ma noi a quel punto eravamo sicuriche fosse necessaria una dimensione 13,e con tutta probabilità anche una dimen-sione 14. (La nostra dimostrazione provache non sono richieste configurazioni piùampie.)

Nel gennaio 1976, con l'ausilio dellanostra nuova procedura di scarica-

mento, cominciammo a costruire un in-sieme inevitabile di configurazioni ridu-cibili. La versione finale della proceduraaveva un ulteriore vantaggio, per assicu-rare la riducibilità delle configurazionifinali. Essa, infatti, era essenzialmente ingrado di autocorreggersi: il programmaera progettato in modo da identificarezone critiche, configurazioni che appa-rissero resistenti ai tentativi di riduzione,e da modificarsi in modo da spostare lecariche positive in posizioni differenti.Dal momento che stavamo operando laprocedura di scaricamento senza l'elabo-ratore, sapevamo di poter modificare laprocedura stessa, qualora avessimo in-contrato aree critiche.

Cominciammo con un'approssimazio-ne, un passaggio preliminare della nostraprocedura di scaricamento. Consideram-mo ogni caso possibile in cui un verticefosse di necessità positivo, e in ogni casosi esaminavano le vicinanze del verticeper trovare una configurazione senza o-stacoli. Se non ne trovavamo, chiamava-mo critiche quelle vicinanze, il che signi-ficava che la procedura andava modifi-cata, per evitare il problema. Anche quan-do si trovava una configurazione senzaostacoli, tuttavia, non avevamo alcunagaranzia di trovarci di fronte a una con-figurazione riducibile. I nuovi program-mi di riduzione venivano applicati percercare di trovare qualche configurazio-ne senza ostacoli nelle vicinanze, che fos-se anche riducibile. Se non se ne trova-no, classificavamo ancora come critichequelle vicinanze.

Questo metodo per sviluppare un in-sieme inevitabile di configurazioni ridu-cibili (perfezionata la procedura di scari-camento) fu possibile solo grazie a un

altro dialogo con l'elaboratore. Per de-terminare quali intorni fossero critici,era necessario fare un rapido esame inmerito alla riducibilità, rapido sia in ter-mini di tempo-macchina che in terminidi tempo reale. Fortunatamente raramen-te era necessario attendere più di qualchegiorno, per avere i risultati, anche sespesso era necessaria una notevole quan-tità di tempo-macchina. Dal momentoche questa interazione uomo-macchina,di tipo così intensivo, era indispensabileper il nostro lavoro, è giusto spiegare lecircostanze che l'hanno resa possibile.

Benché il nostro accordo per l'uso del-l'elaboratore, allora, ci sembrasse deltutto naturale, poi abbiamo scoperto diessere stati particolarmente fortunati alavorare all'Università dell'Illinois, dovela combinazione di un grande centro dicalcolo e di una politica illuminata inmerito all'uso degli elaboratori a fini diricerca ci hanno fornito un'opportunitàche sembra non sia disponibile pressochéin nessuna altra università e in nessunaltro centro di ricerca. Benché non po-tessimo garantire che il nostro lavoroconducesse a una dimostrazione del teo-rema dei quattro colori, ci furono con-cesse oltre 1000 ore di tempo-macchina,con quello che ci sembra un ammirevoleatto di fede nel valore delle ricerche dimatematica pura. Eravamo informati dalcentro di calcolo che, poiché gli elabora-tori dell'università non erano utilizzati apieno in ogni momento in compiti didat-tici o di ricerca, potevamo essere inseritiin un piccolo gruppo di utenti dell'ela-boratore cui era consentito di dividersi iltempo-macchina non utilizzato. Oggi sap-piamo che questo tipo di politica è statoessenziale per il nostro successo.

Nel giugno del 1976 completammo lanostra costruzione di un insieme inevita-bile di configurazioni riducibili. Il teore-ma dei quattro colori era dimostrato. A-vevamo usato circa 1200 ore in tempo--macchina su tre diversi elaboratori. Laprocedura finale di scaricamento differi-va dalla prima nostra approssimazioneper circa 500 modifiche risultanti dallascoperta di intorni critici. Lo sviluppodella procedura stessa ha richiesto l'ana-lisi diretta (con carta e matita, senza ela-boratore) di circa 10 000 intorni di verti-ci a carica positiva e l'analisi con la mac-china di oltre 2000 configurazioni. Nelladimostrazione finale è stata usata unaparte considerevole di questo materiale,compresa la riduzione di 1482 configura-zioni. Benché la procedura di scarica-mento (senza le riduzioni) possa esserecontrollata con carta e matita nel giro diun paio di mesi, sarebbe virtualmenteimpossibile verificare in questo modo icalcoli delle riduzioni. In effetti, quandoabbiamo mandato il nostro saggio sulladimostrazione all'«Illinois Journal of Ma-thematics», il comitato di redazione hacontrollato direttamente, partendo dallenostre note complete, la procedura discaricamento, ma ha controllato i calcolidi riduzione all'elaboratore, utilizzandoun proprio programma indipendente.

Molti matematici, in particolare quelli

formatisi prima dello sviluppo degli ela-boratori ad alta velocità, si oppongonoal trattare gli elaboratori elettronici co-me normali strumenti matematici. Han-no l'impressione che un'argomentazionesia debole quando non può essere con-trollata, tutta o in parte, direttamente.Da questo punto di vista, la verifica dirisultati come i nostri, attraverso pro-grammi indipendenti per l'elaboratore,non è tanto convincente quanto sarebbeun controllo con carta e matita delledimostrazioni. Le dimostrazioni tradizio-nali dei teoremi matematici sono ragio-nevolmente brevi e prettamente teoreti-che - quanto più potente è la teoria,tanto più elegante la dimostrazione - ericontrollarle a mano è, normalmente, ilmetodo migliore. Ma, anche quando ilcontfollo a mano è possibile, se le dimo-strazioni sono lunghe e piene di calcoli, èdifficile credere che il controllo con cartae matita escluderà ogni possibilità di er-rore. Inoltre, quando i calcoli sono suf-ficientemente di routine, come nella no-stra dimostrazione, è probabilmente piùefficiente controllare programmi permezzo di una macchina che non per mez-zo di calcoli fatti con carta e matita.

Se molti matematici sono imbarazzatidalle dimostrazioni lunghe, può essereperché, fino a tempi molto recenti, essihanno utilizzato solo quel genere di me-todi che producono dimostrazioni brevi.Ancora non sappiamo se sia o menopossibile trovare una dimostrazione bre-ve del teorema dei quattro colori. Sonostate annunciate molte nuove dimostra-zioni, di moderata lunghezza, ma nessu-na di esse è passata indenne al vagliodegli esperti. Benché sia concepibile cheuna di queste dimostrazioni sia valida, èaltresì concepibile che le uniche dimo-strazioni corrette debbano essere basatesu insiemi inevitabili di configurazioniriducibili, e che quindi richiedano calcoliche non possono essere fatti con carta ematita. Noi siamo convinti che esistanoteoremi di grande interesse matematico,la cui dimostrazione sia possibile solograzie a metodi che fanno uso di elabo-ratori. Anche se il teorema dei quattrocolori non è di questo genere, ci forniscecomunque un buon esempio di quel chesi deve fare per dimostrare un teorema diquel tipo, e non c'è alcuna ragione perpensare che non esista un gran numerodi problemi che richiedano questo diver-so tipo di analisi.

La nostra dimostrazione del teoremadei quattro colori suggerisce l'esistenzadi limiti teoretici. Essa implica ancheche nel passato l'importanza dei metodidi calcolo nelle dimostrazioni matemati-che è stata decisamente sottovalutata,mentre è in pratica molto importante peril matematico determinare quali siano ipoteri e i /imiti dei suoi metodi. Speria-mo che il nostro lavoro possa facilitare ilprogresso in questa direzione e che que-sto allargamento del campo delle tecni-che di dimostrazione accettabili giustifi-chi gli enormi sforzi dedicati, nel corsodell'ultimo secolo, alla dimostrazione delteorema dei quattro colori.

65