Teorema empat warna

Misalkan kamu disuruh mewarnai peta Indonsia dan kamu hanya diberikan empat crayon dengan warna berbeda. Hanya ada satu aturan kamu tidak boleh mewarnai  propinsi-propinsi yang bersebelahan dengan warna. Apakah kamu sanggup?

Pastinya ya. Jangan kan peta indonesia,  faktanya Semua peta hanya membutuhkan paling banyak 4 warna sehingga tidak ada wilayah-wilayah yang bersebelahan yang mempunyai warna yang sama. Inilah yang dikenal dengan Teorema Empat Warna (TEW)

Dua daerah dinyatakan “bersebelahan” jika mempunyai garis batas yang sama dan batasnya bukan merupakan titik. Contoh :

Supaya lebih mudah di analisis secara matematika maka TEW dibawa kedalan bentuk graph. Setiap wilayah bisa direpresntasikan dengan titik. Sedangkan garis batas 2 wilayah yang bersebelahan bisa direpresentasikan dengan garis yang menghubungkan 2 titik. Jelas bawha 2 garis batas tidak mungkin berpotongan, ini dikenal dengan graph planar. Contoh dibawah adalah peta US jika direpersentasikan ke dalam Graph

Dalam teori Graph, TEW menyatakan

Setiap graph planar hanya membutuhkan paling banyak 4 warna sehingga setiap titik yang beesebelahan mempunyai warna yang berbeda

atau singkatnya

Setiap graph planar dapat diwarnai dengan 4 wana  (every planar graph is four-colorable)

Meskipun terlihat sederhana TEW membutuhkan waktu 100 tahun untuk dibuktikan dan sampai detik ini pembuktiannya masih menjadi perdebatan dikalangan Matematikawan.

Sejarah

Pada tahun 1852, Francis Guthrie sedang mewarnai peta wilayah-wilayah di Inggris. Guthrie menyadari hanya dibutuhkan 4 warna untuk mewarnai peta inggris sehingga tidak ada wilayah-wilayah yang bersebelahan tapi dia penasaran apakah hal tersebut berlaku untuk semua peta. Lalu dia bertanya kepada seorang Matematikan De Morgan tetapi De Morgan tidak mampu menjawabnya.  Kemudian De Morgan melempar pertanyaan tersebut kepada para matematikawan lainnya.

Pada tahun 1879, Kempe menyatakan telah berhasil membuktikan TEW. Para matematikan menerima baik bukti dari Kempe. Sayang 11 tahun kemudian diketahui bukti dari Kempe salah. Kontribusi penting lainya datang dari Birkhoff pada tahun 1922 yang membuktikan TEW berlaku untuk peta paling banyak memuat 25 wilayah. Temuan Birkhoff digunakan matematikan lainnya sebagai dasar untuk membuktikan TEW berlaku secera general.

Akhirnya pada tahun 1976, TEW bener-benar bisa dibuktikan oleh Appel dan Haken pada tahun 1976 dengan menggunakan komputer. Butuh waktu 1200jam untuk komputer saat itu memeverifikasi bukti TEW dari Appel dan Haken.  Ini merupakan pertama kali dalam dunia Matematika suatu teorema dibuktikan oleh Komputer. Hal tersebut menimbulkan pertanyaan mendasar dikalangan Matematikawan

Apakah boleh pembuktian menggunakan komputer?

Matematika adalah ilmu yang mempelajari konsep-konsep abstrak yang hanya ada dikepala kita. Oleh karena itu banyak Matematikawan meyakini hanya dibutuhkan otak yang cerdas untuk membuktikan sifat-sifat konsep abstrak tersebut dan hubungan konsep yang satu dengan konsep lainnya (Baca Teorema). Itulah yang membedakan matematika dengan ilmu-ilmu eksak lainnya, kita membutuhkan telskop untuk mengetahui jarak 2 bintang, kita membutuhkan mikroskop untuk mengetahui sifat-sifat suatu bakteri. Oleh sebab itu lah banyak matematikwan yang kontra dengan pembuktian yang menggunakan komputer, penggunaan komputer sebagai alat bantu pembuktian akan menghilangkan sifat matematika sebagai “brain game”. Sampai detik ini matematikan masih sibuk mengembangkan pembuktian TEW yang tidak membutuhkan bantuan komputer, yang bisa diverifikasi cukup dengan otak manusia saja. Disatu sisi seiring perkembanagan jaman dimana komputer sudah menjadi alat umum yang digunakan sehari-hati maka banyak matematikawan muda yang beranggapan penggunaan komputer untuk membuktikan teorema itu sah-sah saja.

———————————————————————————————————————————————-
**Ingin mendapatkan kaos unik bertema matematika silahkan kunjungi kaos.ariaturns.com**

Advertisements

About Aria Turns

Seorang Alumnus Matematika UGM, dengan ilmu yang didapat ketika kuliah (Padahal sering bolos kuliah :p ), saya menyebarkan virus matematika
This entry was posted in graph theory and tagged , , , , , , , . Bookmark the permalink.

9 Responses to Teorema empat warna

  1. kka' says:

    jadi titik terang aku disaat aku lagi berusaha bs paham ttang graf. lg ada tugas bikin modul graf jg ne….. mungkin bs lebih bnyk mas aria tulisan materinya ttng graf-graf yang lain…jadi kan bs lebih teraaaang gitchu bwat dirikoe…. makasiii mas aria….

  2. Uha says:

    Jadi pengen ambil teori Graph ^^

  3. Zanra_GTG says:

    oOo Ternyata “Teorema Empat Warna”, bisa diimplementasikan pakai graph yach…!!?, saya kira hanya digunakan untuk “Shortest Path” atau masalah pengurutan topologis saja,,, kira” ada saran referensi tidak untuk mempelajari Graph ini…!?

    • Aria Turns says:

      Lha TEW kan emang teorema didalam teori Graph. Shortest Path”dan masalah pengurutan topologis keduanya merupakan pembahasan didalam teori graph pula. Kalo kamu mengerti/mempelajari kedua hal tersebut artinya kamu punya dasar graph yang cukup baik

  4. Dah lupa tuh graph planar. Hehe. Ingetnya cuma pernah belajar teori graph. Kapan2 buka lagi ah.

  5. emma says:

    Sok, lu Wij 😀

    Burnside lemma yang mana ya? :p

  6. Mawi Wijna says:

    saya baru inget dulu pernah nyinggung topik ini di kuliah Teori Graf. Tapi perihal coloring, (dulu) aku lebih ngeh soal Burnside Lemma karena pernah disuruh presentasi 😀

  7. zakimath says:

    Jadi inget dulu kuliah Teori Graf-nya Bapak Prof. Setiadji, dapet materi tentang pewarnaan graf dan aplikasinya pada pewarnaan peta… 😀

Silahkan, tinggalkan komentar

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s