Teorema celor patru culori

Exemplu de hartă cu patru culori

Teorema celor patru culori este o teoremă matematică care afirmă că, având în vedere o suprafață plană împărțită în regiuni conectate, cum ar fi o hartă politică, patru culori sunt suficiente pentru a colora fiecare regiune, astfel încât regiunile adiacente să nu aibă aceeași culoare. Se spune că două regiuni sunt adiacente dacă au cel puțin o linie de graniță în comun. ^[1] Fiecare regiune trebuie să ocupe și un teritoriu conectat, adică nu trebuie să fie formată din două sau mai multe părți deconectate sau cu prezența exclavelor . ^[2]

Este ușor să găsiți hărți pentru care doar trei culori nu sunt suficiente. Nu este prea dificil să demonstrezi că cel mult cinci sunt suficiente. ^[3] Cu toate acestea, demonstrarea faptului că patru sunt suficiente este deosebit de complexă, atât de mult încât dovada acestei teoreme a impus, printre altele, o utilizare extinsă a computerelor , pentru una dintre primele ori din istoria matematicii .

Istorie

Conjectura a fost prezentată pentru prima dată în 1852 , când Francis Guthrie , student al lui Augustus De Morgan , a descoperit că patru culori erau suficiente pentru a colora o hartă a județelor britanice. Prima publicație pe această temă se datorează lui Arthur Cayley ^[4] .

În anii următori, mulți matematicieni au încercat în zadar să demonstreze teorema. Prima „dovadă”, aclamată, recunoscută de mult ca definitivă, a fost formulată în 1879 de Alfred Kempe ; în 1880 Peter Tait a anunțat că a găsit o altă dovadă a teoremei. În 1890 Percy Heawood a descoperit eroarea care a subminat dovada lui Kempe, la unsprezece ani după formularea sa; în anul următor, de Julius Petersen , dovada lui Tait a fost, de asemenea, recunoscută ca fiind incorectă. Refuzând dovada lui Kempe, totuși, Heawood a dovedit că cinci culori erau suficiente pentru orice hartă.

Dovada definitivă a teoremei pentru doar patru culori a fost furnizată în 1977 de Kenneth Appel și Wolfgang Haken , doi matematicieni de la Universitatea din Illinois, grație unui algoritm computerizat complex.

Dovada se bazează pe reducerea numărului infinit de hărți posibile la configurațiile din 1936 (apoi reduse în continuare la 1476), pentru care validitatea teoremei este verificată caz de caz de către computer. Orice hartă poate fi, de fapt, trasată la un număr finit, deși foarte mare, de topologii „notabile” prin intermediul operațiilor care modifică pozițiile relative ale regiunilor care o constituie, dar nu și proprietățile topologice ale hărții în sine.

Pentru a minimiza posibilitatea de eroare, programul a fost rulat pe două mașini diferite cu doi algoritmi independenți; pentru a finaliza analiza tuturor cazurilor posibile a fost necesar ca computerele să funcționeze mii de ore. În cele din urmă, au fost necesare peste 500 de pagini pentru a transcrie manual toate verificările care au constituit dovada.

Utilizarea revoluționară a algoritmilor computerizați pentru a verifica acuratețea conjecturii a stârnit mari controverse cu privire la fiabilitatea acestor metode. Faptul că dovada s-a bazat pe analiza unei multitudini de cazuri discrete i-a determinat pe unii matematicieni să pună la îndoială validitatea sa efectivă: atât pentru impracticabilitatea unei verificări manuale a tuturor cazurilor posibile, cât și pentru dificultatea de a avea certitudinea că algoritmul a fost implementat corect. Cu toate acestea, în ciuda acuzațiilor de lipsă de „eleganță”, nu s-au găsit niciodată erori în algoritm.

Formularea în teoria graficelor

Teorema poate fi exprimată într-o formă mai ușor de înțeles prin exploatarea teoriei graficelor. În această formulare, vârfurile fiecărui grafic plan pot fi colorate folosind până la patru culori, astfel încât două vârfuri adiacente să nu primească niciodată aceeași culoare. Pe scurt, se poate spune că „fiecare grafic planar este 4-colorabil”. Această reprezentare asociază fiecare regiune a hărții cu un vârf al graficului; două vârfuri sunt conectate printr-o margine dacă și numai dacă cele două regiuni corespunzătoare au un segment de margine în comun.

