Pewarnaan Graf

Pewarnaan graf menetapkan label, atau warna, pada elemen-elemen graf sehingga elemen-elemen yang berdekatan berbeda, dan mempelajari jumlah minimum warna yang dibutuhkan.

Definition

Pewarnaan graf yang tepat adalah penetapan warna pada verteks-verteksnya sehingga tidak ada dua verteks yang berdekatan berbagi warna yang sama; bilangan kromatik adalah jumlah warna terkecil yang memungkinkan penetapan tersebut.

Scope

Topik ini membahas pewarnaan verteks yang tepat dan bilangan kromatik, pewarnaan sisi dan indeks kromatik, polinomial kromatik yang menghitung pewarnaan, serta hasil-hasil penting termasuk teorema Brooks, teorema Vizing, dan Teorema Empat Warna untuk graf planar. Ini mengaitkan pewarnaan dengan independensi, klik, dan teori parameter graf yang lebih luas.

Core questions

• Berapa jumlah warna paling sedikit yang dibutuhkan untuk mewarnai graf tertentu dengan tepat?
• Berapa banyak pewarnaan yang tepat dengan palet tertentu yang dapat diterima oleh suatu graf?
• Graf mana yang dapat diwarnai dengan sedikit warna, dan hambatan apa yang memaksa banyak warna?
• Bagaimana pewarnaan sisi dan pewarnaan daftar memperluas gagasan dasar?

Key concepts

• Pewarnaan verteks yang tepat
• Bilangan kromatik
• Polinomial kromatik
• Pewarnaan sisi dan indeks kromatik
• Teorema Brooks
• Teorema Empat Warna

Key theories

Teorema Empat Warna

Setiap graf planar dapat diwarnai dengan tepat menggunakan paling banyak empat warna, sebuah pernyataan yang terbuka selama lebih dari satu abad dan pertama kali dibuktikan oleh Appel dan Haken pada tahun 1976 menggunakan analisis kasus ekstensif yang dibantu komputer.

Teorema Vizing

Sisi-sisi dari setiap graf sederhana dapat diwarnai dengan tepat menggunakan derajat maksimum atau satu lebih dari derajat maksimum warna, membagi semua graf menjadi dua kelas sempit.

Clinical relevance

Pewarnaan memodelkan alokasi sumber daya bebas konflik: penjadwalan tanpa bentrokan, alokasi register dalam kompilator, penetapan frekuensi dalam jaringan nirkabel, dan masalah kendala gaya Sudoku semuanya dapat direduksi menjadi pewarnaan graf.

History

Konjektur Empat Warna, yang diajukan pada tahun 1852, mendorong banyak teori pewarnaan; bukti yang dibantu komputer pada tahun 1976 oleh Appel dan Haken merupakan tonggak awal dalam matematika yang dibantu komputer dan memicu perdebatan tentang sifat bukti.

Debates

Status bukti yang dibantu komputer

Ketergantungan Teorema Empat Warna pada kasus-kasus yang diperiksa mesin menimbulkan pertanyaan apakah bukti yang terlalu panjang untuk diverifikasi secara manual oleh manusia harus dianggap sebagai bukti matematika yang asli.

Key figures

• Kenneth Appel
• Wolfgang Haken
• Vadim Vizing

Seminal works

• diestel2017

Frequently asked questions

Apa itu bilangan kromatik dari suatu graf?

Ini adalah jumlah warna terkecil yang dibutuhkan agar verteks-verteks yang berdekatan selalu menerima warna yang berbeda; misalnya, siklus ganjil memiliki bilangan kromatik tiga.

Apakah Teorema Empat Warna berlaku untuk semua peta?

Ini berlaku untuk peta yang digambar pada bidang atau bola di mana wilayah-wilayahnya terhubung; peta pada permukaan seperti torus mungkin membutuhkan lebih banyak warna.