Studi tentang Algoritma Prim dan Kruskal dalam penentuan pohon perentang minimum pada Layout Plan UIN Malang

ABSTRAK

Teori graf merupakan cabang matematika sekaligus pokok bahasan yang memiliki banyak terapan saat ini. Graf adalah satu alat yang digunakan untuk mencari solusi dari permasalahan diskret yang ditemui dalam dunia nyata. Pada skripsi ini menghadirkan graf dengan konsep pohon untuk memecahkan masalah yaitu mengkonstruksi graf menjadi pohon perentang minimum. Misalnya Lay Out Plan UIN Malang adalah gambar miniatur UIN Malang pada skala 1:2.250. Lay Out Plan tersebut adalah sebuah graf, yang dalam hal ini gedung-gedung dinyatakan sebagai titik dan jarak antara gedung dinyatakan sebagai sisi sekaligus bobot Pada gambar tersebut akan ditentukan jarak terpendek (mempunyai bobot minimum) antar gedung. Sehingga dapat digunakan untuk keperluan-keperluan penting, seperti penentuan pipa minimum pada penyaluran air dan kabel minimum pada penyaluran listrik dan telepon.

Algoritma Prim dan Kruskal adalah algoritma yang digunakan dalam membangun pohon perentang minimum. Bagaimanakah langkah-langkah kedua algoritma ini dalam menentukan pohon perentang minimum dari Lay Out Plan ا1لا Malang dan bagaimana perbandingan antara keduanya. Oleh sebab itu tujuan dari penelitian ini adalah unuk memahami langkah-langkah menentukan pohon perentang minimum dengan mengunakan algoritma Prim dan Kruskal serta menganalisa perbandingan kedua metode tersebut. Data yang digunakan adalah jarak antar gedung pada Lay Out Plan UIN dalam skala 1:2.250. Maka dalam skripsi ini jenis penelitian yang digunakan adalah studi kepustakaan (Library Research).

Hasil penelitian ini merupakan pendeskripsian langkah-langkah dalam menentukan pohon perentang minimum dengan menggunakan kedua algoritma. Setelah itu dilanjutkan dengan analisis perbandingan dari dua algoritma tersebut. Hasil penelitian menunjukkan bahwa jumlah langkah yang digunakan kedua algoritma memiliki kesamaan. Selain itu bentuk pohon perentang dan jumlah bobot minimumnya juga mempunyai kesamaan yaitu berjumlah 167.787. Yang membedakan antara algoritma Prim dengan algoritma Kruskal adalah pada pemilihan sisi. Jika algoritma Prim, sisi yang dimasukkan ke dalam T selain berbobot minimum juga harus bersisian dengan sebuah titik di T. Pada algoritma Prim tidak ada pengecekan apakah sisi yang dipilih membentuk sirkuit apa tidak Sedangkan pada algoritma Kruskal, sisi yang dipilih adalah sisi yang berbobot paling terkecil sampai terbesar dengan catatan sisi tersebut tidak membentuk sirkuit.