Teorema celor patru culori

Teorema celor patru culori afirmă că orice hartă situată pe un plan sau pe o sferă poate fi colorată cu cel mult patru culori diferite (vopsele), astfel încât oricare două zone cu un segment de limită comun să aibă o culoare diferită. În același timp, zonele trebuie să fie conectate [1] (adică zona nu poate consta din două sau mai multe „bucăți”) separate, iar chenarul trebuie să fie nepunctual (la un moment dat, câte zone doriți pot atinge colțurile lor, inclusiv cele pictate în aceeași culoare).

În 1852, Francis Guthrie , în timp ce alcătuia o hartă a comitatelor Angliei, a observat că patru culori erau suficiente pentru un astfel de scop. Fratele său Frederick a raportat această observație celebrului matematician Augustus de Morgan , care a spus comunității matematice. Formularea exactă a ipotezei a fost publicată de Arthur Cayley (1878) [2] . A durat mult timp pentru a demonstra teorema. S-au făcut multe încercări atât pentru a dovedi, cât și pentru a infirma, iar această problemă a fost numită problema celor patru culori [3] .

Pentru hărțile simple sunt suficiente trei culori și este necesară o a patra culoare, de exemplu, atunci când există o zonă înconjurată de un număr impar de altele care se ating, formând un ciclu. Teorema celor cinci culori , care afirmă că cinci culori sunt suficiente, a avut o demonstrație scurtă, simplă și a fost demonstrată la sfârșitul secolului al XIX-lea, dar demonstrarea teoremei pentru cazul celor patru culori a întâmpinat dificultăți semnificative.

Teorema celor patru culori a fost demonstrată în 1976 de Kenneth Appel și Wolfgang Haken de la Universitatea din Illinois . A fost prima teoremă matematică majoră care a fost demonstrată de un computer. Primul pas al demonstrației a fost de a demonstra existența unui anumit set de cărți din 1936, niciuna dintre ele nu ar putea conține o carte mai mică care să infirme teorema. Autorii au folosit un program special de calculator pentru a demonstra această proprietate pentru fiecare dintre cardurile din 1936. Dovada acestui fapt a durat sute de pagini. După aceea, Appel și Haken au ajuns la concluzia că nu există cel mai mic contraexemplu pentru teoremă, pentru că altfel ar trebui să conțină una dintre aceste cărți de 1936, ceea ce nu are. Această contradicție spune că nu există deloc un contraexemplu.

Inițial, dovada nu a fost acceptată de toți matematicienii, deoarece nu poate fi verificată manual. Mai târziu a câștigat o acceptare mai largă, deși unii au avut îndoieli multă vreme. Pentru a înlătura orice îndoieli rămase, în 1997 Robertson, Sanders, Seymour și Thomas au publicat o dovadă mai simplă folosind idei similare, dar totuși făcută de computer. În plus, în 2005, dovada a fost făcută de Georges Gonteer folosind software specializat ( Coq v7.3.1) [4] .

Formulări echivalente

În teoria grafurilor, enunțul teoremei celor patru culori are următoarele formulări:

Se cunosc mult mai multe formulări echivalente [5] .

Încercări istorice de dovadă

Cele mai cunoscute încercări de demonstrare sunt:

Variații și generalizări

Alte suprafete

Probleme similare pentru alte suprafețe ( torus , sticla Klein etc.) s-au dovedit a fi mult mai simple. Pentru toate suprafețele închise, cu excepția sferei (și a planului și cilindrului echivalent) și a sticlei Klein , numărul necesar de culori poate fi calculat din genul său folosind următoarea formulă, propusă în 1890 de Percy John Heawood : [9]

Limita superioară se obține destul de simplu, a fost dovedită chiar de Heawood (pentru o sferă, formula dă răspunsul corect - 4, dar demonstrația lui Heawood nu este aplicabilă acesteia). Cel de jos se dovedește prin încorporarea graficului complet în suprafața corespunzătoare; dovada a fost construită în 1952-1968 de un grup de matematicieni, ultimul pas a fost făcut de Gerhard Ringel și John Youngs . [10] [11] [12]

Pentru banda Möbius (precum și pentru planul proiectiv ) sunt necesare 6 culori. Pentru suprafețele unilaterale ale genului , [11]

Pentru o sticlă Klein (gen ), numărul este 6 (și nu 7, conform formulei) - acest lucru a fost arătat de P. Franklin în 1934. [13]

Harta insulei

Din teorema celor patru culori rezultă că o hartă a unei insule în care fiecare țară are acces la mare poate fi colorată cu 3 culori. Această afirmație are însă și o dovadă elementară.

Problema Imperiului

O problemă similară pentru hărțile cu imperii coloniale (adică cu țări formate din mai multe „piese” separate pe hartă, al căror număr este m ), a fost luată în considerare de Percy John Heawood . Când răspunde . Limita superioară este obținută destul de simplu; a fost dovedită chiar de Heawood. Cel de jos se dovedește prin încorporarea graficului complet în suprafața corespunzătoare; dovada este dată de Gerhard Ringel și Brad Jackson. [paisprezece]

Varianta problemei despre imperii cu colonii pe alte planete rămâne deschisă. De exemplu, dacă fiecare țară de pe Pământ are o colonie pe Lună, atunci se cunosc doar estimări

Dimensiuni mai mari

În dimensiuni mai mari , nu există o generalizare rezonabilă a problemei, deoarece este ușor să veniți cu o hartă tridimensională cu un număr arbitrar de zone care se ating între ele. .

Jocul „patru culori”

Stephen Barr a propus un joc de logică pe hârtie pentru doi jucători numit „Patru culori”. În cuvintele lui Martin Gardner  , „Nu cunosc o modalitate mai bună de a înțelege dificultățile pe care le implică rezolvarea problemei cu patru culori decât prin simpla joacă a acestui joc curios” [15] .

