Teorema celor patru culori explicată

În 1852, un tânăr matematician care colora o hartă a comitatelor Angliei a observat că patru culori păreau suficiente pentru a deosebi comitatele vecine. Putea fi adevărat pentru orice hartă posibilă? Întrebarea a devenit una dintre cele mai celebre probleme ale matematicii, a atras o faimoasă demonstrație greșită care a rezistat unsprezece ani și a fost în cele din urmă rezolvată în 1976 într-un mod care a schimbat ceea ce matematicienii acceptă drept demonstrație.

O hartă cu țări neregulate, colorată cu patru culori astfel încât oricare doi vecini au culori diferite
O hartă cu țări neregulate, colorată cu patru culori astfel încât oricare doi vecini au culori diferite

Întrebarea

Francis Guthrie, fost student al lui Augustus De Morgan, a întrebat dacă orice hartă poate fi colorată cu patru culori astfel încât țările cu graniță comună să primească culori diferite. Două reguli fac întrebarea precisă. Țările trebuie să fie conexe, fiecare dintr-o singură bucată, iar țările care se întâlnesc doar într-un singur punct nu sunt considerate vecine. Trei culori nu sunt, evident, întotdeauna suficiente, deoarece o țară înconjurată de un inel de alte trei care se ating toate are nevoie de o a patra. Întrebarea este dacă este vreodată nevoie de o a cincea.

Hărțile ca grafuri

Marcați un punct în fiecare țară și trasați o linie între două puncte ori de câte ori țările lor au o graniță comună. Rezultatul este un graf și, deoarece harta se află pe o foaie plană, liniile pot fi trasate fără să se intersecteze: graful este planar. A colora harta înseamnă a colora vârfurile acestui graf astfel încât capetele fiecărei muchii să difere. Cel mai mic număr de culori care funcționează este numărul cromatic, iar teorema celor patru culori afirmă că niciun graf planar nu are numărul cromatic mai mare de patru.

Demonstrația eșuată a lui Kempe

În 1879, avocatul și matematicianul Alfred Kempe a publicat o demonstrație. Ideea ei ingenioasă, numită astăzi lanțuri Kempe, este de a schimba între ele două culori de-a lungul unui lanț conex de țări pentru a elibera o culoare acolo unde este nevoie de ea. Demonstrația a fost acceptată timp de unsprezece ani, până când Percy Heawood a găsit o lacună în 1890. Corectura lui Heawood a demonstrat un rezultat mai slab: cinci culori sunt întotdeauna suficiente. Lanțurile lui Kempe au supraviețuit și au devenit un instrument în demonstrația finală.

De ce cinci este ușor

Orice graf planar are un vârf cu cel mult cinci vecini; aceasta rezultă din formula lui Euler, care limitează un graf planar cu n vârfuri la cel mult 3n − 6 muchii. Eliminați un astfel de vârf, colorați restul hărții prin același argument și puneți vârful la loc. Dacă vecinii săi folosesc mai puțin de cinci culori, una este liberă. Dacă le folosesc pe toate cinci, o schimbare de-a lungul unui lanț Kempe eliberează întotdeauna una. Cu patru culori, aceeași schimbare poate eșua, iar aceasta este exact lacuna care i-a scăpat lui Kempe.

Demonstrația pe calculator

În 1976, Kenneth Appel și Wolfgang Haken de la Universitatea Illinois au demonstrat teorema. Ei au arătat că orice hartă conține cel puțin una dintre cele 1.936 de configurații ale unei mulțimi inevitabile și că fiecare configurație este reductibilă: o hartă minimă care ar avea nevoie de cinci culori nu ar putea-o conține. Verificarea reductibilității a durat peste o mie de ore pe calculatoare, mult prea mult pentru a fi verificată manual. Mulți matematicieni s-au simțit stânjeniți de o demonstrație pe care niciun om nu o putea citi în întregime, și a început dezbaterea despre demonstrațiile asistate de calculator.

Wolfgang Haken, care împreună cu Kenneth Appel a demonstrat teorema celor patru culori la University of Illinois în 1976.
Wolfgang Haken, care împreună cu Kenneth Appel a demonstrat teorema celor patru culori la University of Illinois în 1976.

Demonstrații mai simple și verificare completă

În 1996, Neil Robertson, Daniel Sanders, Paul Seymour și Robin Thomas au publicat o demonstrație mai sistematică, cu 633 de configurații, verificată tot pe calculator, dar mai ușor de verificat. În 2005, Georges Gonthier și Benjamin Werner au formalizat întreaga demonstrație în asistentul de demonstrații Coq, astfel încât un program mic, de încredere, verifică fiecare pas logic. Astăzi, teorema celor patru culori este unul dintre cele mai temeinic verificate rezultate din matematică.

Algoritmi de colorare

Găsirea unei colorări cu patru culori pentru o hartă dată este rapidă în practică, dar găsirea numărului minim de culori pentru un graf oarecare este dificilă: a decide dacă trei culori sunt suficiente este o problemă NP-completă. Metodele practice includ colorarea greedy în ordinea descrescătoare a gradelor, DSATUR, care colorează în continuare vârful cel mai constrâns, și căutarea cu backtracking, care explorează alegeri și le anulează când se blochează. Colorarea grafurilor programează examene fără suprapuneri, atribuie frecvențe radio astfel încât emițătoarele vecine să nu interfereze și alocă registre în compilatoare.

Explorați

Deschideți colorarea hărților cu patru culori pentru a genera hărți cu 4 până la 120 de țări, colorați-le manual cu patru culori și urmăriți cum apar conflictele cu roșu. Lăsați colorarea greedy, DSATUR sau backtrackingul să rezolve harta pas cu pas, afișați graful țărilor vecine și aflați numărul minim de culori de care harta are cu adevărat nevoie.

Întrebări frecvente

Îi ajută teorema pe cartografi?

Prea puțin. Hărțile reale sunt de obicei colorate cu mai multe culori, pentru claritate, și includ oceane, lacuri și țări formate din mai multe bucăți, pe care teorema nu le acoperă. Importanța ei este matematică: a impulsionat dezvoltarea teoriei grafurilor și a ridicat întrebarea despre ce se poate considera o demonstrație.

Ce este un lanț Kempe?

Luați două culori, de exemplu roșu și albastru, și o țară colorată cu roșu. Lanțul ei Kempe este mulțimea tuturor țărilor roșii și albastre la care puteți ajunge pornind de la ea, trecând doar prin vecini roșii și albaștri. Schimbarea între ele a roșului și albastrului în tot lanțul păstrează colorarea validă și poate elibera o culoare pentru o țară de lângă lanț.

De ce strică teorema țările formate din mai multe bucăți?

Dacă o țară poate fi formată din regiuni separate care trebuie să aibă toate aceeași culoare, graful vecinătăților nu mai este planar și se pot construi hărți care au nevoie de orice număr de culori până la 12 când fiecare țară are două bucăți, așa cum a studiat Heawood în problema imperiilor.

De ce creează aplicația hărți din puncte?

Fiecare țară este regiunea pătratului mai apropiată de un anumit punct aleatoriu decât de oricare altul, adică o diagramă Voronoi. Astfel rezultă hărți cu aspect realist, cu țări convexe, iar două țări sunt vecine exact atunci când regiunile lor au în comun o porțiune de graniță, lucru pe care aplicația îl calculează precis.

Ești gata să încerci?

Deschide PictorX în browser – fără instalare și fără card de credit.

Deschide colorarea hărților cu patru culori