PROFILPELAJAR.COM

Masalah Guthrie atau Teorema Empat Warna menyatakan bahwa setiap peta dapat diwarnai dengan menggunakan empat warna, sehingga daerah yang berbatasan tidak memiliki warna yang sama.^[1]

Pada tahun 1976, Masalah Guthrie menjadi teorema matematika pertama yang dibuktikan menggunakan komputer, akan tetapi ditolak akibat pembuktiannya yang terlalu sulit bagi manusia.^[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.

Sejarah

Percobaan Gagal

Konjektur muncul untuk pertama kalinya pada 23 Oktober, 1852.^[4] Ketika Francis Guthrie mewarnai denah wilayah Inggris, ia menyadari bahwa hanya empat warna berbeda yang diperlukan. Kemudian saudara laki-lakinya, Frederick Guthrie, menyampaikan pesain tersebut kepada Augustus De Morgan.^[5]

Pesan dari De Morgan kepada Hamilton, 23 Oct. 1852

Ada beberapa percobaan yang gagal untuk membuktikan konjektur. De Morgan percaya bahwa itu mengikuti fakta sederhana tentang empat bagian, meskipun ia tidak percaya bahwa kebenaran dapat diturunkan dari fakta yang lebih mendasar.^[6]

Pada tahun 1854, salah seorang dari Guthrie bersaudara mengajukan pertanyaan di The Athenaeum,^[7] dan De Morgan menerbitkannya lagi di majalah yang sama pada tahun 1860.^[6] Konjektur itu direferensikan oleh Arthur Cayley pada tahun 1870.

Pada tahun 1879, pembuktian oleh Alfred Kempe diakui secara luas,^[8] dan terungkap cacat oleh Percy Heawood pada tahun 1890. Kejadian serupa terulang kembali oleh Peter Guthrie Tait pada tahun 1880, yang buktinya ditunjukkan salah oleh Julius Petersen pada tahun 1891. Masing-masing bukti palsu tidak tertandingi selama 11 tahun.^[9]

Pada tahun 1943, Hugo Hadwiger merumuskan Konjektur Hadwiger,^[10] generalisasi luas dari teorema empat warna yang dianggap sebagai masalah terbuka paling menantang di bidangnya.

Catatan

^ Mathworld Wolfram
^ Swart (1980).
^ Wilson (2014), 216–222.
^ Donald MacKenzie, Mechanizing Proof: Computing, Risk, and Trust (MIT Press, 2004) p103
^ (Wilson 2014, hlm. 18)
^ ^a ^b De Morgan (anonymous), Augustus (April 14, 1860), "The Philosophy of Discovery, Chapters Historical and Critical. By W. Whewell.", The Athenaeum: 501–503
^ (F. G. 1854); (McKay 2012)
^ W. W. Rouse Ball (1960) The Four Color Theorem, in Mathematical Recreations and Essays, Macmillan, New York, pp 222–232.
^ Thomas (1998), hlm. 848.
^ Hadwiger (1943).

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, diarsipkan dari versi asli tanggal 2022-02-04, diakses tanggal 2020-06-18
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, diarsipkan dari versi asli tanggal 2013-01-16, diakses tanggal 2020-06-18
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, diarsipkan dari versi asli tanggal 2013-02-03, diakses tanggal 2020-06-18
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, diarsipkan dari versi asli tanggal 2020-02-14, diakses tanggal 2020-06-18
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 ^{[pranala nonaktif permanen]}
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