Skripsi

Penerapan algoritma recursive largest first pada pewarnaan. Graph untuk penjadwalan kuliah / Marfuad

Abstrak
Kata kunci Pewarnaan Titik Graph Penjadwalan Kuliah Algoritma Recursive Largest First. Salah satu permasalahan dalam teori graph yang banyak berfungsi dalam kehidupan sehari-hari adalah masalah pewarnaan khususnya pewarnaan titik. Tujuan utama dari pewarnaan titik adalah mewarnai semua titik dalam suatu graph sedemikian sehingga tidak ada titik yang saling bertetangga memiliki warna yang sama dengan jumlah minimum yang disebut juga sebagai bilangan khromatik. Salah satu aplikasi pewarnaan titik dalam kehidupan sehari-hari adalah menyelesaikan masalah penyusunan jadwal kuliah. Terdapat banyak algoritma yang dapat menyelesaikan masalah pewarnaan titik salah satunya adalah algoritma recursive largest first. Prinsip dasar penyelesaian algoritma ini adalah dengan memilih titik yang berderajat terbesar sebagai titik awal kemudian mencari titik yang tidak bertetangga dengan titik awal sehingga titik-titik tersebut menjadi calon titik yang akan diwarnai sama dengan titik awal. Setelah calon titik tersebut diperoleh maka langkah selanjutnya adalah menyeleksi calon titik tersebut sehingga diperoleh titik mana saja yang dapat diwarnai sama dengan titik awal. Kemudian ulangi langkah-langkah tersebut sampai semua titik diwarnai. Tujuan penelitian ini adalah untuk menyelesaikan masalah pewarnaan titik dengan menggunakan algoritma recursive largest first untuk penjadwalan kuliah sehingga akan diperoleh jadwal matakuliah yang tidak bertabrakan baik jadwal dari pihak mahasiswa (offering mahasiswa) maupun dari jadwal dosen yang mengajar matakuliah tersebut serta jadwal pemakaian ruangan yang tidak sama pada waktu yang bersamaan. Tujuan lainnya adalah untuk membantu penyusunan jadwal kuliah dengan waktu yang relatif singkat. Dengan menggunakan algoritma ini untuk menyelesaikan masalah penjadwalan kuliah maka akan diperoleh informasi yang lebih cepat mengenai jumlah waktu minimum yang bisa digunakan untuk menyusun jadwal. Dalam skripsi ini dapat dilihat bahwa pewarnaan titik dengan algoritma recursive largest first dapat digunakan untuk menyelesaikan masalah penjadwalan kuliah dan variabel yang perlu diperhatikan adalah banyaknya matakuliah yang diambil oleh offering mahasiswa yang sama dan banyaknya matakuliah yang diajarkan oleh dosen yang sama. Sementara penjedwalan kuliah yang lebih kompleks seperti mempertimbangkan jam atau hari perkuliahan kapasitas kelas dan kondisi lainnya tidak dapat diselesaikan dengan menggunakan pewarnaan titik dengan algoritma recursive largest first.

Informasi Detail

DDC

Rs 511.352 MAR p

Prodi

Universitas Negeri Malang. Program Studi Matematika, 2011.

Deskripsi Fisik

viii, 115 lembar : il., tab. ; 30 cm.

Bahasa

Indonesia

No Reg

04355/KI/11

Edisi

Skripsi (Sarjana)--Universitas Negeri Malang, 2011

Subjek

1. ALGORITMA RECURSIVE
2. PENJADWALAN KULIAH

Pembimbing

1. SUSY KUSPAMBUDI ANDAINI ; 2. DARMAWAN SATYANANDA

Lampiran Berkas