TEOREMA CELOR PATRU CULORI

Publicat în 30. 05. 2025 de Iuliana Ghinea

Tot ce e gândire corectă este sau matematică
sau susceptibilă de matematizare.
Grigore Moisil
       Este binecunoscut faptul că marile probleme ale matematicii, cum ar fi Marea Teoremă a lui Fermat sau Conjectura lui Goldbach, au contribuit enorm la dezvoltarea acestei ştiinţe. Din eforturile matematicienilor (timp de zeci sau chiar sute de ani) de a găsi o rezolvare la întrebări în aparenţă simple s-au născut noi discipline în matematică, cu aplicaţii spectaculoase.
      Problema celor patru culori are toate valenţele unei probleme de mare “carieră”: în primul rând formularea ei este extrem de simplă, nu presupune cunoştinţe matematice; în al doilea rând, ea a rămas nerezolvată timp de peste un secol, fiind surprinzător de grea şi a suscitat preocuparea multor matematicieni de prestigiu.
      În 1852 un geograf din Edinburgh (istoria nu i-a reţinut numele) l-a informat pe prietenul său, student în matematici, că foloseşte cel mult patru culori pentru o hartă împărţită în regiuni, fără ca două regiuni vecine să aibă aceeaşi culoare (precizăm că este vorba despre hărţi plane, cu regiuni închise, iar “vecine” sunt regiunile cu o linie de frontieră comună; două regiuni care se întâlnesc într-un număr finit de puncte nu sunt considerate vecine).
    Tânărului matematician, pe nume Francis Guthrie, i-au plăcut cele aflate şi a cerut informaţii mai ample, însă geograful l-a încredinţat că acest procedeu e foarte răspândit şi aplicat pretutindeni din cauza economiei care-l prezintă. Răspunsul nu a fost mulţumitor pentru Guthrie ; el şi-a propus să demonstreze acest fapt dar nu a reuşit.
    Fratele său, Frederick, studia chimia la Londra şi aflând de problema care-l preocupa pe Francis a cerut ajutorul profesorului August De Morgan, dar nici acesta nu a găsit o demonstraţie satisfăcătoare.
       În câţiva ani, problema a ajuns “la modă” printre matematicieni. Astfel, A. Cayley nefiind nici el capabil să demonstreze valabilitatea teoremei, a propus-o Societăţii Matematice din Londra.
Să trecem în revistă câteva din rezultatele parţiale ale demonstrării teoremei.
Faptul că trei culori nu sunt suficiente pentru colorarea oricărei hărţi plane a fost repede constatat. De Morgan a demonstrat că nu există hartă formată din 5 regiuni astfel încât să fie două câte două vecine, deci aceasta poate fi colorată cu patru culori.
       A. B. Kempe, un avocat din Londra, membru al Societăţii Matematice din Londra şi deosebit de pasionat de matematică a publicat în 1879 un articol în care susţinea că a demonstrat teorema. Raţionamentul lui era deosebit de ingenios, el redusese problema la hărţi normale, adică hărţi în care nu există ţări închise complet în alte ţări şi nici puncte în care se întâlnesc mai mult de trei regiuni. Deşi raţionamentul s-a dovedit incomplet, el conţinea ideile de bază ce au condus la demonstraţia corectă un secol mai târziu. Astfel, oricărei hărţi i se poate asocia un graf în care fiecare regiune este reprezentată printr-un punct şi două puncte vor fi legate printr-o muchie dacă şi numai dacă punctele corespund la două regiuni vecine .
       În acest mod problema colorării regiunilor de pe hartă revine la problema colorării punctelor din graful asociat astfel încât punctele legate printr-o muchie să fie colorate diferit.
