Penerapan teorema empat warna

8

Saya membaca teorema empat warna dan bertanya-tanya apakah ada aplikasi praktisnya. (Saya rasa memisahkan peta menjadi empat warna berbeda dapat dianggap sebagai aplikasi.)

Saya mencoba Googling untuk aplikasi tetapi tidak dapat menemukannya.

graph-theory colorings Kutu buku komputer
sumber

Karena telah diketahui bahwa lima warna sudah mencukupi (dengan bukti sederhana), pertanyaan sebenarnya adalah: apa manfaat aplikasi dari fakta bahwa empat daripada lima warna sudah mencukupi.

Yuval Filmus

Bisa dibilang mewarnai peta bukan aplikasi, karena teorema tidak memungkinkan untuk wilayah yang terputus. Misalnya, Alaska, Hawaii, dan benua AS semuanya harus memiliki warna yang sama. Kemungkinan wilayah yang terputus berarti bahwa grafik yang terkait dengan peta tidak harus planar: memang dengan grafik apa pun

m

$m$ ujung-ujungnya dapat direalisasikan dengan memiliki

m

$m$ pulau-pulau sedemikian rupa sehingga negara

i

$i$ dan

j

$j$ berbagi pulau iff

i j

$ij$ adalah keunggulan dalam grafik. Saya tidak ingat apakah peta dunia yang sebenarnya 4-colourable; mungkin itu.

David Richerby

7

Salah satu aplikasi Teorema 4 Warna yang paling terkenal adalah tiang telepon seluler. Tiang-tiang ini semuanya mencakup area tertentu dengan beberapa tumpang tindih yang berarti bahwa mereka tidak dapat mentransmisikan semuanya pada frekuensi yang sama. Metode sederhana untuk memastikan bahwa tidak ada dua tiang yang tumpang tindih memiliki frekuensi yang sama adalah memberi mereka semua frekuensi yang berbeda. Tetapi, karena pemerintah memiliki semua frekuensi dan biaya untuk masing-masing, orang ingin menggunakan jumlah frekuensi minimum yang mungkin. Area yang dicakup dapat digambarkan sebagai peta dan frekuensi yang berbeda dapat direpresentasikan sebagai warna.

Raaman Nair
sumber

Dengan kata lain, dengan asumsi bahwa empat pewarnaan dapat ditemukan secara efisien, Anda hanya perlu memesan empat frekuensi di muka bahkan jika lokasi yang tepat dari tiang tidak diketahui (atau bahkan dapat berubah).

Yuval Filmus

1

Apakah ini benar? Grafik tidak dijamin planar (lima tiang yang cukup berdekatan akan menyebabkan a

K_{5}

$K_5$ subgraph) jadi tidak dijamin empat warna.

David Richerby

@YuvalFilmus Planar grafik dapat empat warna dalam waktu kuadratik: Robertson, Sanders, Seymour dan Thomas, "Grafik planar empat warna yang efisien", Proc. STOC 1996 ( PDF ).

David Richerby

Sebenarnya, izinkan saya untuk kembali dan membuat pernyataan yang lebih kuat. Ini tidak benar, justru karena lima tiang yang ditempatkan dengan erat menghasilkan a

K_{5}

$K_5$ . Pada kenyataannya, ini adalah aplikasi dari fakta bahwa ada algoritma waktu polinomial untuk menghitung jumlah kromatik grafik unit disk , yang tidak harus planar dan belum tentu 4-colourable.

David Richerby

3

Masalah pewarnaan grafik secara luas berlaku untuk masalah penjadwalan.

Pertimbangkan Universitas, tempat Anda mencoba menjadwalkan waktu untuk semua ujian akhir. Beberapa siswa mengambil lebih dari satu kelas, jadi Anda ingin memastikan mereka tidak memiliki dua ujian yang dijadwalkan secara bersamaan. Namun, Anda ingin periode penulisan ujian Anda sesingkat mungkin, untuk menjalankan sebanyak mungkin ujian secara bersamaan.

Anda bisa menganggap ini sebagai masalah pewarnaan Grafik: yang Anda buat $G=(V,E)$ di mana setiap kelas adalah simpul, dan keunggulan antara simpul setiap saat dua kelas berisi siswa yang sama. Warna Anda akan mewakili waktu ujian yang berbeda. Angka minimum yang dapat digunakan untuk mewarnai grafik itu adalah jumlah waktu terkecil yang Anda perlukan untuk menulis semua ujian.

