View/Open

Author
Hendry , Pratama

Advisor
Prof.Dra.Wamiliana,MA.,Ph.D. ,
Dear Michiko Mutiara Noor,S.Si.,M.Si.,

Koleksi
Matematika

Publisher

Dalam kemajuan zaman, matematika memiliki peran dalam perkembangan ilmu pengetahuan dan teknologi di bidang ilmu murni dan terapan. Di kehidupan nyata salah satu contohnya ialah dalam desain jaringan. Jaringan disini adalah jaringan secara umum seperti jaringan telekomunikasi, jaringan transportasi, jaringan energi atau listrik, jaringan pipa air dan lain-lain. Salah satu backbone yang sering digunakan dalam desain jaringan adalah Minimum Spanning Tree (MST). Pada penelitian ini akan didiskusikan Algoritma modified Prim yang di hybrid dengan faktor peluang untuk menyelesaikan masalah MST dengan batasan lintasan antar pasangan titik yang dikenal dengan Bounded Diameter Minimum Spanning Tree. Algoritma akan diimplementasikan dengan 150 data set yang merupakan graf dengan orde 10, 20, 30, 40, dan 50 dan masing masing orde terdiri dari 30 problem. Besar bounded diameter yang digunakan pada penelitian ini adalah ⌊n/2⌋,⌊n/3⌋,⌊n/4⌋,dan ⌊n/5⌋ dengan n ialah orde (banyaknya titik). Didapat hasil bahwa semakin banyak orde dan semakin besar bounded diameter maka solusi pada masalah BDMST akan mendekati solusi MST, dan faktor peluang tidak merubah pengaruh dari besar bounded diameter ataupun banyaknya orde pada solusi BDMST yang mendekati solusi MST. Selain itu, penelitian titik awal secara random lebih baik dari pada titik awal yang tetap untuk diameter maksimal ⌊n/2⌋ dan ⌊n/4⌋, sedangkan pada diameter ⌊n/3⌋ dan ⌊n/5⌋ pemilihan titik awal tetap lebih baik dari titik awal yang random. Kata kunci : Algoritma Modified Prim, MST, Bounded Diameter, Orde, Faktor Peluang.

URI
https://repo.itera.ac.id/depan/submission/SB2106090004

Keyword