PENYELESAIAN MULTI PERIOD DEGREE CONSTRAINED MINIMUM SPANNING TREE MENGGUNAKAN ALGORITMA MODIFIED PRIM DAN PEMOGRAMAN GNU OCTAVE

Mas Dafri Maulana, 1317031051 (2017) PENYELESAIAN MULTI PERIOD DEGREE CONSTRAINED MINIMUM SPANNING TREE MENGGUNAKAN ALGORITMA MODIFIED PRIM DAN PEMOGRAMAN GNU OCTAVE. FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM , UNIVERSITAS LAMPUNG.

Preview	Text ABSTRAK.pdf Download (268Kb) | Preview
	Text SKRIPSI FULL.pdf Restricted to Hanya pengguna terdaftar Download (3861Kb)
Preview	Text SKRIPSI TANPA BAB PEMBAHASAN.pdf Download (3057Kb) | Preview

Abstrak

Dalam teori graf, salah satu masalah optimasi adalah penentuan pohon rentang minimum, atau dikenal dengan istilah Minimum Spanning Tree (MST), yaitu menentukan bobot yang minimum dari suatu graf yang terhubung. Jika pada suatu MST diberikan kendala degree (derajat) pada tiap titiknya maka MST tersebut menjadi masalah DCMST (Degree Constrained Minimum Spanning Tree). Contoh terapan dari DCMST adalah masalah proses instalasi suatu jaringan yang dapat dilakukan dalam satu tahap. Akan tetapi, karena ada kendala (umumnya kendala pendanaan) maka proses instalasi tersebut harus dilakukan dalam beberapa tahap. Masalah inilah yang disebut dengan instalasi jaringan multi tahap atau Multi Period Degree Constrained Minimum Spanning Tree (MPDCMST). Untuk menyelesaikan MPDCMST dapat digunakan Algoritma Prim yang telah dimodifikasi atau disebut dengan Modified Prim. Penelitian ini bertujuan untuk mengimplementasikan Algoritma Prim untuk penentuan MST, DCMST, dan MPDCMST. Program DCMST dan MPDCMST dibuat dengan memberikan kendala batasan degree ≤ 3 dan membagi proses instalasi menjadi 3 tahap. Implementasi MPDCMST menggunakan beberapa algoritma yakni MPDCMST_awal, MPDCMST_akhir, dan MPDCMST_kick. Dilakukan pada 300 data dengan orde graf dari 10 sampai dengan 100. Setiap pengujian dalam satu permasalahan dikenakan 30 kali uji dan dicatat waktu yang diperlukan untuk menyelesaikan suatu permasalah tersebut. Hasil menunjukkan bahwa nilai DCMST merupakan lower bound untuk MDCMST dan berdasarkan solusi optimal MPDCMST_kick merupakan metode terbaik dari ketiga metode ini.

Tipe Karya Ilmiah:	Skripsi
Subyek:	> Q Science (General) > QA Mathematics
Program Studi:	Fakultas MIPA > Prodi Matematika
Depositing User:	18367101 . Digilib
Date Deposited:	11 Jul 2017 08:07
Last Modified:	11 Jul 2017 08:07
URI:	http://digilib.unila.ac.id/id/eprint/27203

Actions (login required)

View Item