Forum Sains Indonesia

Ilmu Alam => Matematika => Topik dimulai oleh: ListRA-92 pada Desember 22, 2010, 03:29:32 PM

Judul: Hadwiger–Nelson problem (Unsolved)
Ditulis oleh: ListRA-92 pada Desember 22, 2010, 03:29:32 PM
(http://upload.wikimedia.org/wikipedia/commons/thumb/a/a3/Hadwiger-Nelson.svg/220px-Hadwiger-Nelson.svg.png)

Pada teori graf geometris, permasalahan Hadwiger–Nelson (Hugo Hadwiger and Edward Nelson), mencari banyak warna minimum yang dibutuhkan untuk mewarnai bidang (lihat gambar) sehingga tidak ada dua titik bertetangga yang memiliki warna yang sama. Jawabannya belum diketahui, namun sudah disempitkan cakupannya antara 4, 5, 6 atau 7. Nilai aktual mungkin sebenarnya bergantung pada pilihan aksioma untuk teori himpunan  (Shelah & Soifer 2003).

Pertanyaan dapat diungkapkan dalam pernyataan teoretis graf sebagai berikut. Misalkan G adalah graf jarak satuan pada bidang: graf tak hingga dengan semua titik bidang sebagai verteks dan dengan sebuah sisi di antara dua verteks jika dan hanya jika terdapat jarak satuan di antara dua titik. Maka permasalahan Hadwiger–Nelson adalah mencari bilangan kromatik G (banyak warna minimum yang dibutuhkan untuk mewarnai graf). Sebagai konsekuensi, persoalan seringkali disebut "mencari bilangan kromatik bidang". Dengan teorema de Bruijn–Erdős (Bruijn & Erdős, 1951), permasalahan ekivalen (dibawah asumsi aksioma pilihan) dengan mencari bilangan kromatik terbesar yang mungkin untuk graf jarak satuan terhingga.

Menurut Jensen & Toft (1995), permasalahan ini pertama kali diformulasikan oleh E. Nelson in 1950, dan pertama kali dipublikasikan oleh Gardner (1960). Hadwiger (1945) memublikasikan hasil yang berkaitan, menunjukkan bahwa penutupan bidang oleh lima set tertutup kongruen berisi jarak satuan dalam salah satu set, dan beliau juga menyebutkan permasalahan di dokumen selanjutnya (Hadwiger 1961).

Sumber:
[pranala luar disembunyikan, sila masuk atau daftar.]–Nelson_problem[/font]