Masalahnya secara umum adalah NP sulit, tetapi jika Anda memiliki pengetahuan tentang jadwal Anda, katakanlah, itu planar, maka Anda dapat menerapkan teorema 4-warna untuk menulis semua ujian bersama.

Saya tidak 100% yakin Anda akan pernah mendapatkan grafik planar dalam masalah penjadwalan kehidupan nyata, tetapi ada pelajaran yang lebih luas di sini: grafik secara luas berlaku untuk hal-hal yang tidak segera jelas. Teorema 4-warna bukan hanya tentang grafik dan peta, itu dapat digunakan untuk memodelkan masalah kehidupan nyata di mana Anda mengekspresikan beberapa set objek, dan beberapa hubungan biner antara objek-objek itu.

Ya ampun
sumber

1

Tampaknya relatif tidak mungkin bahwa Anda akan mendapatkan grafik planar dalam masalah penjadwalan karena, seperti yang Anda katakan, itu akan memungkinkan Anda untuk menyelesaikan semuanya menggunakan hanya empat slot. (Misalnya, dalam contoh spesifik yang Anda berikan, grafik tidak planar jika ada satu siswa yang mengambil lima kelas.)

David Richerby

-3

ya grafik planar $n$ -warna untuk rendah / tetap $n$ memiliki aplikasi minimal, terutama pewarnaan peta planar. namun $n$ -warna untuk sewenang-wenang $n$ adalah NP lengkap , itu adalah salah satu 1 ^st masalah terbukti NP lengkap, maka mengikat ke dalam bangunan besar teori. tetapi sebenarnya bahkan $n$ -warna dapat direduksi menjadi 3 warna melalui transformasi dasar. [1] begitu $n$ mewarnai untuk $n \geq 3$ NP lengkap (tetapi tidak terbatas pada grafik planar) . mungkin ada pengurangan lain untuk peta 4-warna & planar yang dipelajari dalam literatur. yaitu untuk mendapatkan perasaan yang lebih baik tentang signifikansinya, seseorang harus mempelajari kemungkinan pengurangannya yang merupakan topik kompleks / maju / melebar.

tetapi sudut lain adalah bahwa pertanyaan 4-pewarnaan dari peta / grafik planar adalah masalah terbuka yang sulit dalam matematika / ilmu komputer selama beberapa dekade (sebenarnya lebih dari 1 ½ abad , dan salah satu masalah grafik yang paling maju). matematika maju melalui pemecahan masalah yang belum terpecahkan. cocok dengan pola inti umum "masalah yang mudah dinyatakan tetapi solusi / bukti tidak dapat diakses untuk waktu yang lama dan sangat kompleks". ini adalah asimetri fundamental yang tersebar luas dalam matematika yang menunjukkan batas pengungkit matematis / teoritis .

teknik-teknik yang terbukti berhasil dapat diterapkan pada masalah-masalah lain yang tidak terpecahkan dan kadang-kadang membuka pemandangan / abstraksi teoretis / konseptual baru. kadang-kadang bukti luar biasa berharga dalam hak mereka sendiri dan teorema 4-Warna cocok dengan kategori ini. ini adalah salah satu bukti teorema otomatis awal yang paling canggih. pekerjaan lebih lanjut telah dilakukan untuk meningkatkan penyederhanaan yang dapat dibaca manusia sejak ditemukan dan menyebabkan kejutan relatif melalui komunitas teoretis pada pengumumannya, dan memicu banyak analisis dan komentar lebih lanjut. ini berfungsi sebagai tolok ukur / tonggak / uji kasus utama untuk peningkatan pembuktian teorema otomatis .

[1] 3 pewarnaan selesai NP

vzn
sumber

1

Mungkin lebih baik menggunakan simbol yang berbeda dari

n

$n$ untuk menunjukkan jumlah warna, sejak

n

$n$ sering menunjukkan kardinalitas set vertex. Juga, kita tidak tahu bagaimana grafik planar 3-warna dalam waktu polinomial.

Juho

Penerapan teorema empat warna

Jawaban: