APLIKASI PEWARNAAN GRAF PADA PENJADWALAN PERKULIAHAN DI PROGRAM STUDI PENDIDIKAN MATEMATIKA UNWIDHA KLATEN

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.


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.



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


Pewarnaan sisi yaitu pemberian warna pada sisisisi suatu graf sedemikian hingga setiap dua sisi yang bertemu pada titik yang sama mendapatkan

73


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



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:


75


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



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.


77


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


APLIKASI PEWARNAAN GRAF PADA PENJADWALAN PERKULIAHAN DI PROGRAM STUDI PENDIDIKAN MATEMATIKA UNWIDHA KLATEN

Recommend Documents