Penjelasan teorema empat warna
Pada 1852, seorang matematikawan muda yang sedang mewarnai peta county di Inggris menyadari bahwa empat warna tampaknya cukup untuk membedakan county yang bertetangga. Mungkinkah itu berlaku untuk setiap peta yang mungkin ada? Pertanyaan ini menjadi salah satu masalah paling terkenal dalam matematika, memunculkan bukti keliru yang terkenal dan bertahan selama sebelas tahun, dan akhirnya terjawab pada 1976 dengan cara yang mengubah apa yang diterima matematikawan sebagai bukti.
Pertanyaannya
Francis Guthrie, mantan mahasiswa Augustus De Morgan, bertanya apakah setiap peta dapat diwarnai dengan empat warna sehingga negara yang berbagi perbatasan mendapat warna berbeda. Dua aturan membuat pertanyaan ini tepat. Negara harus terhubung, masing-masing satu bagian utuh, dan negara yang bertemu hanya di satu titik tidak dihitung sebagai tetangga. Tiga warna jelas tidak selalu cukup, karena sebuah negara yang dikelilingi cincin tiga negara lain yang saling bersentuhan membutuhkan warna keempat. Pertanyaannya adalah apakah warna kelima pernah dibutuhkan.
Peta sebagai graf
Tandai sebuah titik di setiap negara dan tarik garis antara dua titik setiap kali negaranya berbagi perbatasan. Hasilnya adalah graf, dan karena peta terletak pada lembar datar, garis-garisnya dapat digambar tanpa bersilangan: grafnya planar. Mewarnai peta berarti mewarnai simpul-simpul graf ini sehingga kedua ujung setiap sisi berbeda warna. Jumlah warna terkecil yang memenuhi disebut bilangan kromatik, dan teorema empat warna menyatakan bahwa tidak ada graf planar yang bilangan kromatiknya lebih dari empat.
Bukti Kempe yang gagal
Pada 1879, pengacara dan matematikawan Alfred Kempe menerbitkan sebuah bukti. Gagasan cerdasnya, yang kini disebut rantai Kempe, adalah menukar dua warna di sepanjang rantai negara yang terhubung untuk membebaskan sebuah warna di tempat yang dibutuhkan. Bukti itu diterima selama sebelas tahun, sampai Percy Heawood menemukan celah pada 1890. Perbaikan Heawood membuktikan hasil yang lebih lemah: lima warna selalu cukup. Rantai Kempe bertahan dan menjadi alat dalam bukti yang akhirnya ditemukan.
Mengapa lima itu mudah
Setiap graf planar memiliki simpul dengan paling banyak lima tetangga; ini mengikuti dari rumus Euler, yang membatasi graf planar dengan n simpul hingga paling banyak 3n − 6 sisi. Hapus simpul seperti itu, warnai sisa peta dengan argumen yang sama, lalu kembalikan simpulnya. Jika tetangganya memakai kurang dari lima warna, satu warna masih bebas. Jika mereka memakai kelimanya, penukaran rantai Kempe selalu membebaskan satu warna. Dengan empat warna, penukaran yang sama bisa gagal, dan itulah tepatnya celah yang terlewat oleh Kempe.
Bukti komputer
Pada 1976, Kenneth Appel dan Wolfgang Haken di University of Illinois membuktikan teorema ini. Mereka menunjukkan bahwa setiap peta memuat setidaknya satu dari 1.936 konfigurasi dari sebuah himpunan tak terhindarkan, dan bahwa setiap konfigurasi dapat direduksi: peta terkecil yang membutuhkan lima warna tidak mungkin memuatnya. Memeriksa keterreduksian memakan lebih dari seribu jam di komputer, terlalu banyak untuk diverifikasi dengan tangan. Banyak matematikawan merasa tidak nyaman dengan bukti yang tidak dapat dibaca seluruhnya oleh siapa pun, dan perdebatan tentang bukti berbantuan komputer pun dimulai.
Bukti yang lebih sederhana dan verifikasi penuh
Pada 1996, Neil Robertson, Daniel Sanders, Paul Seymour, dan Robin Thomas menerbitkan bukti yang lebih sistematis dengan 633 konfigurasi, masih diperiksa komputer tetapi lebih mudah diverifikasi. Pada 2005, Georges Gonthier dan Benjamin Werner memformalkan seluruh bukti di asisten pembuktian Coq, sehingga sebuah program kecil yang tepercaya memeriksa setiap langkah logisnya. Kini teorema empat warna adalah salah satu hasil yang paling teliti diverifikasi dalam matematika.
Algoritma pewarnaan
Menemukan pewarnaan empat warna untuk sebuah peta tertentu berlangsung cepat dalam praktik, tetapi menemukan jumlah warna paling sedikit untuk graf umum itu sulit: menentukan apakah tiga warna cukup adalah masalah NP-lengkap. Metode praktis mencakup pewarnaan greedy menurut urutan derajat menurun, DSATUR, yang mewarnai simpul paling terbatas berikutnya, dan pencarian runut-balik, yang menjelajahi pilihan dan membatalkannya ketika buntu. Pewarnaan graf dipakai untuk menjadwalkan ujian tanpa bentrok, menetapkan frekuensi radio agar pemancar yang berdekatan tidak saling mengganggu, dan mengalokasikan register dalam kompiler.
Jelajahi
Buka pewarna peta empat warna untuk membuat peta berisi 4 hingga 120 negara, mewarnainya sendiri dengan empat warna, dan melihat bentrokan muncul dengan warna merah. Biarkan pewarnaan greedy, DSATUR, atau runut-balik menyelesaikan peta langkah demi langkah, tampilkan graf negara-negara yang bertetangga, dan periksa jumlah warna paling sedikit yang benar-benar dibutuhkan peta.
Pertanyaan yang sering diajukan
Apakah teorema ini membantu pembuat peta?
Hampir tidak. Peta sungguhan biasanya diwarnai dengan lebih banyak warna agar jelas, dan memuat samudra, danau, serta negara yang terdiri dari beberapa bagian, yang tidak dicakup teorema ini. Pentingnya bersifat matematis: teorema ini mendorong perkembangan teori graf dan memunculkan pertanyaan tentang apa yang dianggap sebagai bukti.
Apa itu rantai Kempe?
Ambil dua warna, misalnya merah dan biru, dan sebuah negara berwarna merah. Rantai Kempe-nya adalah himpunan semua negara merah dan biru yang dapat Anda capai darinya dengan hanya melangkah melalui tetangga merah dan biru. Menukar merah dan biru di seluruh rantai itu menjaga pewarnaan tetap sah, dan dapat membebaskan sebuah warna untuk negara di sebelah rantai.
Mengapa negara yang terdiri dari beberapa bagian mematahkan teorema ini?
Jika sebuah negara boleh terdiri dari wilayah-wilayah terpisah yang semuanya harus berwarna sama, graf ketetanggaannya tidak lagi planar, dan dapat dibuat peta yang membutuhkan berapa pun jumlah warna hingga 12 untuk dua bagian per negara, seperti yang dipelajari Heawood dalam masalah kekaisarannya.
Mengapa pewarna ini membuat peta dari titik-titik?
Setiap negara adalah wilayah persegi yang lebih dekat ke satu titik acak daripada ke titik lain mana pun, yaitu diagram Voronoi. Cara ini menghasilkan peta yang tampak realistis dengan negara-negara cembung, dan dua negara bertetangga tepat ketika wilayahnya berbagi seruas perbatasan, yang dihitung aplikasi ini secara akurat.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Buka pewarna peta empat warna