Acest joc necesită patru creioane colorate. Primul jucător începe jocul desenând o zonă goală arbitrară. Al doilea jucător îl pictează cu oricare dintre cele patru culori și, la rândul său, își desenează zona goală. Primul jucător pictează zona celui de-al doilea jucător și adaugă o zonă nouă și așa mai departe - fiecare jucător pictează zona adversarului și o adaugă pe a sa. În acest caz, zonele care au o chenar comună trebuie vopsite în culori diferite. Cel care la rândul său va fi obligat să ia culoarea a cincea pierde.

În acest joc, pierderea unuia dintre jucători nu este deloc o dovadă a incorecității teoremei (patru culori nu au fost suficiente), ci doar o ilustrare a faptului că condițiile jocului și teoremele sunt foarte diferite. . Pentru a verifica corectitudinea teoremei pentru harta obținută în joc, trebuie să verificați conectivitatea zonelor desenate și, după ce ați eliminat culorile din ea, aflați dacă este posibil să vă descurcați cu doar patru culori pentru a picta rezultatul. harta (teorema spune că este posibil).

Există, de asemenea, următoarele variante ale jocului:

  1. Harta este pre-împărțită aleatoriu în zone de diferite dimensiuni. La fiecare mișcare, jucătorul care pictează zona se schimbă și, în ordine strictă, culoarea se schimbă. Astfel, fiecare jucător pictează cartea cu doar două culori. Jucătorul ratează o tură dacă nu poate picta o zonă astfel încât culoarea zonelor adiacente să fie diferită. Jocul se termină când niciunul dintre jucători nu mai poate face nicio mișcare. Câștigătorul este cel cu suprafața totală mai mare a zonelor umbrite.
  2. Un pătrat cu laturile colorate diferit într-una din cele patru culori este împărțit în mai multe pătrate (de obicei 4 × 4). Prima mișcare pictează peste pătratul adiacent laturii, în mișcări ulterioare puteți picta peste pătratul care este adiacent unuia dintre pătratele umplute. Nu puteți picta peste un pătrat cu culorile pe care este pictat unul dintre pătratele adiacente acestuia sau latura adiacentă pătratului. Câștigă jucătorul care face ultima mutare.

În cultură

Vezi și

Note

  1. ↑ Frank Harari. Conjectura în patru culori // Teoria graficelor = Teoria graficelor. - M .: Mir , 1973. - S. 17-18.
  2. ↑ Samokhin A.V. Problema celor patru culori: o istorie neterminată a dovezii  // Jurnal educațional Sorovsky. - 2000. - T. 6 , nr 7 .
  3. ↑ 1 2 3 J. J. O'Connor, E. F. Robertson. Teorema celor patru culori . Arhiva MacTutor Istoria matematicii . Şcoala de Matematică şi Statistică, Universitatea St Andrews, Scoţia (septembrie 1996).
  4. ↑ Georges Gonthier. O dovadă verificată de computer a teoremei celor patru culori  . Microsoft Research Cambridge (2005). Arhivat din original pe 5 iunie 2022.
  5. ↑ 1 2 Shor N. Z. , Donets G. A. Despre problema celor patru culori // Matematica azi / ed. prof. A. Ya. Dorogovtseva  - Kiev, școala Vișcha, 1982. - Tiraj 3000 de exemplare. — c. 33-53
  6. ↑ Lakeev A.V. Elemente ale teoriei graficelor obișnuite. - Irkutsk: Editura IGU, 2014. - P. 7. - 92 p.
  7. ↑ A.B.Kempe. Despre problema geografică a celor patru culori  (engleză)  // Amer. J Math. . - 1879. - Vol. 2 . - P. 193-200 .
  8. ↑ P.G. Tait. Notă asupra unei teoreme în geometria poziţiei   // Trans . Roy. soc. Edinburgh . - 1880. - Vol. 29 . - P. 657-660 .
  9. ↑ Percy John Heawood. Teorema Hartă-Color  (engleză)  // Quarterly Journal of Mathematics, Oxford. - 1890. - Vol. 24 . - P. 332-338 .
  10. ↑ G. Ringel, JWT Youngs. Rezolvarea problemei de colorare a hărții Heawood   // Proc . Nat. Acad. sci. STATELE UNITE ALE AMERICII. - 1968. - Vol. 60 , iss. 2 . - P. 438-445 . - doi : 10.1073/pnas.60.2.438 . — PMID 16591648 .
  11. ↑ 1 2 Ringel G. Teorema de colorare a hărții / Tradus din engleză de V. B. Alekseev. — M .: Mir, 1977. — 256 p.
  12. ↑ Boltyansky, 1982 , p. 77.
  13. ↑ P. Franklin. O problemă cu șase culori  //  J. Math. Fiz. - 1934. - Vol. 13 . - P. 363-369 .
  14. ↑ Jackson, Brad; Ringel, Gerhard. Problema imperiului lui Heawood  //  J. Combin. Teoria Ser. B. - 1985. - Vol. 38 , nr. 2 . - P. 168-178 .
  15. ↑ Martin Gardner. Problema celor patru culori // Puzzle-uri și diversiuni matematice = Puzzle-uri și diversiuni matematice: [trad. din  engleză. ]. - Ed. a II-a. - M .  : Mir , 1999. - S. 389-390. — 447 p. — ISBN 5-03-003340-8 .
  16. ↑ Martin Gardner. Insula celor cinci culori . N.Y .: Fantasia Mathematica , 1958.

Literatură

  Accesați articolul Wikidata  Dicționare și enciclopedii