Geometri : Teorema Empat Warna

Empat perkiraan warna, diperkirakan ditemukan oleh Francis Guthrie. Dia adalah mahasiswa di Universitas London dimana dia belajar dibawah asuhan De Morgan. Setelah lulus dari London, dia belajar hokum, pada saat itu saudara laki-lakinya Frederick Guthrie telah menjadi murid De Morgan. Francis Guthrie menunjukkan ke saudara laki-lakinya beberapa percobaannya tentang pewarnaan peta dan meminta Frederick untuk menanyakan pendapar De Morgan tentang hal itu.

De Morgan tak dapat menjawabnya, pada 23 Oktober 1852, hari yang sama dengan datangnya pertanyaan itu, dia menulis ke Hamilton di Dublin. De Morgan menulis :

“Hari ini seorang muridku menanyakan padaku untuk memberikan padanya tentang sebuah alasan yang pada kenyataannya saya tidak tahu - belum tahu. Dia mengatakan bahwa jika sebuah gambar terbagi dan kompartemen berbedanya diberi warna – 4 warna, tidak lebih – masalah selanjutnya adalah pada 4 warna tersebut. Percobaan untuk menemukan yang ke lima atau lebih tidak diperlukan… jika kamu menjawab pertanyaan ini dengan jawaban yang mudah hal itu akan membuat saya seperti binatang yang bodoh, saya piker saya akan menjadi seperti Sphinx…”

Hamilton membalasnya pada 26 Oktober 1852 (menunjukkan efisien dari dirinya dan pelayanan kantor pos).

“Saya tidak bisa menjawab pertanyaanmu tentang quaternion warna dengan cepat.”

Sebelum melanjutkan pada sejarah dari 4 perkiraan warna, kita akan membahas tentang Francis Guthrie. Setelah belajar menjadi pengacara, dia pergi ke Afrika Selatan pada tahun 1861 sebagai Profesor Matematika. Ia menulis beberapa buku Matematika dan menjadi tertarik di bidang botani.

De Morgan terus bertanya pada setiap orang untuk dapat menemukan solusi pada masalah Guthrie’s dan beberapa matematikawan mencoba menemukannya. Charles Peirce di USA mencoba membuktikan perkiraan tersebut pada tahun 1860. Cayley juga belajar permasalahan tersebut dari De Morgan dan 13 Juni 1878, dia mengajukan sebuah pertanyaan ke Komunitas Matematika London menanyakan apakah 4 perkiraan warna telah dipecahkan. Cayley mengirim sebuah paper, On the colouring of maps, pada komunitas Geografi Kerajaan dan dipublikasikan pada tahun 1879. Paper ini menjelaskan kesulitan-kesulitan yang ada dalam percobaan untuk membuktikan perkiraan tersebut.

Pada 17 Juli 1879, Alfred Bray Kempe mengumumkan bahwa dia telah membuktikan 4 perkiraan warna. Kempe adalah seorang pengacara di London yang belajar Matematika di bawah asuhan Cayley di Cambridge dan mencurahkan sebagian waktunya untuk penemuan di bidang Matematika. Atas saran Cayley, Kempe mengajukan teoremanya ke American Journal of Mathematics yang dipublikasikan pada tahun 1879.

Kempe mengemukakan sebuah argument yang dikenal sebagai methode of Kempe chains. Jika kita punya peta yang mana setiap daerah diwarnai merah, hijau, biru, atau kuning kecuali satu, anggaplah X. jika daerah X tidak dikelilingi oleh daerah dengan 4 warna tersebut maka ada warna yang disisakan untuk X. oleh karena itu anggaplah daerah 4 warna tersebut mengelilingi X. jika X dikelilingi A, B, C, D dengan warna merah, kuning, hijau, dan biru maka ada dua hal yang harus dibahas.

i. tidak ada rantai antara daerah yang berdekatan dari A ke C dengan warna merah dan hijau.

ii. ada rantai antara daerah yang berdekatan dari A ke C dengan warna merah dan hijau.

Jika berbentuk (i), maka tidak ada masalah. Ganti A ke hijau, lalu ubah warna daerah dalam rantai merah atau hijau untuk mengikuti A. Karena C tidak dalam rantai, maka C tetap hijau dan sekarang tidak ada daerah merah yang berdekatan dengan X, warna X adalah merah.

Jika berbentuk (ii), maka tidak mungkin ada daerah yang berdekatan dengan rantai kuning atau biru dari B ke D. [hal itu tidak dapat melintasi daerah rantai merah atau hijau]. Oleh karena (i) ada pada B dan D kita rubah warnanya seperti di atas.

Kempe menerima pujian besar karena karyanya itu. Dia terpilih anggota dari The Real Society dan dianggap sebagai harta karun selama beberapa tahun.

Teorema 4 warna kembali menjadi 4 perkiraan warna pada tahun 1890. Percy John Heawood, seorang Dosen pada Durhan England, menerbitkan buku berjudul Map Colouring Theorem, di dalamnya ia menyatakan :

”Lebih ke merusak daripada membangun, dengan ini akan memperlihatkan kekurangan dari bukti yang ada pada saat ini”.

