Pewarnaan (Coloring)

Pewarnaan yang kita bahas kali ini adalah sebuah cara yang digunakan untuk menyelesaiakan proses panjadwalan. Dimana dalam pewarnaan ini akan digambarkan dengan graph yang terdiri atas simpul, dan ruas

Dalam kehidupan sehari-hari sering kali kita dipusingkan oleh rumitnya penjadwalan, misalnya jika kita harus membuat jadwal ujian dimana ada beberapa mahasiswa yang mengikuti beberapa mata kuliah, tentunya agar mahasiswa tersebut dapat mengikuti  semua ujian, maka mata kuliah yang diambil secara bersamaan oleh satu siswa tersebut tidak boleh dijadwalkan pada hari dan jam yang sama. Atau misalnya kita mendapatkan proyek untuk membuat  lampu lalulintas di sebuah perlimaan, maka kita harus mengatur nyala lampu merah dan hijau agar tidak terjadi tabrakan. Saat ini kita akan belajar bersama salah satu metode untuk mengatasi permasalahan tersebut dengan metode pewarnaan (Coloring).

Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek. Representasi visual dari graf adalah dengan menyatakan objek dengan simpul, noktah, bulatan, titik, atau vertex, sedangkan hubungan antara objek dinyatakan dengan garis , edge atau ruas.

Pewarnaan graf adalah proses pelabelan setiap simpul dalam graf dengan label tertentu (warna) sehingga tidak ada dua simpul bertetangga yang memiliki warna sama. Warna yang kita gunakan untuk mewarnai objek diusahakan seminimal mungkin. Jumlah warna minimum yang dapat digunakan untuk mewarnai simpul disebut bilangan kromatik

.
beberapa contoh permasalahan yang bisa diselesaiakan dengan pewarnaan adalah

Penjadwalan Ujian
Pengaturan Warna Pada Lampu Lalu Lintas