Teorema četiri boje

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 G {\displaystyle G} bez petlji, hromatski broj njegovog dualnog grafa χ ( G ∗ ) ≤ 4 {\displaystyle \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

  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

  • 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

Teorema četiri boje на Викимедијиној остави.
  • 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