Walaupun Heawood menunjukkan bahwa bukti Kempe salah, dia membuktikan bahwa setiap peta dapat diwarnai dengan 5 warna pada sebuah kertas. Kempe melaporkan kesalahannya sendiri pada komunitas matematika London dan berkata dia tidak dapat memperbaiki kesalahan pada buktinya. Pada tahun 1896 De Lavalle Poussin memfokuskan kesalahan Kempe.

Heawood sepanjang hidupnya bekerja pada pewarnaan peta. Setelah bekerja selama 60 tahun, dia sukses meneliti warna diperlukan untuk peta pada permukaan yang berbeda dan menyatakan apa yang dikenal sebagai Heawood estimate untuk angka yang diperlukan pada permukaan Euler characteristic.

Heawood menyumbangkan kontribusi pada 4 perkiraan warna pada tahun 1898, dia membuktikan bahwa jika angka dari masing-masing batas sekitar daerah adalah dapat terbagi tiga lalu daerah-daerah tersebut terdiri dari 4 warna. Dia kemudian menulis banyak paper tentang hasilnya tersebut.

Secara jelas sebuah grafik dapat dibuat dari semua peta yang daerahnya dijelaskan oleh titik tertinggi dan dua titik tertinggi yang tergabung oleh suatu ujung, jika daerah yang berhubungan dengan titik tertinggi berdekatan. Hasil grafiknya adalah planar, berarti bahwa grafik itu dapat digambar dalam permukaan tanpa ada ujung. 4 perkiraan warna menimbulkan pertanyaan jika titik tertinggi pada grafik dapat diwarnai dengan 4 warna, maka tidak ada dua titik tertinggi (yang berdekatan) yang mempunyai warna yang sama.

Berdasarkan grafik, sebuah triangulation dapat ditentukan dengan menambahkan batas untuk membagi semua bentuk non-traingular menjadi triangle. Sebuah bentuk adalah bagian dari tiangulation yang didalamnya terdapat sebuah sirkuit. Set yang tidak dapat dihindari adalah bentuk set dengan properti, yaitu bahwa semua triangulation harus terdiri dari salah satu bentuk dalam set. Suatu bentuk dapat dikurangi jika bentuk itu tidak dapat berada pada grafik terkecil triangulation yang tidak dapat dibuat menjadi 4 warna.

Pencarian untuk set yang dapat dihindari dimulai pada tahun 1904 pada karya Weinicle. Sedangkan, di Amerika pada saat Veblen yang menerbitkan paper pada tahun 1912 tentang 4 perkiraan warna meneruskan karya Heawood.

Franklin pada 1922 menerbitkan contoh yang lebih maju dari set yang tidak dapat dihindari dan menggunakan ide Birkhoff tentang kemampuan berkurang untuk membuktikan bahwa semua peta dengan daerah <= 25 dapat di 4 warna-kan. Angka daerah yang dihasilkan dalam 4 warna peta perlahan bertambah. Reynold menambah menjadi 27, pada tahun 1926, Winn menjadi 35 tahun 1940, Ore dan Setemple menambah menjadi 35 pada tahun 1970 dan Mayer menjadi 95 di tahun1976.

Akan tetapi, ide final dari solusi 4 perkiraan warna ini telah ada sebelum kedua hasil di atas tersebut. Heesh pada tahun 1969, mengenalkan method of discharging. Metode ini terdiri penentuan titik tertinggi dengan derajat i dengan charge 6-i. Sekarang berdasarkan formula Euler kita dapat menyimpulkan jumlah charge dari semua titik tertinggi pasti 12. Bentuk S yang telah ditentukan dapat dibuktikan tidak dapat dihindari jika untuk triangulation T yang tidak terdiri dari bentuk S, kita dapat mendistribusikan kembali charge tersebut (tanpa mengubah keseluruhan charge) maka tidak ada titik tertinggi yang menghasilkan charge positif.

Heesch berfikir bahwa 4 perkiraan warna dapat diselesaikan dengan meneliti set dengan 8900 bentuk. Ada kesulitan dalam pendekatan ini karena beberapa bentuk mempunyai pembatas lebih dari 18 ujung (batas) dan kemampuan berkurangnya tidak dapat ditest. Test pada kemampuan pengurangan menggunakan argumen rantai Kempe, tetapi beberapa bentuk mempunyai hambatan untuk mencegah reduksi.

Pada tahun 1976 diperlihatkan solusi lengkap untuk perkiraan warna, ketika pada saat itu menjadi teorema 4 warna untuk kedua kalinya, dan terakhir. Pembuktiannya dilakukan oleh Appel dan Haken, menggunakan berdasarkan pada metode kemampuan berkurang menggunakan rantai Kempe. Merek ajuga menggunakan ide Heesch dan akhirnya mereka membangun set yang tidak dapat dihindari dengan 1500 bentuk. Mereka mengatur untuk tetap menjaga ukuran ring pembatas dibawah <= 14 membuat perhitungan lebih mudah daripada yang dilakukan Heesch.

Teorema 4 warna adalah teorema penting yang pertama kali dibuktikan menggunakan komputer. Walalupun pada mulanya ada kekhawatiran, akhirnya pembuktian independen meyakinkan orang-orang bahwa teorema 4 warna telah dapat dibuktikan. Detail tentang bukti tersebut ditulis dalam 2 artikel pada tahun 1977.

Sumber :

Haza’a, Salah Kaduri. dkk. 2007. Sejarah Matematika Klasik dan Modern. Yogyakarta : Universitas Ahmad Dahlan Press.