Aplikasi pewarnaan Graf terhadap penjadwalan kuliah di jurusan Matematika UIN Malang

ABSTRAK

Graf adalah diagram atau himpunan yang terdiri dari noktah-noktah yang disebut titik dan dihubungkan oleh garis-garis yang disebut sisi, serta setiap sisi menghubungkan tepat dua titik. Dalam pandangan Al-Qur’an, teori graf adalah suatu himpunan yang terdiri atas pencipta (Allah) dan hamba-hambanya dimana diantara anggota himpunan tersebut saling berhubungan, yaitu hubungan antara pencipta dengan hambanya (QS. Qaaf/50: 16).

Teori graf telah banyak digunakan dalam kehidupan sehari-hari, misalnya dalam membuat jadwal kuliah di jurusan matematika UIN Malang. Dalam penjadwalan kuliah ini harus diperhatikan beberapa komponen-komponen penting yang berhubungan erat dengan penjadwalan kuliah. Seperti banyaknya tingkatan semester, banyaknya kelompok kelas, banyaknya mata kuliah, dan banyaknya waktu yang tersedia dalam perkuliahan (hari dan jam mata kuliah). Sehingga dapat diperoleh suatu kemungkinan jadwal yang sesuai dan efisien.

Pewarnaan graf dalam penjadwalan kuliah yaitu pewarnaan antara banyaknya tingkatan semester, banyak hari, dan banyaknya ruang kuliah; yang dibagi dalam pewarnaan selama satu minggu, pewarnaan harian dan pewarnaan berdasarkan jam matakuliah.

Pewarnaan graf dalam penjadwalan ini terbatas hanya pada pewarnaan sisi. Pewarnaan sisi-k untuk G adalah pemberian k warna pada sisi-sisi G sedemikian hingga setiap dua sisi yang bertemu pada titik yang sama mendapatkan warna berbeda. Kemudian dicari bilangan kromatiknya, yaitu banyaknya warna minimum yang dapat digunakan untuk mewarnai sisi.

Dari pewarnaan itu, minimal ada tiga ruang kelas untuk perkuliahan, dengan enam hari hari perkuliahan (senin—sabtu) dimulai jam 06.30—14.00 WIB. Dimana untuk semester I-II dimulai jam 08.10—11.30 WIB. Sedangkan untuk semester diatasnya mulai jam 06.30—14.00 WIB.

Penjadwalan kuliah di jurusan matematika ini erat hubungannya dengan manajemen waktu. Yaitu mengatur dan memanfaatkan waktu sebaik mungkin agar waktu yang ada tidak berlalu dengan sia-sia, sehingga kelak tidak termasuk pada golongan orang-orang yang merugi dikarenakan waktu (QS. Al-‘Ashr/103: 1—3).