Teorema empat warna

pernyataan dalam matematika

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]

Contoh dari peta dengan empat warna
Peta empat warna dari negara bagian Amerika Serikat (tidak termasuk wilayah perairan).

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

sunting

Percobaan Gagal

sunting

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

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

Referensi

sunting

Pranala luar

sunting