Penjadwalan Ujian

Kali ini kita akan mencoba memecahkan masalah penjadwalan dengan cara melakukan pewarnaan pada sebuah graf.

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

Tabel berikut adalah contoh penjadwalan kuliah dalam graf:

Tabel 1 Contoh tabel penjadwalan kuliah 

Gambar 1

Pada tabel diatas 6 kolom yang dilambangkan dengan huruf menunjukan nama mata kuliah, sedangkan 8 baris yang ditunjukan dengan angka menunjukan mahasiswa, sedangkan angka 1 menandakan mata kuliah yang diambil, 0 berarti mata kuliah yg tdk diambil. 

Pada tabel diatas menunjukan adanya mahasiswa yang mengambil 2 mata kuliah sekaligus.

Maka berdasarkan tabel diatas, tim pembuat jadwal harus membuat jadwal, dimana siswa harus dapat mengikuti semua ujian dari mata kuliah yang diambil, berarti mata kuliah yang diambil bersamaan oleh seorang mahasiswa tidak boleh dijadwalkan pada waktu yang sama.

Maka untuk menyelesaikan permasalahan tersebut, hal yang dilakukan adalah

1. Menggambarkan Simpul yang menunjukan mata kuliah
2. Membuat ruas atau garis penghubung menyatakan ada mahasiswa yang memilih kedua mata kuliah itu.
3. Memilih simpul yang berwarna sama, simpul yang berwarna sama menunjukan tidak ada mahasiswa yang mengambil mata kuliah tersebut secara bersamaan, berarti boleh dijadwalkan pada waktu yang sama

untuk lebih jelasnya lihat gambar berikut

Gambar 2

Berdasarkan graf tersebut kita menyimpulkan, bahwa apabila terdapat dua buah simpul dihubungkan oleh sisi atau ruas, maka ujian kedua mata kuliah itu tidak dapat dibuat pada waktu yang sama. Maka untuk mempermudah kita bisa memberi warna pada masing-masing simpul, dimana warna yang berbeda dapat diberikan pada simpul graf yang menunjukkan bahwa waktu ujiannya berbeda, warna yang digunakan harus seminimal mungkin dengan ketentuan simpul yang berdampingan atau bertetangga tidak boleh berwarna sama, berikut cara pemberian warnanya.

Gambar 3

M = Merah

P = Putih

H = Hijau

Dari gambar diatas kita memulai memberikan pewarnaan pada simpul F dengan warna merah, kemudian kita memberi warna pada simpul A dengan warna putih, selanjutnya kita memberi warna simpul E dengan warna merah, dilanjutkan ke simpul B kita beri warna Putih, kemudian kita lanjutkan ke simpul D, kembali kita beri warna Merah, terakhir kita mewarnai simpul C dengan warna hijau, mengapa simpul C berwarna hijau, ini dikarenakan ketentuan yang telah kita bahas diatas, bahwa setiap simpul yang bertetangga tidak boleh berwarna sama, kita lihat simpul C bertetangga dengan simpul B yang berwarna putih, dan simpul D yang berwarna merah, maka simpul C harus diberi warna selain warna Merah dan Putih.

Kemudian kita kelompokan simpul yang mempunyai warna sama, simpul dengan warna sama berarti bisa dijadwalkan dalam waktu yang bersamaan karena tidak ada mahasiswa yang mengambil mata kuliah tersebut secara bersamaan, dari gambar 3 diperoleh hasil:

1. Simpul merah = F, E, D
2. Simpul Putih = A, B
3. Simpul hijau = C

Catatan: 

Untuk posisi peletakan Simpul Bisa Bebas

Awal pemberian warna boleh bebas

Warna yang digunakan Bebas

Awal pemberian warna mempengaruhi susunan Jadwal