Pewarna peta teorema empat warna
Serumit apa pun sebuah peta, empat warna selalu cukup untuk mewarnainya sehingga negara yang berbagi perbatasan tidak pernah berwarna sama. Pernyataannya cukup sederhana untuk diuji seorang anak dengan krayon, tetapi pembuktiannya memakan waktu lebih dari satu abad dan membutuhkan komputer. Warnai sendiri sebuah peta acak, lihat perbatasan mana yang bentrok, lalu saksikan tiga metode mengerjakannya, dari aturan greedy yang cepat tetapi kadang membutuhkan warna kelima hingga pencarian runut-balik yang selalu cukup dengan empat. Pilih warna dan klik negara untuk mewarnainya; perbatasan berubah merah jika dua tetangga memiliki warna yang sama. Negara yang hanya bersentuhan di satu sudut boleh berwarna sama. Atau biarkan komputer yang mengerjakannya: pilih metode lalu tekan Selesaikan untuk menontonnya, atau Langkah untuk mengikutinya satu gerakan demi satu gerakan. Warna paling sedikit memeriksa apakah peta ini cukup dengan tiga warna, atau bahkan dua. Peta baru menggambar peta lain, dan Tampilkan tetangga menggambar jaringan negara yang berbagi perbatasan.
Cara kerjanya
- Pilih jumlah negara dan tekan Peta baru, atau mulai dengan peta yang ditampilkan.
- Pilih warna dan klik negara untuk mewarnainya, sambil memperhatikan perbatasan merah di tempat tetangga bentrok.
- Pilih metode lalu tekan Selesaikan atau Langkah untuk menyaksikannya mewarnai peta, dan tekan Warna paling sedikit untuk melihat berapa warna yang dibutuhkan peta ini.
Dari peta ke graf
Letakkan sebuah titik di setiap negara dan hubungkan dua titik jika negaranya berbagi perbatasan. Peta menjadi graf, dan mewarnai peta sama dengan mewarnai titik-titik sehingga titik yang terhubung berbeda warna. Karena peta digambar pada lembar datar, graf ini planar: graf ini dapat digambar tanpa garis yang bersilangan. Negara yang bertemu hanya di satu titik, seperti empat persegi di sebuah sudut, bukan tetangga. Teorema empat warna menyatakan bahwa setiap graf planar dapat diwarnai dengan empat warna. Aktifkan Tampilkan tetangga untuk melihat graf dari peta saat ini.
Tiga cara mewarnai
Pewarnaan greedy mengambil negara satu per satu, dimulai dari yang tetangganya paling banyak, dan memberi masing-masing warna pertama yang belum dipakai tetangganya. Cara ini cepat tetapi berpandangan pendek, dan pada beberapa peta ia meraih warna kelima atau bahkan keenam. DSATUR, yang ditemukan Daniel Brélaz pada 1979, selalu memilih berikutnya negara yang tetangganya sudah menampilkan warna berbeda paling banyak, yang biasanya menghindari jebakan itu. Runut-balik mencoba warna secara bergiliran dan, ketika sebuah negara tidak punya warna tersisa, membatalkan pilihan-pilihan terakhirnya lalu mencoba lagi; ia selalu menemukan pewarnaan dengan empat warna, kadang setelah mundur berkali-kali.
Pertanyaan yang sering diajukan
Mengapa empat warna selalu cukup?
Belum ada yang menemukan alasan singkatnya. Bukti Kenneth Appel dan Wolfgang Haken pada 1976 menunjukkan bahwa setiap peta pasti memuat salah satu dari 1.936 konfigurasi kecil, dan bahwa masing-masing dapat dihapus lalu pewarnaannya dipulihkan kemudian; memeriksa semuanya memakan lebih dari seribu jam waktu komputer. Bukti komputer yang lebih sederhana oleh Neil Robertson, Daniel Sanders, Paul Seymour, dan Robin Thomas pada 1996 membutuhkan 633 konfigurasi, dan pada 2005 Georges Gonthier memverifikasi sebuah bukti secara menyeluruh dengan asisten pembuktian Coq.
Apakah ada peta yang membutuhkan keempat warna?
Ya. Empat negara yang masing-masing bersentuhan dengan tiga lainnya, seperti sebuah negara yang dikelilingi cincin tiga negara lain, membutuhkan empat warna. Namun, banyak peta cukup dengan tiga, dan Warna paling sedikit mencari tahu hal itu untuk peta di layar. Menentukan secara umum apakah sebuah peta dapat diwarnai dengan tiga warna adalah masalah sulit, NP-lengkap, meskipun empat warna selalu cukup.
Mengapa metode greedy kadang memakai lima warna?
Metode ini mewarnai setiap negara sekali dan tidak pernah berubah pikiran. Pilihan awal bisa membuat negara berikutnya dikelilingi keempat warna, dan satu-satunya jalan keluar adalah warna kelima. Runut-balik justru akan kembali dan mengubah pilihan-pilihan sebelumnya.
Apakah teorema ini berlaku pada permukaan lain?
Pada bola, ya: sama saja dengan bidang datar. Pada torus, permukaan sebuah donat, beberapa peta membutuhkan tujuh warna, dan tujuh warna selalu cukup, seperti yang ditunjukkan Percy Heawood. Jika negara boleh terdiri dari beberapa bagian terpisah, seperti negara yang memiliki koloni, empat warna tidak lagi cukup.
Apakah ada yang dikirim ke server?
Tidak. Peta, metode pewarnaan, dan pemeriksaannya berjalan di browser Anda. Pengaturan Anda tetap tersimpan di penyimpanan lokal browser ini.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Ke Editor