Schimbă limba

Englishعربى中文DeutschEspañolFrançaisहिन्दीHrvatskiItaliano日本語PortuguêsRomânăРусскийSvenskaTürkçeTiếng Việt

Conectați-vă la Mathigon

sau

Cont nou     Reseteaza parola     

Grafice și rețele
Introducere
Podurile din Königsberg
Strângeri de mână și întâlniri
Graficele planare
Harta de colorat
Problema vânzătorului călător
Programarea problemelor
Grafice în viața de zi cu zi

Acțiune

Resetați Progresul

Acest lucru vă va șterge progresul și datele de chat pentru toate capitolele din acest curs și nu poate fi anulat!

Glosar

Selectați unul dintre cuvintele cheie din stânga ...

Grafice și rețeleHarta de colorat

Timp de citit: ~15 min

Am folosit deja teoria graficului cu anumite hărți. Pe măsură ce mărim, drumurile și podurile individuale dispar și, în schimb, vedem conturul țărilor întregi.

Atunci când colorați o hartă - sau orice alt desen format din regiuni distincte - țările adiacente nu pot avea aceeași culoare. De asemenea, am putea dori să folosim cât mai puține culori diferite.

Unele „hărți” simple, precum o tablă de șah, au nevoie doar de două culori (alb-negru), dar cele mai complexe hărți au nevoie de mai multe.

Când colorați harta statelor din SUA, sunt evident 50 de culori, dar sunt necesare mult mai puține. Încercați să colorați hărțile de mai jos cu cât mai puține culori:

United States

0 colours used

South America

0 colours used

Germany

0 colours used

England

0 colours used

Toate aceste hărți pot fi colorate doar cu patru culori diferite, dar nu este greu de imaginat că alte hărți foarte complicate ar putea avea nevoie de mult mai multe culori. De fapt, unele hărți au cel puțin patru culori, ori de câte ori conțin patru țări toate conectate între ele.

Ca și înainte, putem converti o hartă cu țări și granițe într-un grafic plan: fiecare țară devine și țările care să fie conectate de o margine:

Acum vrem să colorăm vertexurile unui grafic, iar două vârfuri trebuie să aibă o culoare diferită dacă sunt conectate de o margine.

În 1852, studentul de botanică Francis Guthrie a trebuit să coloreze o hartă a județelor din Anglia. El a observat că patru culori păreau să fie suficiente pentru orice hartă încercată, dar nu a fost în stare să găsească o dovadă care să funcționeze pentru toate hărțile. Aceasta s-a dovedit a fi o problemă extrem de dificilă și a devenit cunoscută sub numele de teorema celor patru culori .

În următorii 100 de ani, mulți matematicieni au publicat „dovezi” la cele patru culori ale teoremei, doar pentru a găsi greșeli mai târziu. Unele dintre aceste dovezi invalide au fost atât de convingătoare încât a fost nevoie de mai mult de 10 ani pentru a descoperi erori.

Pentru o lungă perioadă de timp, matematicienii nu au putut nici să dovedească faptul că patru culori sunt suficiente, nici să găsească o hartă care avea nevoie de mai mult de patru culori.

Nu s-au înregistrat progrese în ceea ce privește problema celor patru culori până în 1976, când Wolfgang Haken și Kenneth Appel au folosit un computer pentru a rezolva definitiv. Aceștia au redus la infinit multe hărți posibile la 1936 cazuri speciale, care au fost verificate fiecare de un computer în total peste 1000 de ore.

Teorema în patru culori este prima teoremă matematică bine cunoscută care a fost dovedită folosind un computer, ceva care a devenit mult mai comun și mai puțin controversat de atunci. Calculatoare mai rapide și un algoritm mai eficient înseamnă că astăzi poți dovedi teorema de patru culori pe un laptop în doar câteva ore.

Postmark for the Department of Mathematics at the University of
Illinois Urbana-Champaign, where Haken and Appel worked.

Teorema celor patru culori funcționează numai pentru hărți pe un plan plat sau o sferă și în care toate țările constau dintr-o singură zonă.

Cu toate acestea, matematicienii s-au uitat, de asemenea, la hărțile imperiilor , unde țările pot consta din mai multe componente deconectate și la hărți de pe planete în formă diferită, cum ar fi un torus (formă de gogoși). În aceste cazuri, este posibil să aveți nevoie de mai mult de patru culori, iar dovezile devin și mai dificile.

This map on a torus requires seven colours.

Archie