PENGGUNAAN MODIFIED PRIM ALGORITHM UNTUK MENYELESAIKAN MASALAH BOUNDED DIAMETER MINIMUM SPANNING TREE (BDMST)

Michael Salim, 1717031040 (2021) PENGGUNAAN MODIFIED PRIM ALGORITHM UNTUK MENYELESAIKAN MASALAH BOUNDED DIAMETER MINIMUM SPANNING TREE (BDMST). FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM, UNIVERSITAS LAMPUNG.

[img]
Preview
File PDF
1. ABSTRAK MICHAEL.pdf

Download (145Kb) | Preview
[img] File PDF
2. SKRIPSI FULL - MICHAEL.pdf
Restricted to Hanya staf

Download (2089Kb)
[img]
Preview
File PDF
3. SKRIPSI TANPA MICHAEL.pdf

Download (1518Kb) | Preview

Abstrak

ABSTRACT PENGGUNAAN MODIFIED PRIM ALGORITHM UNTUK MENYELESAIKAN MASALAH BOUNDED DIAMETER MINIMUM SPANNING TREE (BDMST) By Michael Salim Prim's algorithm is one method to solve the Minimum Spanning Tree (MST) problem. In this reasearch, a Modified Prim Algorithm will be carried out to solve the Bounded Diameter Minimum Spanning Tree (BDMST) problem. Modified Prim Algorithm is done by adding bounded diameter constraint in Prim Algorithm. In comparison, we are using the python program to facilitate and shorten the time to implement the Modified Prim Algorithm to solve BDMST problems. This research aims to develop and implement BDMST source code with Modified Prim Algorithm on complete graph data. Then, we will show the properties of BDMST where the bounded diameter depends on the order ( ) of the complete graph. Obtaining the MST solution with Prim Algorithm and BDMST with Modified Prim Algorithm, obtained the larger the order of the data to a bounded diameter and the larger the bounded diameter to an order the BDMST value is getting closer to the MST value. The results of implementing the source code in this study show that the BDMST value is greater than or equal to the MST value, where MST is the lower bound of BDMST. Keywords: Prim Algorithm, Minimum Spanning Tree, Modified Prim Algorithm, Bounded Diameter Minimum Spanning Tree. ABSTRAK PENGGUNAAN MODIFIED PRIM ALGORITHM UNTUK MENYELESAIKAN MASALAH BOUNDED DIAMETER MINIMUM SPANNING TREE (BDMST) Oleh Michael Salim Algoritma Prim adalah salah satu metode untuk menyelesaikan masalah Minimum Spanning Tree (MST). Pada penelitian ini, akan dilakukan Modified Prim Algorithm untuk menyelesaikan masalah Bounded Diameter Minimum Spanning Tree (BDMST). Modified Prim Algorithm dilakukan dengan menambah kendala bounded diameter pada Algoritma Prim. Penggunaan program python untuk memudahkan dan mempersingkat waktu dalam implementasi Modified Prim Algorithm untuk menyelesaikan masalah BDMST. Tujuan penelitian ini mengembangkan serta mengimplementasikan source code BDMST dengan Modified Prim Algorithm pada data graf lengkap. Kemudian, akan ditunjukan sifat-sifat BDMST dimana bounded diameter bergantung pada orde ( ) graf lengkap. Mendapatkan solusi MST dengan Algoritma Prim dan BDMST dengan Modified Prim Algorithm, diperoleh semakin besar orde data terhadap suatu bounded diameter dan semakin besar bounded diameter terhadap suatu orde menghasilkan nilai BDMST semakin mendekati nilai MST. Hasil implementasi source code pada penelitian ini diperlihatkan bahwa nilai BDMST lebih besar atau sama dengan nilai MST, MST adalah lower bound dari BDMST. Kata Kunci: Algoritma Prim, Minimum Spanning Tree, Modified Prim Algorithm, Bounded Diameter Minimum Spanning Tree.

Jenis Karya Akhir: Skripsi
Subyek: 500 ilmu pengetahuan alam dan matematika > 510 Matematika
Program Studi: FAKULTAS MIPA > Prodi Matematika
Pengguna Deposit: UPT Anita Ekarini
Date Deposited: 12 May 2022 02:28
Terakhir diubah: 12 May 2022 02:28
URI: http://digilib.unila.ac.id/id/eprint/60892

Actions (login required)

Lihat Karya Akhir Lihat Karya Akhir