Problema celor patru culori a contribuit la cercetări importante în teoria grafurilor, cum ar fi “numerele cromatice ale grafurilor”. Cu ajutorul unui graf special, matematicianul P. J. Heawood a arătat în 1890 că demonstraţia lui Kempe are o eroare nu tocmai uşor de înlăturat.
     Mai târziu, în 1913, matematicianul Ph. Franklin de la Massachusetts Institute of Technology ridică limita numărului de regiuni pentru care problema este rezolvată de la 5 la 21, iar în 1940 Winn reuşeşte să ajungă la 35 de regiuni.
      Un alt rezultat deosebit de interesant se datorează lui P. J. Heawood, care şi-a consacrat 60 de ani din viaţă studierii problemei. Iată-l: probabilitatea de a găsi o hartă cu mai mult de 36 regiuni care să nu poată fi colorată cu patru culori este mai mică decât 10-10000 ! (de remarcat că 1010000 este un număr mai mare decât numărul atomilor din întreaga galaxie …).
     O “teoremă a celor cinci culori” (faptul că cinci culori sunt eficiente pentru a colora o hartă) a fost obţinută relativ uşor; o demonstraţie elementară a acestui rezultat poate fi găsită în “Despre numere şi figuri” de H. Rademacher şi O. Toeplitz.
      Pe la mijlocul sec. XX s-a conturat ideea de rezolvare a problemei prin mărirea numărului de regiuni pentru care patru culori sunt suficiente şi examinarea unor aşa-zise configuraţii inevitabile. Dacă ar fi fost posibil să se producă toate aceste configuraţii şi să se arate că ele pot fi colorate cu patru culori, atunci demonstraţia ar fi fost completă.
     Cea mai eficientă metodă de producere a configuraţiilor s-a dovedit a fi un algoritm implementat pe calculator de W. Haken şi K. Appel , Universitatea Illinois, SUA , care au lucrat aproape 1200 ore şi, în fine, demonstraţia a fost încheiată. Un an mai târziu, folosind o altă procedură de reducere a configuraţiilor inevitabile, F. Allaise de la Universitatea Waterloo, Ontario, CA, a reuşit să obţină demonstraţia teoremei în numai 50 de ore de dialog om-calculator.
     Entuziasmul firesc stârnit în lumea matematicienilor de această reuşită neobişnuită până atunci a fost “temperat” de voci sceptice care susţineau că aceasta nu e o teorema de matematică în sensul clasic. Astfel, T. Tymoczko în articolul “Problema celor patru culori şi semnificaţia ei filozofică” (Journal of Philosophy, 1979) afirmă că teorema exprimă un adevăr a posteriori şi nu a priori, ca orice adevăr matematic. Argumentele sale se bazează în principal pe imposibilitatea de a verifica manual (“cu creionul”) demonstraţia, dat fiind faptul că nu există un unic algoritm care să verifice toate programele posibile pe calculator.
    În replică, E. R. Swart scrie în că inconvenientul semnalat de preopinentul său este aparent, deoarece calculele foarte numeroase efectuate pe calculator erau de rutină, iar programul utilizat poate fi verificat. Sarcina calculatorului a fost copleşitoare prin dimensiuni, sarcină pe care omul ştia cum să o abordeze, dar n-ar fi putut-o termina niciodată.
    A fost prima situaţie memorabilă în urma căreia lumea matematicienilor a trebuit să admită existenţa unor demonstraţii parţial accesibile omului, cât şi dreptul calculatorului de a ne sprijini în stabilirea adevărurilor matematice.

Bibliografie
1. K. Appel, W. Haken – Every Planar Map Is Four Colorable , Bulletin of the American Mathematical Society, 82(1976), 711-712.
2. F. Câmpan – Probleme celebre, Ed. Albatros, Bucureşti, 1972.
3. Gh. Păun – Din spectacolul matematicii, Ed. Albatros, Bucureşti, 1983.
4. L.A. Steen – Mathematicians Today, Twelve Informal Essays, Springer–Verlag, 1978.
5. E.R Swart – The Philosophical Implications of the Four-Color Problem, The American Mathematical Monthly, 87(1980), 697-707.