Teorema celor patru culori: colorarea hărților
Oricât de complicată ar fi o hartă, patru culori sunt întotdeauna suficiente pentru a o colora astfel încât țările cu graniță comună să nu aibă niciodată aceeași culoare. Enunțul este atât de simplu încât un copil îl poate verifica cu creioane colorate, și totuși demonstrarea lui a cerut mai mult de un secol și un calculator. Colorați chiar dumneavoastră o hartă aleatorie, vedeți ce granițe intră în conflict și apoi urmăriți trei metode la lucru, de la o regulă greedy rapidă, care uneori are nevoie de o a cincea culoare, până la o căutare cu backtracking, care se descurcă mereu cu patru. Alege o culoare și dă clic pe țări ca să le colorezi; o graniță devine roșie când doi vecini au aceeași culoare. Țările care se ating doar într-un colț pot avea aceeași culoare. Sau lasă calculatorul să o facă: alege o metodă și apasă Rezolvă ca să urmărești cum lucrează, sau Pas ca să vezi câte o mutare pe rând. Minim de culori verifică dacă harta aceasta s-ar descurca cu trei sau chiar două culori. Hartă nouă desenează o altă hartă, iar Arată vecinii desenează rețeaua țărilor care au o graniță comună.
Cum funcționează
- Alegeți numărul de țări și apăsați Hartă nouă sau începeți cu harta afișată.
- Alegeți o culoare și dați clic pe țări pentru a le colora, urmărind granițele roșii, acolo unde vecinii intră în conflict.
- Alegeți o metodă și apăsați Rezolvă sau Pas pentru a o vedea colorând harta, apoi apăsați Minim de culori pentru a afla de câte culori are nevoie această hartă.
De la hărți la grafuri
Puneți un punct în fiecare țară și uniți două puncte atunci când țările lor au o graniță comună. Harta devine un graf, iar colorarea hărții este același lucru cu colorarea punctelor astfel încât punctele unite să difere. Deoarece hărțile sunt desenate pe o foaie plană, aceste grafuri sunt planare: pot fi desenate fără linii care se intersectează. Țările care se întâlnesc într-un singur punct, ca patru pătrate într-un colț, nu sunt vecine. Teorema celor patru culori spune că orice graf planar poate fi colorat cu patru culori. Activați Arată vecinii pentru a vedea graful hărții curente.
Trei moduri de a colora
Colorarea greedy ia țările pe rând, întâi pe cele cu cei mai mulți vecini, și îi dă fiecăreia prima culoare pe care vecinii ei nu au folosit-o. Este rapidă, dar miopă, iar pe unele hărți ajunge la o a cincea sau chiar a șasea culoare. DSATUR, inventat de Daniel Brélaz în 1979, alege mereu ca următoare țara ai cărei vecini au deja cele mai multe culori diferite, ceea ce de obicei evită această capcană. Backtrackingul încearcă culorile pe rând și, când unei țări nu i-a mai rămas niciuna, anulează alegerile cele mai recente și încearcă din nou; găsește întotdeauna o colorare cu patru culori, uneori după multe reveniri.
Întrebări frecvente
De ce sunt patru culori întotdeauna suficiente?
Nimeni nu a găsit o explicație scurtă. Demonstrația lui Kenneth Appel și Wolfgang Haken din 1976 a arătat că orice hartă trebuie să conțină una dintre 1.936 de configurații mici și că fiecare dintre acestea poate fi eliminată, colorarea putând fi apoi restabilită; verificarea tuturor a necesitat peste o mie de ore de calcul pe computer. O demonstrație pe calculator mai simplă, a lui Neil Robertson, Daniel Sanders, Paul Seymour și Robin Thomas, din 1996, are nevoie de 633 de configurații, iar în 2005 Georges Gonthier a verificat complet o demonstrație cu asistentul de demonstrații Coq.
Există hărți care au nevoie de toate cele patru culori?
Da. Patru țări care se ating fiecare cu celelalte trei, ca o țară înconjurată de un inel de alte trei, au nevoie de patru. Multe hărți se descurcă însă cu trei, iar Minim de culori verifică acest lucru pentru harta de pe ecran. A decide în general dacă o hartă poate fi colorată cu trei culori este o problemă dificilă, NP-completă, deși patru culori sunt întotdeauna suficiente.
De ce folosește uneori metoda greedy cinci culori?
Colorează fiecare țară o singură dată și nu se răzgândește niciodată. O alegere timpurie poate lăsa o țară ulterioară înconjurată de toate cele patru culori, iar singura ieșire este o a cincea. Backtrackingul, în schimb, s-ar întoarce și ar schimba alegerile anterioare.
Este teorema adevărată și pe alte suprafețe?
Pe sferă, da: este același lucru ca planul. Pe tor, suprafața unei gogoși, unele hărți au nevoie de șapte culori, iar șapte sunt întotdeauna suficiente, după cum a arătat Percy Heawood. Dacă țările pot fi formate din mai multe bucăți separate, ca o națiune cu colonii, patru culori nu mai sunt suficiente.
Se trimite ceva către un server?
Nu. Harta, metodele de colorare și verificarea rulează în browserul dumneavoastră. Setările dumneavoastră rămân în stocarea locală a acestui browser.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Mergi la editor