Generalizare

De asemenea, este posibil să se ia în considerare problema colorării pe o suprafață, mai degrabă decât pe un plan. Problema aplicată sferei este echivalentă cu cea din plan. Pentru suprafețele închise (orientate ca torul sau nedirecționate ca banda Möbius ) de gen pozitiv, numărul maxim de culori necesare depinde de caracteristica Euler $\,\chi$ ${\ displaystyle \, \ chi}$ $\,\care$ a suprafeței, conform formulei:

$p=\left\lfloor {\frac {7+{\sqrt {49-24\chi }}}{2}}\right\rfloor$ ${\ displaystyle p = \ left \ lfloor {\ frac {7 + {\ sqrt {49-24 \ chi}}} {2}} \ right \ rfloor}$ $p = \ left \ lfloor {\ frac {7 + {\ sqrt {49-24 \ chi}}} {2}} \ right \ rfloor$

unde parantezele exterioare indică funcția părții întregi. De exemplu, torul are o caracteristică Euler $\,\chi$ ${\ displaystyle \, \ chi}$ $\,\care$ = 0 și p = 7: prin urmare, vor fi necesare maximum șapte culori pentru a colora orice hartă pe o suprafață toroidală. ^[5]

Singura excepție de la formulă este sticla Klein , care are o caracteristică Euler de 0 și necesită șase culori.

Hărți geografice cărora nu le este aplicabilă teorema

Teorema se aplică hărților împărțite în regiuni conectate și independente reciproc. În hărțile geografice politice există state al căror teritoriu, chiar și cu excepția insulelor, este alcătuit dintr-un set de regiuni neconectate: exemple sunt Alaska ca parte a Statelor Unite și exclava Kaliningrad , aparținând Rusiei, dar complet înconjurată de Polonia și Lituania . În cazuri similare, prin impunerea condiției ca întregul teritoriu al unui stat să fie neapărat de aceeași culoare, premisele care stau la baza teoremei sunt modificate și patru culori pot să nu fie suficiente.

Conceptual, o astfel de constrângere ar genera o hartă non-plană. Să luăm în considerare, de exemplu, o hartă simplificată:

În această hartă, cele două regiuni marcate cu A fac parte din aceeași stare și trebuie să aibă aceeași culoare. Această hartă are nevoie de cinci culori, deoarece cele două regiuni A sunt în totalitate contigue cu alte patru regiuni, fiecare dintre ele fiind adiacentă tuturor celorlalte.

Dacă A ar fi format din trei regiuni, ar putea fi necesare șase sau mai multe culori; prin exploatarea regiunilor neconectate este deci posibilă construirea hărților care necesită un număr arbitrar de mare de culori.

Notă

