Primer četvorobojne mape
Četvorobojna mapa saveznih država SAD (ignorišući jezera).

U matematici, teorema četiri boje, ili teorema mape sa četiri boje, navodi da za bilo koje razdvajanje ravni na susedne regione, čime se formira slika koji se naziva mapa, nije potrebno više od četiri boje da bi se obojili regioni karte tako da nijedan par susednih regiona nema istu boju. Susedni znači da dva regiona dele zajednički segment granične krive, a ne samo ugao gde se susreću tri ili više regiona.[1] Ovo je bila prva značajna teorema koja je dokazana pomoću računara. U početku ovaj dokaz nisu prihvatili svi matematičari, jer je bilo nemoguće da se manuelno proveri kompjuterski dokaz.[2] Od tada je dokaz stekao široko prihvatanje, mada ima onih koji i dalje osporavaju njegovu validnost.[3]

Teoremu četiri boje su dokazali Kenet Apl i Volfgang Hejken 1976. godine, nakon mnogih lažnih dokaza i protivprimera (za razliku od teoreme pet boja, teoreme koja navodi da je pet boja dovoljno za bojenje mape, što je dokazano 1800-ih). Da bi se razvejale sve preostale nedoumice oko dokaza Apel-Hejkena, jednostavniji dokaz koji koristi iste ideje i koji se još uvek oslanja na računare objavili su Robertson, Sanders, Sejmour i Tomas 1997. godine. Pored toga, 2005. godine teoremu je dokazao Žorž Gontje, softverom opšte namene za dokazivanja teorema.

Precizna formulacija teoremeУреди

U grafno-teoretskom pogledu, ova teorema navodi da je za planarni graf   bez petlji, hromatski broj njegovog dualnog grafa  .

Intuitivnu formulaciju teoreme četiri boje, i.e. „ako je dato bilo kakvo razdvajanje ravni u susedne oblasti, regioni se mogu obojiti koristeći najviše četiri boje tako da nijedan par susednih regiona nema istu boju”, potrebno je tumačiti na odgovarajući način da bi bila tačna.

Prvo, regioni su susedni ako dele granični segment; dva regiona koja dele samo izolovane granične tačke ne smatraju se susednim. Drugo, bizarni regioni, poput onih sa konačnom površinom, ali beskonačno dugim obodom, nisu dozvoljeni; mape sa takvim regionima mogu zahtevati više od četiri boje.[4] (Da bismo bili sigurni, možemo se ograničiti na regione čije se granice sastoje od konačno mnogo pravolinijskih segmenata. Dozvoljeno je da region u potpunosti okružuje jedan ili više drugih regiona.) Traba imati na umu da pojam „susedni region” (tehnički: povezani otvoreni podskup ravni) nije isto što i „država” na regularnim mapama, jer zemlje ne moraju biti kontinuirane (npr. provincija Kabinda kao deo Angole, Nahčivan kao deo Azerbejdžana, Kaliningrad kao deo Rusije i Aljaska je deo Sjedinjenih Država, mada nisu susedni). Ako se zahteva da čitava teritorija neke zemlje dobije istu boju, tada četiri boje nisu uvek dovoljne. Na primer, razmotrite pojednostavljenu mapu:

Na ovoj mapi, dve regiona sa oznakom A pripadaju istoj zemlji. Ako bi se želelo da ti regioni dobiju istu boju, tada bi bilo potrebno pet boja, jer su dva A regiona zajedno susedna sa četiri druga regiona, svaki od kojih pripada svim ostalim. Slična konstrukcija se takođe primenjuje ako se za sva vodena tela koristi jedna boja, kao što je to uobičajeno na stvarnim mapama. Za mape u kojima više zemalja može imati više nepovezanih regija, moguće je da će biti potrebno šest ili više boja.

 
Mapa sa četiri regiona, i korespondirajućim planarnim grafom sa četiri vrha.

Jednostavnija formulacija teoreme koristi teoriju grafova. Skup regiona mape se može apstraktnije predstaviti kao neusmereni graf koji ima vrh za svaki region i ivicu za svaki par regiona koji imaju granični segment. Ovaj graf je planaran: on se može nacrtati u ravni bez ukrštanja postavljanjem svakog vrha na proizvoljno odabranu lokaciju unutar regije kojoj pripada, i crtanjem ivica kao krivih bez ukrštanja, koje vode od vrha jednog regiona, preko zajedničkog graničnog segmenta, do vrha susednog regiona. Suprotno tome, bilo koji planarni graf može se formirati iz mape na ovaj način. U grafno-teorijskoj terminologiji, teorema četiri boje navodi da se vrhovi svakog planarnog grafa mogu obojiti sa najviše četiri boje tako da nijedan par susednih vrhova ne dobije istu boju ili ukratko:

Svaki planarni graf je četvorobojan.[5][6]

ReferenceУреди

  1. ^ From Gonthier (2008): "Definitions: A planar map is a set of pairwise disjoint subsets of the plane, called regions. A simple map is one whose regions are connected open sets. Two regions of a map are adjacent if their respective closures have a common point that is not a corner of the map. A point is a corner of a map if and only if it belongs to the closures of at least three regions. Theorem: The regions of any simple planar map can be colored with only four colors, in such a way that any two adjacent regions have different colors."
  2. ^ Swart (1980).
  3. ^ Wilson (2014), 216–222.
  4. ^ Hudson (2003).
  5. ^ Thomas (1998, стр. 849)
  6. ^ Wilson (2014)).

LiteraturaУреди

Spoljašnje vezeУреди