Penerapan Aplikasi Pewarnaan Graf Pada Kasus Penjadwalan Kuliyah Semester Gasal Di Jurusan Matematika UIN Maulana Malik Ibrahim

Abstract

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. Teori graf telah banyak digunakan dalam kehidupan sehari-hari, misalnya dalam membuat jadwal kuliyah di jurusan matematika UIN Malang. Dalam penjadwalan kuliyah ini harus diperhatikan beberapa komponen-komponen penting yang berhubungan erat dengan penjadwalan kuliyah. Seperti banyaknya tingkatan semsster, banyaknya kelompok kelas, banyaknya mata kuliyah dan banyaknya waktu yang tersedia dalam perkuliahan (hari dan jam mata kuliyah), sehingga dapat diperoleh suatu kemungkinan jadwal yang sesuai dan efisien. Pewarnaan graf dalam penjadwalan kuliyah yaitu pewarnaan antara banyaknya tingkatan semester, banyaknya hari dan banyaknya ruang kuliyah yang dibagi dalam pewarnaan selama satu minggu, pewarnaan harian dan pewarnaan berdasarkan jam mata kuliyah. Pewarnaan graf pada penjadwalan ini terbatas hanya pada pewarnaan sisi. Pewarnaan sisi-k untuk G adalah pewarnaan k warna pada sisi-sisi G sedemikian sehingga setiap dua sisi yang bertemu pada titik yang sama mendapat warna yang 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 perkuliahan (Senin s/d Sabtu) dimulai pukul 06.30 WIB sampai dengan 14.00 WIB. Dimana untuk semester satu dimulai pukul 08.10 WIB sampai dengan 11.30 WIB. Sedangkan untuk semester di atasnya mulai pukul 06.30 WIB sampai dengan 14.00 WIB