Aplikasi pewarnaan Graf menggunakan Algoritma Welch-Powell pada penyusunan jadwal mata kuliah prodi matematika UIN Sunan Ampel Surabaya

This item is published by Universitas Islam Negeri Sunan Ampel Surabaya

Firdaus, Mir'atul (2020) Aplikasi pewarnaan Graf menggunakan Algoritma Welch-Powell pada penyusunan jadwal mata kuliah prodi matematika UIN Sunan Ampel Surabaya. Undergraduate thesis, UIN SUNAN AMPEL SURABAYA.

Text
Mir'atul Firdaus_H72216060.pdf
Download (7MB)

Abstract

Dalam kehidupan sehari-hari, penyusunan jadwal akan menyebabkan kekacauan jika tidak tersusun dengan benar. Penyusunan jadwal juga terjadi di bidang pendidikan seperti penyusunan jadwal mata kuliah yang dilakukan setiap semester. Pewarnaan graf merupakan bagian dari teori graf dan salah satu cabang dari ilmu matematika yang dapat digunakan dalam menyelesaikan suatu permasalahan yang berhubungan dengan penyusunan jadwal. Pewarnaan graf juga dapat diaplikasikan untuk menyelesaikan penjadwalan mata kuliah di Program Studi Matematika Fakultas Sains dan Teknologi UINSA. Terdapat tiga jenis pewarnaan graf yaitu pewarnaan titik, sisi dan wilayah. Jenis pewarnaan graf yang digunakan adalah pewarnaaan titik. Penyusunan jadwal kuliah pada penelitian ini menggunakan pewarnaan graf dengan Algoritma Welch-Powell. Algoritma Welch-Powell dapat digunakan untuk mewarnai sebuah graf secara efisien. Setelah dilakukan pewarnaan titik akan didapatkan bilangan kromatik. Bilangan kromatik (γ(G)) adalah jumlah minimum warna yang digunakan dalam mewarnai titik. Parameter yang digunakan adalah mata kuliah setiap tingkat semester, dosen pengampu mata kuliah, slot waktu dan hari efektif yang digunakan untuk perkuliahan, ruang kelas perkuliahan dan jumlah mahasiswa. Dengan langkah menghubungkan mata kuliah sebagai titik dan dosen sebagai sisi tersebut dalam bentuk graf, kemudian diterapkan Algoritma Welch-Powell untuk pewarnaan titiknya. Setelah itu, akan dilakukan pembagian kelas, ruang kuliah dan slot waktu untuk setiap semester di tiap hari efektif. Hasil dari pewarnaan graf didapatkan jumlah bilangan kromatik (γ(G))= 4.