Teorema empat warna
Dalam matematika, teorema empat warna, atau teorema peta empat warna, menyatakan bahwa, diberikan setiap pemisahan bidang menjadi wilayah yang contiguous, menghasilkan gambar yang disebut peta, diperlukan tidak lebih dari empat warna untuk mewarnai wilayah peta sehingga tidak ada dua daerah yang berdekatan memiliki warna yang sama. Berdekatan berarti dua daerah berbagi segmen kurva batas bersama, bukan hanya sudut tempat tiga atau lebih daerah bertemu.[1] Itu adalah teorema utama pertama yang dibuktikan menggunakan komputer. Awalnya, bukti ini tidak diterima oleh semua ahli matematika karena bukti yang dibantu komputer terlalu sulit bagi manusia untuk diperiksa dengan tangan.[2] Sejak saat itu bukti ini telah diterima secara luas, meskipun beberapa orang masih meragukannya.[3]
Teorema empat warna dibuktikan pada tahun 1976 oleh Kenneth Appel dan Wolfgang Haken setelah banyak pembuktian dan counterexample yang keliru (tidak seperti teorema lima warna, teorema yang menyatakan bahwa lima warna cukup untuk mewarnai peta, yang dibuktikan pada tahun 1800-an). Untuk menghilangkan keraguan yang tersisa tentang pembuktian Appel-Haken, pembuktian yang lebih sederhana menggunakan ide yang sama dan masih mengandalkan komputer diterbitkan pada tahun 1997 oleh Robertson, Sanders, Seymour, dan Thomas. Selain itu, pada tahun 2005, teorema tersebut dibuktikan oleh Georges Gonthier dengan perangkat lunak pembuktian teorema tujuan umum.
Catatan
- ^ Dari (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.
Referensi
- Allaire, Frank (1978), "Another proof of the four colour theorem. I.", dalam D. McCarthy; H. C. Williams, Proceedings, 7th Manitoba Conference on Numerical Mathematics and Computing, Congr. Numer., 20, Winnipeg, Man.: Utilitas Mathematica Publishing, Inc., hlm. 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, doi:10.1215/ijm/1256049011 , MR 0543792
- Appel, Kenneth; Haken, Wolfgang; Koch, John (1977), "Every Planar Map is Four Colorable. II. Reducibility", Illinois Journal of Mathematics, 21 (3): 491–567, doi:10.1215/ijm/1256049012 , MR 0543793
- Appel, Kenneth; Haken, Wolfgang (October 1977), "Solution of the Four Color Map Problem", Scientific American, 237 (4), hlm. 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, doi:10.1090/conm/098, ISBN 0-8218-5103-9, MR 1025335
- Bar-Natan, Dror (1997), "Lie algebras and the four color theorem", Combinatorica, 17 (1): 43–52, arXiv:q-alg/9606016 , doi:10.1007/BF01196130, MR 1466574
- Bernhart, Frank R. (1977), "A digest of the four color theorem", Journal of Graph Theory, 1 (3), hlm. 207–225, doi:10.1002/jgt.3190010305, MR 0465921
- 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 0832128.
- Cayley, Arthur (1879), "On the colourings of maps", Proc. Royal Geographical Society, Blackwell Publishing, 1 (4), hlm. 259–261, doi:10.2307/1799998, JSTOR 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, doi:10.1007/978-1-4612-1720-6 , ISBN 978-0-387-98497-1, MR 1633950
- F. G. (June 10, 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, hlm. 332–338
- Hudson, Hud (May 2003), "Four Colors Do Not Suffice", The American Mathematical Monthly, 110 (5): 417–423, doi:10.2307/3647828, JSTOR 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
- McKay, Brendan D. (2012), A note on the history of the four-colour conjecture, arXiv:1201.2852 , Bibcode:2012arXiv1201.2852M
- Nash-Williams, C. St. J. A. (1967), "Infinite graphs—a survey", Journal of Combinatorial Theory, 3 (3): 286–301, doi:10.1016/s0021-9800(67)80077-2 , MR 0214501.
- O'Connor; Robertson (1996), The Four Colour Theorem, MacTutor archive
- 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
- Ringel, G.; Youngs, J.W.T. (1968), "Solution of the Heawood Map-Coloring Problem", Proc. Natl. Acad. Sci. USA, 60 (2), hlm. 438–445, Bibcode:1968PNAS...60..438R, doi:10.1073/pnas.60.2.438, PMC 225066 , PMID 16591648
- 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), hlm. 571–575, doi:10.1145/237814.238005, MR 1427555
- Robertson, Neil; Sanders, Daniel P.; Seymour, Paul; Thomas, Robin (1997), "The Four-Colour Theorem", J. Combin. Theory Ser. B, 70 (1), hlm. 2–44, doi:10.1006/jctb.1997.1750, MR 1441258
- Saaty, Thomas; Kainen, Paul (1986), "The Four Color Problem: Assaults and Conquest", Science, New York: Dover Publications, 202 (4366): 424, Bibcode:1978Sci...202..424S, doi:10.1126/science.202.4366.424, ISBN 0-486-65092-8
- Swart, Edward Reinier (1980), "The philosophical implications of the four-color problem", American Mathematical Monthly, Mathematical Association of America, 87 (9), hlm. 697–702, doi:10.2307/2321855, JSTOR 2321855, MR 0602826
- Thomas, Robin (1998), "An Update on the Four-Color Theorem" (PDF), Notices of the American Mathematical Society, 45 (7), hlm. 848–859, MR 1633714
- Thomas, Robin (1995), The Four Color Theorem
- 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", dalam Lamb, John D.; Preece, D. A., Surveys in combinatorics, 1999, London Mathematical Society Lecture Note Series, 267, Cambridge: Cambridge University Press, hlm. 201–222, doi:10.1017/CBO9780511721335, ISBN 0-521-65376-2, MR 1725004
- 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
Pranala luar
- Hazewinkel, Michiel, ed. (2001) [1994], "Four-colour problem", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4
- (Inggris) Weisstein, Eric W. "Blanuša snarks". MathWorld.
- (Inggris) Weisstein, Eric W. "Map coloring". MathWorld.
- Daftar generalisasi dari teorema empat warna di MathOverflow