Teorema četiri boje

Č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 $G$ bez petlji, hromatski broj njegovog dualnog grafa $\chi (G^{*})\leq 4$ .

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

^ 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."
^ Swart (1980).
^ Wilson (2014), 216–222.
^ Hudson (2003).
^ Thomas (1998, стр. 849)
^ Wilson (2014)).

Literatura

Allaire, Frank (1978), „Another proof of the four colour theorem. I.”, Ур.: D. McCarthy; H. C. Williams, Proceedings, 7th Manitoba Conference on Numerical Mathematics and Computing, Congr. Numer., 20, Winnipeg, Man.: Utilitas Mathematica Publishing, Inc., стр. 3—72, ISBN 0-919628-20-6, MR 0535003
Appel, Kenneth; Haken, Wolfgang (1977), „Every Planar Map is Four Colorable. I. Discharging”, Illinois Journal of Mathematics, 21 (3): 429—490, MR 0543792, doi:10.1215/ijm/1256049011
Appel, Kenneth; Haken, Wolfgang; Koch, John (1977), „Every Planar Map is Four Colorable. II. Reducibility”, Illinois Journal of Mathematics, 21 (3): 491—567, MR 0543793, doi:10.1215/ijm/1256049012
Appel, Kenneth; Haken, Wolfgang (oktobar 1977), „Solution of the Four Color Map Problem”, Scientific American, 237 (4), стр. 108—121, Bibcode:1977SciAm.237d.108A, doi:10.1038/scientificamerican1077-108
Appel, Kenneth; Haken, Wolfgang (1989), Every Planar Map is Four-Colorable, Contemporary Mathematics, 98, With the collaboration of J. Koch., Providence, RI: American Mathematical Society, ISBN 0-8218-5103-9, MR 1025335, doi:10.1090/conm/098
Bar-Natan, Dror (1997), „Lie algebras and the four color theorem”, Combinatorica, 17 (1): 43—52, MR 1466574, arXiv:q-alg/9606016 , doi:10.1007/BF01196130
Bernhart, Frank R. (1977), „A digest of the four color theorem”, Journal of Graph Theory, 1 (3), стр. 207—225, MR 0465921, doi:10.1002/jgt.3190010305
Borodin, O. V. (1984), „Solution of the Ringel problem on vertex-face coloring of planar graphs and coloring of 1-planar graphs”, Metody Diskretnogo Analiza (41): 12—26, 108, MR 832128 .
Cayley, Arthur (1879), „On the colourings of maps”, Proc. Royal Geographical Society, Blackwell Publishing, 1 (4), стр. 259—261, JSTOR 1799998, doi:10.2307/1799998
Fritsch, Rudolf; Fritsch, Gerda (1998), The Four Color Theorem: History, Topological Foundations and Idea of Proof, Translated from the 1994 German original by Julie Peschke., New York: Springer, ISBN 978-0-387-98497-1, MR 1633950, doi:10.1007/978-1-4612-1720-6
F. G. (10. 6. 1854), „Tinting Maps”, The Athenaeum: 726 .
Gonthier, Georges (2005), A computer-checked proof of the four colour theorem (PDF), unpublished
Gonthier, Georges (2008), „Formal Proof—The Four-Color Theorem” (PDF), Notices of the American Mathematical Society, 55 (11): 1382—1393, MR 2463991
Hadwiger, Hugo (1943), „Über eine Klassifikation der Streckenkomplexe”, Vierteljschr. Naturforsch. Ges. Zürich, 88: 133—143
Heawood, P. J. (1890), „Map-Colour Theorem”, Quarterly Journal of Mathematics, Oxford, 24, стр. 332—338
Hudson, Hud (maj 2003), „Four Colors Do Not Suffice”, The American Mathematical Monthly, 110 (5): 417—423, JSTOR 3647828, doi:10.2307/3647828
Kempe, A. B. (1879), „On the Geographical Problem of the Four Colours”, American Journal of Mathematics, the Johns Hopkins University Press, 2 (3): 193—220, doi:10.2307/2369235
Magnant, C.; Martin, D. M. (2011), „Coloring rectangular blocks in 3-space”, Discussiones Mathematicae Graph Theory, 31 (1): 161—170, doi:10.7151/dmgt.1535, Архивирано из оригинала 04. 02. 2022. г., Приступљено 18. 02. 2020
McKay, Brendan D. (2012), A note on the history of the four-colour conjecture, Bibcode:2012arXiv1201.2852M, arXiv:1201.2852 
Nash-Williams, C. St. J. A. (1967), „Infinite graphs—a survey”, Journal of Combinatorial Theory, 3 (3): 286—301, MR 0214501, doi:10.1016/s0021-9800(67)80077-2 .
O'Connor; Robertson (1996), The Four Colour Theorem, MacTutor archive, Архивирано из оригинала 16. 01. 2013. г., Приступљено 18. 02. 2020
Pegg, Ed, Jr.; Melendez, J.; Berenguer, R.; Sendra, J. R.; Hernandez, A.; Del Pino, J. (2002), „Book Review: The Colossal Book of Mathematics” (PDF), Notices of the American Mathematical Society, 49 (9): 1084—1086, Bibcode:2002ITED...49.1084A, doi:10.1109/TED.2002.1003756
Reed, Bruce; Allwright, David (2008), „Painting the office”, Mathematics-in-Industry Case Studies, 1: 1—8, Архивирано из оригинала 03. 02. 2013. г., Приступљено 18. 02. 2020
Ringel, G.; Youngs, J.W.T. (1968), „Solution of the Heawood Map-Coloring Problem”, Proc. Natl. Acad. Sci. USA, 60 (2), стр. 438—445, Bibcode:1968PNAS...60..438R, PMC 225066 , PMID 16591648, doi:10.1073/pnas.60.2.438
Robertson, Neil; Sanders, Daniel P.; Seymour, Paul; Thomas, Robin (1996), „Efficiently four-coloring planar graphs”, Proceedings of the 28th ACM Symposium on Theory of Computing (STOC 1996), стр. 571—575, MR 1427555, doi:10.1145/237814.238005
Robertson, Neil; Sanders, Daniel P.; Seymour, Paul; Thomas, Robin (1997), „The Four-Colour Theorem”, J. Combin. Theory Ser. B, 70 (1), стр. 2—44, MR 1441258, doi:10.1006/jctb.1997.1750
Saaty, Thomas; Kainen, Paul (1986), „The Four Color Problem: Assaults and Conquest”, Science, New York: Dover Publications, 202 (4366): 424, Bibcode:1978Sci...202..424S, ISBN 0-486-65092-8, doi:10.1126/science.202.4366.424
Swart, Edward Reinier (1980), „The philosophical implications of the four-color problem”, American Mathematical Monthly, Mathematical Association of America, 87 (9), стр. 697—702, JSTOR 2321855, MR 0602826, doi:10.2307/2321855
Thomas, Robin (1998), „An Update on the Four-Color Theorem” (PDF), Notices of the American Mathematical Society, 45 (7), стр. 848—859, MR 1633714
Thomas, Robin (1995), The Four Color Theorem, Архивирано из оригинала 14. 02. 2020. г., Приступљено 18. 02. 2020
Tietze, Heinrich (1910), „Einige Bemerkungen zum Problem des Kartenfärbens auf einseitigen Flächen” [Some remarks on the problem of map coloring on one-sided surfaces], DMV Annual Report, 19: 155—159 ^{[мртва веза]}
Thomas, Robin (1999), „Recent Excluded Minor Theorems for Graphs”, Ур.: Lamb, John D.; Preece, D. A., Surveys in combinatorics, 1999, London Mathematical Society Lecture Note Series, 267, Cambridge: Cambridge University Press, стр. 201—222, ISBN 0-521-65376-2, MR 1725004, doi:10.1017/CBO9780511721335
Tait, P. G. (1880), „Remarks on the colourings of maps”, Proc. R. Soc. Edinburgh, 10: 729, doi:10.1017/S0370164600044643
Wilson, Robin (2014) [2002], Four Colors Suffice, Princeton Science Library, Princeton, NJ: Princeton University Press, ISBN 978-0-691-15822-8, MR 3235839

Spoljašnje veze

Hazewinkel Michiel, ур. (2001). „Four-colour problem”. Encyclopaedia of Mathematics. Springer. ISBN 978-1556080104.
Weisstein, Eric W. „Blanuša snarks”. MathWorld.
Weisstein, Eric W. „Map coloring”. MathWorld.
List of generalizations of the four color theorem on MathOverflow

[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."

[FOOTNOTESwart1980-2] Swart (1980).

[FOOTNOTEWilson2014216–222-3] Wilson (2014), 216–222.

[FOOTNOTEHudson2003-4] Hudson (2003).

[5] Thomas (1998, стр. 849)

[6] Wilson (2014)).

[1]

[2]

[3]

[4]

[5]

[6]