Algoritma Graph Coloring


Algoritma Graph Coloring adalah salah satu algoritma yang digunakan untuk pengambilan keputusan. Contoh yang dibahas kali ini adalah menentukan penjadwalan mata kuliah sederhana.



Diasumsikan ada 4 slot waktu yang tersedia, yaitu slot S1, S2, S3, S4
dan ada 3 ruang yang tersedia, yaitu R1, R2, R3
Berapa mata kuliah yang dapat dimasukkan seminimal mungkin dan memenuhi syarat berikut:
– Tidak ada mata kuliah yang diajarkan pada slot waktu yang sama
– Tidak ada mata kuliah yang diajarkan pada ruang yang sama

Jika diilustrasikan dalam tabel, maka model penjadwalan adalah sebagai berikut

Slot/Ruang R1 R2 R3
S1 ?? ?? ??
S2 ?? ?? ??
S3 ?? ?? ??
S4 ?? ?? ??



Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
Tentukan jumlah titik yang digunakan
Diasumsikan dalam kasus ini, jumlah titik adalah 4 slot waktu * 3 ruang = 12


Langkah-langkah penggunaan algoritma ini adalah

1. Inisialisasi semua variabel yang diperlukan, yaitu variabel gambar, titik, dan garis
Penjelasan tentang masing-masing class akan dijelaskan pada skrip dibawah ini

* Agar dapat menjalankan skrip diatas, maka diperlukan sebuah 4 buah class
Class Titik digunakan untuk menampung data indeks, jumlah tetangga, dan warna titik tersebut
Class Garis digunakan untuk menampung data titik awal, dan titik tujuan garis tersebut
Class Gambar digunakan untuk menampung semua data titik dan semua data garis yang digunakan
Deklarasi masing-masing class adalah sebagai berikut:

2. Masukkan data titik dan garis kedalam masing-masing variabel yang tersedia
data garis yang digunakan adalah mengikuti deskripsi batasan yang sudah dijelaskan sebelumnya
sehingga beri garis pada titik yang berada pada slot waktu atau ruang yang sama

Jika diilustrasikan dalam gambar, maka model graphnya adalah sebagai berikut
graph-coloring-awal

3. Hitung jumlah titik tetangga dari masing-masing titik yang terhubung oleh garis

4. Lakukan pengurutan perhitungan sehingga titik yang dihitung lebih dulu adalah titik dengan jumlah titik tetangga terbanyak sampai pada titik tetangga yang paling sedikit

* Lakukan perhitungan untuk mendapatkan urutan titik dan banyak warna yang digunakan (poin 5)

5. Lakukan perhitungan pada masing-masing titik (poin 5a – 5d)

5a. Dapatkan titik yang sedang digunakan

5b. Lakukan perhitungan pada masing-masing garis
Tandai semua titik lain yang terhubung dengan titik yang sedang dihitung

5c. Lakukan perhitungan pada semua titik
Masukkan semua titik yang tidak terhubung dengan titik yang sedang dihitung secara berurutan,
tapi pastikan juga bahwa tidak ada titik yang sama dimasukkan lebih dari 1 kali
Jika semua titik sudah masuk dalam urutan maka hentikan perhitungan

5d. Jika ditemukan titik yang tidak terhubung dengan titik yang sedang dihitung, maka tambahkan jumlah warna yang digunakan
Jika semua titik sudah masuk dalam urutan maka hentikan perhitungan

6. Lakukan inisialisasi warna sebanyak jumlah warna yang diperlukan

* Lakukan perhitungan untuk memberikan warna pada masing-masing titik (poin 7)

7. Lakukan perhitungan sesuai urutan titik yang sudah ditentukan sebelumnya (poin 7a – 7c)

7a. Dapatkan titik yang sedang digunakan

7b. Lakukan perhitungan pada masing-masing garis
Tandai semua warna yang sudah digunakan pada titik yang terhubung dengan titik yang sedang dihitung

7c. Beri warna titik ini dengan warna yang belum digunakan pada titik yang terhubung dengan titik yang sedang dihitung
Kemudian tandai bahwa titik ini sudah diberi warna

* Tampilkan hasil kesimpulan jumlah warna pada layar
Kemudian tampilkan data mata kuliah yang dapat dimasukkan pada jadwal kuliah


Hasil akhir adalah: (klik untuk perbesar gambar)

cmd153

Jika diilustrasikan dalam tabel, maka hasil penjadwalan adalah sebagai berikut

Slot/Ruang R1 R2 R3
S1 Mata Kuliah #01 Mata Kuliah #04 Mata Kuliah #03
S2 Mata Kuliah #03 Mata Kuliah #01 Mata Kuliah #02
S3 Mata Kuliah #04 Mata Kuliah #02 Mata Kuliah #01
S4 Mata Kuliah #02 Mata Kuliah #03 Mata Kuliah #04

Jika diilustrasikan dalam gambar, maka model hasil akhirnya adalah sebagai berikut
graph-coloring-akhir


Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:



Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.

Tinggalkan sebuah komentar

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *