Pewarnaan (Coloring) Dalam Metode Greedy

Algoritma merupakan suatu prosedur yang tepat untuk dapat memecahkan masalah dengan menggunakan bantuan komputer serta suatu bahasa pemograman tertentu. Pembahasan kali ini membahas tentang algoritma Greedy untuk pewarnaan pada Jenis zat yang perlu disimpan di gudang. Prinsip Greedy merupakan metode paling populer untuk menemukan solusi optimum dalam persoalan optimasi dengan membentuk solusi langkah-perlangkah. Pewarnaan peta merupakan masalah yang dapat diselesaikan menggunakan algoritma Greedy. Solusi terbaik dalam mewarnai peta adalah menggunakan jumlah warna minimum (bilangan kromatik) sehingga akan didapatkan solusi pewarnaAan optimal.

Studi Kasus :

          Ada 6 jenis zat kimia yang perlu disimpan digudang. Beberapa pasangan zat itu tidak dapat disimpan ditempat yang sama, karena campuran gasnya bersifat eksplosif. Berikut ini adalah daftar pasangan zat kimia yang tidak dapat disimpan di tempat yang sama.

Gambarkan pewarnaan yang menyatakan persoalan. Kemudian tentukan jumlah minimum ruangan yang dibutuhkan untuk menyimpan semua zat kimia diatas.

Zat Kimia	Tidak Dapat Disimpan Ditempat Yang sama
A	B,D
B	A,D,E,F
C	E
D	A,F,B
E	B,C
F	B,D

Langkah-langkah penyelesaian masalah :

Berdasarkan graf tersebut dapat disimpulkan, bahwa apabila terdapat dua simpul yang dihungkan oleh sisi, maka kedua zat kimia tersebut tidak dapat disimpan dalam ruangan yang sama, jadi dua simpul tersebut tidak boleh mempunyai warna yang sama.

Oleh karena itu, didapat hasil jumlah minimum ruangan yang dibutuhkan untuk meyimpan semua zat kimia tersebut adalah 3 ruangan, yaitu :

Ruang 1 (Biru)             = A ; F

Ruang 2 (Kuning)        = B ; C

Ruang 3 (Merah)         = E ; D