Teorema empat warna

Dari Wikipedia bahasa Indonesia, ensiklopedia bebas
Loncat ke navigasi Loncat ke pencarian
Contoh dari peta dengan empat warna
Peta empat warna dari negara bagian Amerika Serikat (tidak termasuk danau).

Dalam matematika, teorema empat warna, atau teorema peta empat warna, menyatakan bahwa, diberikan setiap pemisahan bidang menjadi wilayah yang contiguous, menghasilkan gambar yang disebut peta, diperlukan tidak lebih dari empat warna untuk mewarnai wilayah peta sehingga tidak ada dua daerah yang berdekatan memiliki warna yang sama. Berdekatan berarti dua daerah berbagi segmen kurva batas bersama, bukan hanya sudut tempat tiga atau lebih daerah bertemu.[1] Itu adalah teorema utama pertama yang dibuktikan menggunakan komputer. Awalnya, bukti ini tidak diterima oleh semua ahli matematika karena bukti yang dibantu komputer terlalu sulit bagi manusia untuk diperiksa dengan tangan.[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.

Catatan[sunting | sunting sumber]

  1. ^ Dari (Gonthier 2008): "Definitions: A planar map is a set of pairwise disjoint subsets of the plane, called regions. A simple map is one whose regions are connected open sets. Two regions of a map are adjacent if their respective closures have a common point that is not a corner of the map. A point is a corner of a map if and only if it belongs to the closures of at least three regions. Theorem: The regions of any simple planar map can be colored with only four colors, in such a way that any two adjacent regions have different colors."
  2. ^ Swart (1980).
  3. ^ Wilson (2014), 216–222.

Referensi[sunting | sunting sumber]

Pranala luar[sunting | sunting sumber]