APLIKASI PEWARNAAN GRAF PADA PENJADWALAN PERKULIAHAN DI PROGRAM STUDI PENDIDIKAN MATEMATIKA UNWIDHA KLATEN Tasari*
Abstrak : Tujuan penelitian ini adalah untuk mengaplikasikan pewarnaan graf pada penjadwalan perkuliahan di Program Studi Pendidikan Matematika Unwidha Klaten. Metode penelitian yang digunakan adalah studi literatur. Setelah data diperoleh dari literatur utama maupun literatur pendukung, selanjutnya dianalisis untuk mengetahui aplikasi pewarnaan graf pada penjadwalan perkuliahan di Program Studi Pendidikan Matematika Unwidha Klaten. Kesimpulan dari penelitian ini adalah pewarnaan graf dapat diaplikasikan pada penjadwalan perkuliahan di Program Studi Pendidikan Matematika Unwidha Klaten. Pada penelitian ini hanya diambil satu semester sebagai sampel, yaitu semester genap. Dalam pewarnaan grafnya harus memperhatikan beberapa komponen-komponen penting yang berhubungan erat dengan penjadwalan perkuliahan, antara lain banyaknya tingkatan semester, banyaknya kelas, banyaknya matakuliah, dan banyaknya waktu yang tersedia dalam perkuliahan (hari dan jam matakuliah). Kata kunci: Pewarnaan Graf, Penjadwalan Perkuliahan
Pewarnaan titik pada graf
PENDAHULUAN Salah satu cabang ilmu matematika adalah teori graf. Pada teori graf diberikan model matematika untuk setiap himpunan dari sejumlah obyek diskrit, dimana beberapa pasangan unsur dari himpunan tersebut terikat menurut suatu aturan tertentu. Obyek diskrit dari himpunan tersebut misalnya dapat berupa orang-orang dengan aturan kenal, atau juga himpunan nama kota dengan aturan jalan yang menghubungkan antara kota satu ke kota yang lain. Saat ini teori graf semakin berkembang dan menarik karena keunikan dan banyak sekali penerapannya. Keunikan teori graf adalah kesederhanaan pokok bahasan yang dipelajarinya, karena dapat disajikan sebagai titik (vertex) dan sisi (edge).
adalah pemberian warna untuk setiap titik pada graf sehingga tidak ada dua titik yang terhubung langsung berwarna sama. Sedangkan 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. Pewarnaan graf mempunyai penerapan yang cukup luas, salah satuya adalah Penjadwalan Perkuliahan di Program Studi Pendidikan Matematika Unwidha Klaten. Dimana pada Prodi Pendidikan Matematika ada beberapa tingkatan semester, mulai semester satu sampai semester delapan. Tujuan penjadwalan adalah untuk memperoleh kemungkinan waktu dan tempat yang paling efisien. Bagaimana mengatur jadwal kuliah
* Staf Pengajar Prodi Pendidikan Matematika FKIP UNWIDHA Klaten
70
Magistra No. 82 Th. XXIV Desember 2012 ISSN 0215-9511
Aplikasi Pewarnaan Graf Pada Penjadwalan Perkuliahan di Progdi ....
untuk beberapa semester yang ada agar waktu yang diperlukan dan tempat yang digunakan untuk kuliah tidak saling tumpang tindih. Selain itu juga, bagaimana agar jadwal yang ada tidak melebihi dari waktu atau jam kuliah yang telah ditetapkan.
METODE PENELITIAN Metode penelitian yang digunakan adalah studi literature. Buku-buku yang dijadikan sebagai acuan pada penelitian ini antara lain Matematika Diskrit, Graph an Introductiory Approach. Disamping itu juga digunakan data-data dari Prodi Pendidikan Matematika seperti sebaran matakuliah, tingkatan semester yang ada, ruang kuliah yang ada. Setelah data diperoleh dari literatur utama maupun literatur pendukung, selanjutnya dianalisis untuk mengetahui aplikasi pewarnaan graf pada penjadwalan perkuliahan di Program Studi Pendidikan Matematika Unwidha Klaten.
PEMBAHASAN 1.
Kurikulum S1 Pendidikan Matematika Unwidha Klaten Guna menyelesaikan studi S1 pada Prodi Pendidikan Matematika Unwidha Klaten setiap mahasiswa reguler harus menempuh 159 SKS. Di bawah ini disajikan semua matakuliah yang ditempuh bagi mahasiswa Prodi Pendidikan Matematika.
Magistra No. 82 Th. XXIV Desember 2012 ISSN 0215-9511
1. No. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15.
2. No. 1. 2. 3. 4. 5. 6. 7. 8. 9.
Mata Kuliah Dasar Umum Kode MK MKU 4020 MKU 4010 MKU 4050 MKU 4060 MKU 4110 MKU 4040 MKU 4070 KIP 4010 KIP 4020 KIP 4030 KIP 4040 KIP 4050 KIP 4060 MKU 4030 MKU 4100
Nama Matakuliah Pendidikan Agama Pendidikan Pancasila BahasaInggris I BahasaInggrisII Komputer Dasar Bahasa Indonesia Ilmu Sosial Budaya Dasar Pengantar Pendidikan Psikologi Pendidikan Belajar dan Pembelajaran Bimbingan dan Konseling Profesi Kependidikan Administrasi Pendidikan Pend. Kewarganegaraan Kewirausahaan
SKS 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
Kelompok MPK MPK MPK MPK MPK MPK MPK MKK MKK MKK MKK MKK MKK MPK MPK
MATA KULIAH INTI Kode MK MAT 4011 MAT 4021 MAT 4031 MAT 4040 MAT 4050 MAT 4060 MAT 4012 MAT 4022 MAT 4032
Nama Matakuliah KalkulusI FisikaDasarI Kimia Dasar I Biologi Umum Peng. Dasar Matematika Trigonometri KalkulusII FisikaDasarII KimiaDasar II
SKS 2 3 3 3 2 2 2 3 3
Kelompok MKB MKB MKB MKB MKB MKB MKB MKB MKB
10. MAT 4070 11. MAT 4081
Pengetahuan Lingkungan AljabarI
3 2
MKB MKB
12. 13. 14. 15. 16. 17. 18. 19. 20.
TeoriBilangan AljabarII AljabarMatriks Geometri KalkulusLanjutI Komputer Program I InteraksiBelajarMengajar StrategiBelajarMengajar Program Linier
2 2 2 2 2 2 2 2 2
MKB MKB MKB MKB MKB MBB MKB MKB MKB
MAT 4090 MAT 4082 MAT 4100 MAT 4110 MAT 4121 MAT 4131 MAT 4340 MAT 4350 MAT 4140
71
Aplikasi Pewarnaan Graf Pada Penjadwalan Perkuliahan di Progdi .... 21. 22. 23. 24. 25. 26. 27.
MAT 4132 MAT 4151 MAT 4161 MAT 4170 MAT 4122 MAT 4180 MAT 4360
28. MAT 4370 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39.
MAT 4191 MAT 4200 MAT 4152 MAT 4210 MAT 4221 MAT 4162 MAT 4231 MAT 4240 MAT 4133 MAT 4300 MAT 4490
40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55.
MAT 4250 MAT 4232 MAT 4222 MAT 4134 MAT 4261 MAT 4390 MAT 4400 MAT 4000 MAT 4192 MAT 4470 MAT 4262 MAT 4301 MAT 4311 MAT 4302 MAT 4312 MAT 4500
72
Komputer Program II 2 GeometriAnalitikI 2 StatistikaDasarI 2 Matematika Diskrit 2 KalkulusLanjutII 2 Matematika Ekonomi 2 Perencanaan Pengajaran 2 Matematika Evaluasi Proses dan Hasil 2 Belajar AljabarLinierI 2 Riset Operasi 2 GeometriAnalitikII 2 PersamaanDiferensialBiasa 2 StrukturAljabarI 2 StatistikaDasarII 2 TelaahKurikulumMat.SMAI 2 Metode Numerik 2 Komputer Program III 2 Micro Teaching 2 Program Pengalaman 2 Lapangan Geometri Transformasi 2 Telaah Kurikulum Mat SMA II 2 StrukturAljabarII 2 Komputer Program IV 2 StatistikaMatematikaI 2 Seminar Matematika 2 MetodologiPenelitian 2 Kuliah Kerja Lapangan 2 AljabarLinierII 2 KKN/KKT 3 StatistikaMatematikaII 2 AnalisRealI 2 Analisis Kompleks I 2 AnalisisRealII 2 AnalisisKompleks II 2 Skripsi 6
MBB MKB MKB MKB MKB MKB MKB MKB MKB MKB MKB MKB MKB MKB MKB MKB MKB MBB MPB MKB MKB MKB MBB MKB MPB MKB MBB MKB MPB MKB MKB MKB MKB MKB MPB
3.
Mata Kuliah Pilihan
No. 1. 2. 3.
Kode MK MAT 4270 MAT 4220 MAT 4281
4.
MAT 4291
5. 6.
MAT 4320 MAT 4282
7.
MAT 4292
8.
MAT 4330
2.
Nama Mata Kuliah Model Matematika PersamaanDiferensialParsial Telaah Kurikulum Matematika SD I Telaah Kurikulum Matematika SMP I Rancangan Percobaan Telaah Kurikulum Matematika SD II Telaah Kurikulum Matematika SMP II Masalah Nilai Awal dan Syarat Batas
SKS 2 2 2
Kelompok MKB MKB MKB
2
MKB
2 2
MKB MKB
2
MKB
2
MKB
Keterbatasan Ruang dan Waktu Dalam melaksanakan perkuliahan Program Studi Pendidikan Matematika dialokasikan menempati 3 ruang (non laboratorium) yakni ruang G.1.2, G.1.4, dan G.1.5 dan waktu perkuliahan efektif hanya lima hari yaitu Senin sampai Jum’at. Batasan waktu dalam setiap harinya adalah dari pukul 07.30 WIB sampai dengan pukul 15.40 WIB. Sedangkan jumlah kelas yang ada lebih banyak dibandingkan dengan jumlah ruangan yang disediakan, yaitu ada sebanyak sebelas kelas. Semua itu adalah semester I/II ada tiga kelas, semester III/IV ada tiga kelas, semester V/VI ada tiga kelas, dan semester VII/VIII ada dua kelas. Dengan demikian jelas terlihat bahwa kebutuhan akan ruang perkuliahan sangat besar. Dalam pembahasan ini, peneliti hanya mengambil sampel sebanyak lima dari sebelas kelompok kelas dalam tiap semesternya untuk mempermudah pembahasan.
Magistra No. 82 Th. XXIV Desember 2012 ISSN 0215-9511
Aplikasi Pewarnaan Graf Pada Penjadwalan Perkuliahan di Progdi ....
Dari gambar graf di atas, untuk masing-
GAMBAR GRAF PENJADWALAN
masing semester mempunyai jadwal kuliah mulai hari Senin sampai dengan hari Jum’at. Demikian
Pada Program Studi Pendidikan Matematika Unwidha Klaten, terdapat dua semester dalam tiap tahunnya, yaitu semester gasal dan genap. Untuk
pula dengan ruang perkuliahan, masing-masing semester mempunyai ruang kuliah di gedung
masing-masing tingkatan yang masih aktif melakukan perkuliahan ada empat tingkatan, pada semester gasal yaitu semester I, III, V, dan VII. Pada semester genap yaitu semester II, IV, VI, dan VIII. Karena banyaknya tingkatan semester dan terbatasnya ruang perkuliahan, sedangkan hari efektif perkuliahan adalah Senin
G.1.2, G.1.4 dan G.1.5. Jika dua sisinya bertemu pada titik yang sama, maka perkuliahan tidak dapat dilakukan secara serempak atau bersamasama. b.
hingga Jum’at, maka diperlukan penjadwalan yang paten atau konsisten agar tidak terjadi tumpang tindih ruang ataupun waktu dalam proses perkuliahan.
Sebagaimana telah disampaikan di atas tentang matakuliah yang harus ditempuh sesuai dengan sebaran matakuliah tiap semester, maka yang dapat digambarkan adalah sebagai berikut:
Waktu perkuliahan untuk setiap harinya adalah pukul 07.30 - 15.40 WIB. Waktu perkuliahan kuliah tersebut adalah: 1.
Pukul 07.30 – 09.10 WIB
2.
Pukul 09.20 – 11.00 WIB
3.
Pukul 11.10 – 12.50 WIB
4.
Pukul 14.00 – 15.40 WIB
Penjadwalan kuliah tersebut dilakukan dengan terlebih dahulu mengekspresikan seluruh obyek atau komponen yang ada dalam bentuk graf. a.
Graf antara Banyaknya Matakuliah per Semester, Banyaknya Hari dan Banyaknya Ruang Kuliah
Gbr. 2. Graf antara Banyaknya Matakuliah per Semester, Banyaknya Hari, dan Banyaknya Ruang Kuliah
Graf antara Banyaknya Tingkatan Semester, Banyaknya Hari dan Banyaknya Ruang Kuliah
Dari gambar graf di atas, ketiga jenis matakuliah A, B, dan C masing-masing menempati ruang G.1.2, G.1.4, dan G.1.5. Untuk masing-masing matakuliah mempunyai jadwal
Contoh graf antara banyaknya tingkatan semester, banyaknya hari dan banyaknya ruang
kuliah mulai hari Senin sampai dengan hari Jum’at.
kuliah adalah sebagai berikut:
c.
Pewarnaan Graf dalam Penjadwalan Pewarnaan yang digunakan pada graf penjadwalan ini yaitu pewarnaan sisi.
Gbr. 1. Graf antara Banyaknya Tingkatan Semester, Banyaknya Hari, dan Banyaknya Ruang Kuliah
Magistra No. 82 Th. XXIV Desember 2012 ISSN 0215-9511
Pewarnaan sisi yaitu pemberian warna pada sisisisi suatu graf sedemikian hingga setiap dua sisi yang bertemu pada titik yang sama mendapatkan
73
Aplikasi Pewarnaan Graf Pada Penjadwalan Perkuliahan di Progdi ....
warna berbeda. Kemudian dari pewarnaan tersebut dicari bilangan kromatiknya, yaitu banyaknya warna minimum yang dapat digunakan untuk mewarnai sisi. Penjadwalan diambil hanya untuk semester genap. Berdasarkan graf pada gambar 1 dapat dikatakan bahwa apabila terdapat dua sisi bertemu pada titik yang sama, maka kuliah tidak dapat dilakukan pada hari dan ruang yang sama. Warna-warna yang berbeda dapat diberikan pada
Jadi minimal bisa diwarnai dengan empat warna sehingga bilangan kromatiknya (G) = 4. Warna yang berbeda menyatakan bahwa waktu kuliah bisa dilaksanakan di hari yang sama, yaitu: Warna 1 untuk (IIA, G1.2), (IIB, G1.4) dan (IVB, G1.5) Warna 2 untuk (IIA, G1.4), (IIB, G1.2) dan (VIA, G1.5) Warna 3 untuk (IVA, G1.2) dan (IVB, G1.4) Warna 4 untuk (IVA, G1.4) dan (VIA, G1.2) 2) Hari Selasa
sisi graf yang menunjukkan bahwa jadwal kuliahnya tidak bersamaan pada hari dan tempat yang sama. Diinginkan jadwal kuliah seefisien mungkin untuk memudahkan pelaksanaannya. Jadi harus ditentukan bilangan kromatik grafnya. Jadi gambar grafnya adalah seperti berikut: Gambar 5. Pewarnaan sisi Graf Semester Genap Hari Selasa
Gbr. 3. Pewarnaan sisi Graf antara Banyaknya Tingkatan Semester, Banyaknya Hari dan Banyaknya Ruang Kuliah
Jadi minimal bisa diwarnai dengan tiga warna sehingga bilangan kromatiknya (G) = 3. Warna yang berbeda menyatakan bahwa waktu kuliah bisa dilaksanakan di hari yang sama, yaitu: Warna 1 untuk (IIA, G.1.4), (IIB, G.1.2) dan (VIA, G.1.5)
a) Pewarnaan Harian 1) Hari Senin
Warna 2 untuk (IIA, G.1.2), (IIB, G.1.4) dan (IVA, G.1.5) Warna 3 untuk (IVA, G.1.4) dan (IVB, G.1.2)
Gbr. 4. Pewarnaan sisi Graf Smt.r Genap Hari Senin
74
Magistra No. 82 Th. XXIV Desember 2012 ISSN 0215-9511
Aplikasi Pewarnaan Graf Pada Penjadwalan Perkuliahan di Progdi ....
3) Hari Rabu
Warna 1 untuk (IIA, G1.4), (IIB, G1.2) dan (IVA, G1.5) Warna 2 untuk (IIA, G1.2), (IIB, G1.4) dan (IVB, G1.5) Warna 3 untuk (IVA, G1.2), (IVB, G1.4) dan (VIA, G1.5)
Gambar 6. Pewarnaan sisi Graf Semester Genap Hari Rabu
Warna 4 untuk (IVB, G1.2) dan (VIA, G1.4) 5) Hari Jum’at
Jadi minimal bisa diwarnai dengan empat warna sehingga bilangan kromatiknya (G) = 4. Warna yang berbeda menyatakan bahwa waktu kuliah bisa dilaksanakan di hari yang sama, yaitu: Warna 1 untuk (IIA, G1.2), (IIB, G1.4) dan (IVA, G1.5) Warna 2 untuk (IIA, G1.4), (IIB, G1.2) dan (IVB, G1.5) Warna 3 untuk (IVA, G1.2), (IVB, G1.4) dan (VIA, G1.5) Warna 4 untuk (VIA, G1.4) 4) Hari Kamis
Gambar 8. Pewarnaan sisi Graf Semester Genap Hari Jum’at Jadi minimal bisa diwarnai dengan tiga warna sehingga bilangan kromatiknya (G) = 3. Warna yang berbeda menyatakan bahwa waktu kuliah bisa dilaksanakan di hari yang sama, yaitu: Warna 1 untuk (IIA, G1.2), (IIB, G1.4) dan (VIA, G1.5) Warna 2 untuk (IIA, G1.4), (IIB, G1.2) dan (IVA, G1.5) Warna 3 untuk (IVA, G1.2) dan (IVB, G1.4) b) Pewarnaan berdasarkan Jam Matakuliah 1) Hari Senin
Gambar 7. Pewarnaan sisi Graf Semester Genap Hari Kamis
Jadi minimal bisa diwarnai dengan empat warna sehingga bilangan kromatiknya (G) = 4. Warna yang berbeda menyatakan bahwa waktu kuliah bisa dilaksanakan di hari yang sama, yaitu:
Magistra No. 82 Th. XXIV Desember 2012 ISSN 0215-9511
75
Aplikasi Pewarnaan Graf Pada Penjadwalan Perkuliahan di Progdi ....
3) Hari Rabu
Gambar 9. Graf Jadwal Kuliah Semester Genap Hari Senin 2) Hari Selasa
Gambar 11. Graf Jadwal Kuliah Semester Genap Hari Rabu 4) Hari Kamis
Gambar 10. Graf Jadwal Kuliah Semester Genap Hari Selasa
Gambar 12. Graf Jadwal Kuliah Semester Genap Hari Kamis
76
Magistra No. 82 Th. XXIV Desember 2012 ISSN 0215-9511
Aplikasi Pewarnaan Graf Pada Penjadwalan Perkuliahan di Progdi ....
5) Hari Jum’at
PEMBAHASAN Dari hasil pewarnaan graf antara banyaknya tingkatan semester, banyak hari, dan banyaknya ruang kuliah yaitu dengan membagi pewarnaan tersebut dari pewarnaan dalam satu minggu menjadi pewarnaan harian hingga pewarnaan berdasarkan jam matakuliah, maka bilangan kromatik yang diperoleh semakin kecil. Hal tersebut karena derajat titik graf akan semakin berkurang, di mana banyaknya minimum pewarnaan atau bilangan kromatik graf bipartit adalah derajat terbesar titik yang dimiliki oleh graf, sebagaimana yang telah dijelaskan dalam teorema Konig. Pada semester genap, dalam seminggu hanya
Gambar 13. Graf Jadwal Kuliah Semester Genap Hari Jum’at
terpakai selama lima hari dari hari Senin sampai dengan Jum’at untuk perkuliahan. Masing-masing jam perkuliahan hampir semua penuh.
Pewarnaan sisi berdasarkan jam matakuliah
Dengan demikian, jadwal yang terbentuk dari
pada masing-masing gambar graf di atas yaitu setiap
hasil pewarnaan graf adalah lima hari aktif dalam
sisinya tidak mempunyai hubungan dengan sisi yang
seminggu terpakai untuk jam perkuliahan mahasiswa
lain. Dengan demikian cukup diwarnai dengan satu
Prodi Pendidikan Matematika Unwidha Klaten.
warna saja, sehingga = 1 Penjadwalan kuliah semester genap mulai dari hari Senin sampai dengan hari Jum’at menunjukkan
SIMPULAN
bahwa untuk semester II hanya kuliah pada pukul
Dalam pewarnaan graf harus memperhatikan
09.20–12.50 WIB. Sedangkan untuk semester IV dan
beberapa komponen penting yang berhubungan erat
VI mulai pukul 07.30–15.40 WIB. Untuk semester II
dengan penjadwalan kuliah, antara lain banyaknya
masing-masing kelas ada sembilan pertemuan yang
tingkatan semester, banyaknya kelas, banyaknya
sesuai dengan jumlah matakuliah beserta bobot
matakuliah, dan banyaknya waktu yang tersedia dalam
semester yang ditempuh, semester IV ada duabelas
perkuliahan (hari dan jam matakuliah).
pertemuan untuk masing-masing kelas dan semester VI ada duabelas pertemuan. Maksimal untuk tiga ruang kelas perkuliahan pada masing-masing jam ditempati satu semester.
Magistra No. 82 Th. XXIV Desember 2012 ISSN 0215-9511
77
Aplikasi Pewarnaan Graf Pada Penjadwalan Perkuliahan di Progdi ....
Pewarnaan graf di atas yaitu pewarnaan antara banyaknya tingkatan semester, banyak hari, dan banyaknya ruang kuliah. Hasil pewarnaan grafnya diperoleh bilangan kromatik yang semakin kecil. Pada semester genap, dalam seminggu hanya terpakai selama lima hari yakni hari Senin sampai
DAFTAR PUSTAKA Lipschutz, Seymour dan Lipson, Marc Lars (diterjemahkan oleh Tim Editor Penerbit Salemba Teknika). Matematika Diskrit 2. Jakarta: Salemba Teknika
dengan Jum’at untuk perkuliahan. Masing-masing jam
Munir, Rinaldi. 2003. Matematika Diskrit. Bandung: Informatika Bandung
perkuliahan hampir semua penuh.
Murty dan Bondy. 1976. Graph Theory with
Dari hasil pewarnaan tersebut dapat diambil
Applications. Canada: The Macmillan Press LTD
kesimpulan bahwa minimal ada tiga ruang kelas untuk
Tim Penyusun. 2006. Pedoman Akademik 2006/2009
perkuliahan, dengan lima hari perkuliahan (Senin-
Universitas Widya Dharma Klaten. Klaten: UNWIDHA
Jum’at) dimulai dari pukul 07.30-15.40 WIB.
Wilson, Robin J dan Watkins, John J (diterjemahkan oleh Dra. Theresia MH Tirta Seputro, M.Pd). 1990. Graph An Introductory Approach. Canada: Wiley.
78
Magistra No. 82 Th. XXIV Desember 2012 ISSN 0215-9511