^ Nu este suficient să aibă în comun doar unul sau mai multe puncte izolate, altfel o figură în formă de plăcintă feliată ar fi un contraexemplu.
^ În realitate, rezultatul rămâne valabil dacă exclava nu se învecinează cu state care în niciun caz nu se învecinează cu teritoriul căruia îi aparține - o condiție care este respectată atât de Italia ( Campione d'Italia este în întregime înconjurată de teritoriul elvețian ), și de Statele Unite ale Americii (Alaska se învecinează numai cu Canada ), care din Rusia ( Kaliningrad se învecinează numai cu Polonia și Lituania ), dar de exemplu nu din Angola (a cărei provincie Cabinda se învecinează, precum și cu Republica Democrată Congo) , care îl separă de restul Angolei, tot cu Republica Congo , care nu se învecinează cu nicio altă provincie angoleză).
^ Trebuie să fim atenți să nu confundăm teorema celor patru culori cu cea mult mai simplă pentru a demonstra că nu pot exista cinci regiuni plane, fiecare dintre ele mărginind cu toate celelalte patru. Diferența substanțială este constituită din imposibilitatea de a exprima într-un mod simplu procedura de urmat pentru diferitele constrângeri, pe măsură ce colorarea continuă. Cu toate acestea, a se vedea teorema celor cinci culori .
^ Vezi articolul „ Despre culorile hărților ”, Proc. Royal Geog. Soc. 1 (1879), p. 259-261.
^ Această formulă, cunoscută inițial sub numele de conjectura lui Heawood , a luat numele teoremei hărții colorate după ce a fost dovedită de Gerhard Ringel și JTW Youngs în 1968 .

Bibliografie

Kenneth Appel, Wolfgang Haken, John Koch, Every Planar map is Four Colorable , 1977, Illinois Journal of Mathematics, vol. 21, pp. 439–567
Kenneth Appel, Wolfgang Haken, Soluția problemei celor patru culori , Scientific American, vol. 237 n. 4 pp. 108-121
Kenneth Appel, Wolfgang Haken, Fiecare hartă plană este o Providență cu patru culori , 1989, RI: American Mathematical Society
Saaty, Kainen, The Four Color Problem: Assalults and Conquest , ISBN 0-486-65092-8

Elemente conexe

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere ale teoremei celor patru culori

linkuri externe

( EN ) Istoria teoremei celor patru culori în MacTutor
( RO ) O actualizare a teoremei celor patru culori de Robin Thomas (fișier PDF din Notificări ale Societății Americane de Matematică , Volumul 45, numărul 7 august 1998)
( RO )Teorema celor patru culori de Robin Thomas
( RO ) O nouă dovadă a teoremei celor patru culori , pe geocities.com . Adus la 21 noiembrie 2007 (arhivat din original la 18 octombrie 2007) . de Ashay Dharwadker

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[1] Nu este suficient să aibă în comun doar unul sau mai multe puncte izolate, altfel o figură în formă de plăcintă feliată ar fi un contraexemplu.

[2] În realitate, rezultatul rămâne valabil dacă exclava nu se învecinează cu state care în niciun caz nu se învecinează cu teritoriul căruia îi aparține - o condiție care este respectată atât de Italia ( Campione d'Italia este în întregime înconjurată de teritoriul elvețian ), și de Statele Unite ale Americii (Alaska se învecinează numai cu Canada ), care din Rusia ( Kaliningrad se învecinează numai cu Polonia și Lituania ), dar de exemplu nu din Angola (a cărei provincie Cabinda se învecinează, precum și cu Republica Democrată Congo) , care îl separă de restul Angolei, tot cu Republica Congo , care nu se învecinează cu nicio altă provincie angoleză).

[3] Trebuie să fim atenți să nu confundăm teorema celor patru culori cu cea mult mai simplă pentru a demonstra că nu pot exista cinci regiuni plane, fiecare dintre ele mărginind cu toate celelalte patru. Diferența substanțială este constituită din imposibilitatea de a exprima într-un mod simplu procedura de urmat pentru diferitele constrângeri, pe măsură ce colorarea continuă. Cu toate acestea, a se vedea teorema celor cinci culori .

[4] Vezi articolul „ Despre culorile hărților ”, Proc. Royal Geog. Soc. 1 (1879), p. 259-261.

[5] Această formulă, cunoscută inițial sub numele de conjectura lui Heawood , a luat numele teoremei hărții colorate după ce a fost dovedită de Gerhard Ringel și JTW Youngs în 1968 .

[1]

[2]

[3]

[4]

[5]

V · D · M Combinatorial
Orientare generală	Combinatorial · Istorie combinatorie · Matematică discretă · Secțiunea 05-XX MSC
Noțiuni introductive	Permutații · Dispoziții · Combinații · Coeficienți binomiali · Partiții de numere întregi · Partiții de mulțimi finite - Identități și bijecții combinatorii
Configurări	Pătrat latin · pătrate magice · Desene Block · geometrii finite · Matroids - mozaicare · Polimini
Teoria graficelor	Copaci · Mers pe grafice ( Eulerian , Hamiltonian ) · Conexiune în grafice - grafice plane · Vopsirea graficelor și teorema celor patru culori ) · hipergrafe · Grafice și grupuri · digraf · Grafic al fluxului de numerar · Plimbări aleatorii pe grafice · omomorfismul graficelor · Algoritmi pe grafice
Combinatorie algebrică	Tabelul lui Young · funcții simetrice - serie de puteri formale · Funcții de generare · Polinoame ortogonale · Părți ale unui grup de structuri combinatorii - Aspecte algebră comutativă combinatorie
Alte domenii	Calculul umbrelor ( secvențe polinomiale de tip binomial · secvențe Sheffer ) - Combinatorial extremal