PENGEMBANGAN ALGORITMA MODIFIED PRIM UNTUK MENYELESAIKAN MASALAH INSTALASI JARINGAN MULTI TAHAP

PENGEMBANGAN ALGORITMA MODIFIED PRIM UNTUK MENYELESAIKAN MASALAH INSTALASI JARINGAN MULTI TAHAP

(Skripsi)

Oleh WIBI CAHYO HASTONO

JURUSAN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS LAMPUNG 2017

ABSTRACT THE MODIFIED PRIM'S ALGORITHM TO SOLVE THE MULTI PERIODS INSTALLATION PROBLEM

By WIBI CAHYO HASTONO

Given a graph G(V,E), and cij ≥ 0, where V is a set of vertices, and E is the set of edges that connects vertices in V, and cij is the weight of the edge eij, The Minimum Spanning Tree (MST) Problem is a problem of finding the minimum weight spanning tree of G. If we add degree restriction on every vertex of G, the problem becomes a Degree Constrained Minimum Spanning Tree Problem (DCMST). Moreover, if we add another constraint which is period, then the problem arises as The Multi Period Degree Constrained Minimum Spanning Tree (MPDCMST) Problem. In reality, this problem usually arises on network installation. Prim’s Algorithm is one of famous algorithms that frequently used to solve MST. To use Prim’s algorithm for MPDCMST, we need to do some modifications. In this research we developed six algorithms based on Modified Prim’s algorithm, named as :WAC1, WAC2, WAC3, WAC4, WAC5 and WAC6. From the results we found that the best solution is Algorithm WAC6. Keywords : multi periods, degree constrained, network installation, modified Prim.

ABSTRAK PENGEMBANGAN ALGORITMA MODIFIED PRIM UNTUK MENYELESAIKAN MASALAH INSTALASI MULTI TAHAP

Oleh WIBI CAHYO HASTONO

Algoritma Prim merupakan salah satu algoritma yang sering digunakan untuk menyelesaikan masalah Minimum Spanning Tree (MST) atau pencarian jalur terpendek dalam sebuah graf. Pada implementasi dunia nyata masalah instalasi jaringan tidak sesederhana masalah MST, terdapat beberapa kendala tambahan dalam masalah instalasi jaringan. Kendala tambahan tersebut adalah kendala degree yang membatasi jumlah maksimal edge yang boleh terhubung dalam suatu vertex. Selanjutnya adalah kendala periode, yang membagi proses instalasi pada beberapa tahap, dengan vertex prioritas pada masing-masing tahapan. MST dengan dua tambahan kendala ini disebut dengan Multi Period Degree Constrained Minimum Spanning Tree (MPDCMST). Pada penelitian ini dikembangkan Algoritma Modified Prim untuk menyelesaikan masalah MPDCMST. Penelitian ini mengembangkan 6 Algoritma Modified Prim yang diberi nama WAC1, WAC2, WAC3, WAC4, WAC5 dan WAC6. Dari hasil pengujian yang dilakukan menggunakan kasus uji seperti pada penelitian sebelumnya, hasil solusi terbaik dihasilkan oleh Algoritma WAC6.

Kata Kunci : multi periods, degree constrained, instalasi jaringan, modified Prim.

PENGEMBANGAN ALGORITMA MODIFIED PRIM UNTUK MENYELESAIKAN MASALAH INSTALASI JARINGAN MULTI TAHAP Oleh

WIBI CAHYO HASTONO

Skripsi Sebagai Salah Satu Syarat Untuk Memperoleh Gelar SARJANA KOMPUTER pada Jurusan Ilmu Komputer Fakultas Matematika dan Ilmu Pengetahuan Alam

JURUSAN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS LAMPUNG 2017

RIWAYAT HIDUP

Penulis dilahirkan pada tanggal 6 Juli 1995 di Tanjung Waras, Natar. Penulis merupakan anak pertama dari tiga bersaudara dengan ayah bernama Yustam Prihastono dan ibu bernama Tusimah. Penulis menyelesaikan pendidikan formal pertama kali di SD Negeri 5 Merak Batin tahun 2007, kemudian melanjutkan pendidikan menengah pertama di SMP Negeri 5 Natar dan selesai pada tahun 2010. Pendidikan menengah atas di SMA Muhammadiyah 2 Bandar Lampung diselesaikan penulis pada tahun 2013.

Pada tahun 2013, penulis terdaftar sebagai mahasiswa Jurusan Ilmu Komputer Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Lampung melalui jalur SNMPTN. Pada bulan Februari tahun 2016, penulis melakukan Kerja Praktik di Grapari Telkomsel Lampung. Pada bulan Juli tahun 2016 penulis melaksanakan Kuliah Kerja Nyata di Desa Gaya Baru VI Kecamatan Seputih Surabaya Kabupaten Lampung Tengah. Selama menjadi mahasiswa, penulis cukup aktif berorganisasi, diantaranya adalah: 1. Kepala Biro Sirkulasi dan Periklanan Lembaga Pers Mahasiswaan Natural FMIPA Unila pada tahun periode 2014-2015.

2. Layouter Lembaga Pers Mahasiswaan Natural FMIPA Unila pada tahun periode 2015-2016. 3. Anggota Bidang Kaderisasi Himpunan Mahasiswa Jurusan Ilmu Komputer pada tahun periode 2014-2015. 4. Bendahara Biro Khusus Himpunan Mahasiswa Jurusan Ilmu Komputer pada tahun periode 2015-2016. 5. Asisten Laboratorium dan Asisten Dosen Jurusan Ilmu Komputer pada tahun periode 2014-2017. 6. Web Master FMIPA Unila pada tahun 2015. 7. Web and Android Programmer pada CV. Moonray Artha Gemilang pada tahun 2016.

ix

PERSEMBAHAN

Puji dan syukur saya ucapkan kepada Allah SWT atas segala nikmat dan karunia-Nya sehingga skripsi ini dapat diselesaikan.

Kupersembahkan karya kecilku ini untuk:

Ibuku, yang telah melahirkanku Ibuku, yang telah merawat dan membesarkanku Ibuku, yang telah mendidikku

Ayahku tercinta, yang telah membesarkanku dengan seluruh kasih dan sayangnya, memberikan pengetahuannya, dan selalu mendukung serta mendoakan untuk keberhasilanku.

Adik serta keluarga besarku yang selalu kusayangi

dan, Almamater yang kubanggakan UNIVERSITAS LAMPUNG

MOTTO

“Indeed, Allah will not change the condition of a people until they change what is in themselves.” (Qur’an Surah 13:11)

“The longer I live, the more I realize the impact of attitude on life. Attitude, to me, is more important than facts. It is more important than the past, the education, the money, than circumstances, than failure, than successes, than what other people think or say or do. It is more important than appearance, giftedness or skill. It will make or break a company... a church... a home. The remarkable thing is we have a choice everyday regarding the attitude we will embrace for that day. We cannot change our past... we cannot change the fact that people will act in a certain way. We cannot change the inevitable. The only thing we can do is play on the one string we have, and that is our attitude. I am convinced that life is 10% what happens to me and 90% of how I react to it. And so it is with you... we are in charge of our Attitudes.” (Charles R. Swindoll)

SANWACANA

Puji dan syukur penulis ucapkan kehadirat Allah SWT atas segala rahmat, hidayah dan kesehatan yang diberikan kepada penulis sehingga dapat menyelesaikan penulisan skripsi ini.

Skripsi ini disusun sebagai syarat untuk memperoleh gelar Sarjana Komputer di Jurusan Ilmu Komputer Fakultas Matematika dan Ilmu Pengetahuan Universitas Lampung. Judul dari skripsi ini adalah “Pengembangan Algoritma Modified Prim untuk Menyelesaikan Masalah Instalasi Jaringan Multi Tahap”.

Dalam penyusunan skripsi ini, penulis banyak menghadapi kesulitan. Namun, berkat bantuan dan dorongan dari berbagai pihak, akhirnya penulis dapat menyelesaikan skripsi ini. Untuk itu pada kesempatan ini, penulis mengucapkan terimakasih kepada: 1. Kedua orang tua, Bapak Yustam Prihastono dan Ibu Tusimah, Adik-adikku tercinta Riski Saifullah dan Zaskia Lutfi Zahratu Sita, serta keluarga besar yang selalu memberikan doa, motivasi dan kasih sayang yang tak terhingga. 2. Ibu Dra. Wamiliana, Ph.D. sebagai pembimbing I, yang telah membimbing penulis dan memberikan ide, kritik serta saran sehingga penulisan skripsi ini dapat diselesaikan. 3. Ibu Astria Hijriani, S.Kom., M.Kom. sebagai pembimbing II, yang telah memberikan saran, bantuan dan membimbing penulis dalam pembuatan skripsi ini.

4. Bapak Ir. Machudor Yusman, M.Kom. sebagai pembahas, yang telah memberikan masukan-masukan yang bermanfaat dalam perbaikan skripsi ini. 5. Bapak dan Ibu Dosen serta seluruh staf Jurusan Ilmu Komputer Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Lampung yang telah memberikan ilmu dan pengalaman dalam hidup untuk menjadi lebih baik. 6. Seluruh mahasiswa angkatan 2013 yang berjuang bersama dalam suka maupun duka, saling membantu, saling bertanya dalam menyelesaikan karya-karyanya selama di Universitas Lampung. Kebersamaan yang telah dilalui menjadi pengalaman berharga bagi penulis.

Penulis menyadari bahwa skripsi ini masih jauh dari kesempurnaan, akan tetapi sedikit harapan semoga skripsi ini bermanfaat bagi perkembangan ilmu pengetahuan terutama bagi teman-teman Ilmu Komputer.

Bandar Lampung, 25 Januari 2017

Wibi Cahyo Hastono

xiii

DAFTAR ISI

Halaman DAFTAR ISI ...............................................................................

xiv

DAFTAR GAMBAR ..................................................................

xvi

DAFTAR TABEL ......................................................................

xix

BAB I PENDAHULUAN 1.1 Latar Belakang .............................................................. 1.2 Rumusan Masalah ......................................................... 1.3 Batasan Masalah ........................................................... 1.4 Tujuan ........................................................................... 1.5 Manfaat .........................................................................

1 3 3 4 4

BAB II TINJAUAN PUSTAKA 2.1 Konsep Dasar Graf ....................................................... 2.2 Minimum Spanning Tree dan Turunannya .................... 2.3 Algoritma Prim dan Extreme Programming .................

5 9 11

BAB III METODE PENELITIAN 3.1 Tempat dan Waktu Penelitian ....................................... 3.2 Bahan dan Alat ............................................................. 3.3 Tahapan Penelitian ........................................................

14 14 15

BAB IV HASIL DAN PEMBAHASAN 4.1 Data yang Digunakan .................................................... 4.2 Penentuan HVTk dan MaxVTk .................................... 4.3 Implementasi ................................................................. 4.3.1 WAC1 .................................................................... 4.3.2 WAC2 .................................................................... 4.3.3 WAC3 .................................................................... 4.3.4 WAC4 .................................................................... 4.3.5 WAC5 .................................................................... 4.3.6 WAC6 .................................................................... 4.4 Pengujian dan Hasil ......................................................

32 32 33 33 39 44 49 54 60 61

BAB V KESIMPULAN DAN SARAN 5.1 Kesimpulan ................................................................... 5.2 Saran .............................................................................

65 66

DAFTAR PUSTAKA

DAFTAR GAMBAR

Halaman Gambar 2.1 Contoh Tree ...................................................................

8

Gambar 2.2 Graf G .............................................................................

8

Gambar 2.3 Semua spanning tree dari graf G....................................

9

Gambar 2.4 Contoh pohon .................................................................

9

Gambar 2.5 Alur Metode Extreme Programming (Pressman, 2009)

13

Gambar 3.1 Flowchart Penelitian ......................................................

15

Gambar 3.2 Flowchart tahapan coding .............................................

21

Gambar 3.3 Isi file 5 vertex ................................................................

22

Gambar 3.4 Visualisasi Tabel 3.1 ......................................................

23

Gambar 3.5 Visualisasi MST .............................................................

25

Gambar 3.6 Visualisasi DCMST .......................................................

27

Gambar 3.7 Visualisasi` MPDCMST ................................................

30

Gambar 4.1 Visualisasi jaringan periode-1 pada WAC1 ..................

36

Gambar 4.2 Visualisasi jaringan periode-2 pada WAC1 ...................

37

Gambar 4.3 Visualisasi jaringan pada WAC1 ...................................

39


41


42

Gambar 4.6 Visualisasi jaringan WAC2 ...........................................

43

Gambar 4.7 Visualisasi bobot k-path .................................................

44


46


47

Gambar 4.10 Visualisasi jaringan pada WAC3 ................................

49

Gambar 4.11 Visualisasi jaringan periode-1 pada WAC4 ................

51


52

Gambar 4.13 Visualisasi jaringan pada WAC4 ................................

53


56

Gambar 4.15 Visualisasi jaringan periode-2 pada WAC5 ..............

58

Gambar 4.16 Visualisasi jaringan pada WAC5 ..............................

59

Gambar 4.17 Visualisasi Grafik Tabel 4.8 ......................................

62

Gambar 4.18 Visualisasi Grafik Tabel 4.9 .......................................

64

xviii

DAFTAR TABEL

Halaman Tabel 3.1 Edge / sisi pembentuk graf ............................................

22

Tabel 4.1 Elemen HVTk untuk setiap periode (Wamiliana, 2015 b) 32 Tabel 4.2 Objek edge file 22.dat 10 vertex ..................................

34

Tabel 4.3 Edge yang terhubung pada proses instalasi WAC1 .....

38


43

Tabel 4.5 Edge yang terhubung pada proses instalasi WAC3 ......

48


53


59

Tabel 4.8 Perbandingan rata-rata bobot antara MST, DCMST, WAC1, WAC2, WAC3, WAC4,WAC5 dan WAC6 ...

61

Tabel 4.9 Perbandingan bobot rata-rata antara WAC6, WAC2, WADR1 dan WADR2 ..................................................

63

BAB I PENDAHULUAN

1.1 LATAR BELAKANG Penerapan ilmu matematika dalam kehidupan sehari-hari memang tidak pernah ada habisnya. Ilmu matematika dapat menjadi solusi konseptual dalam penyelesaian berbagai masalah yang dihadapi oleh manusia. Seiring dengan semakin majunya teknologi komputer, penggunaan komputer dan model matematika semakin banyak digunakan sebagai alat bantu dalam menyelesaikan masalah dalam kehidupan sehari-hari. Dalam matematika dan ilmu komputer, suatu graf adalah objek dasar pelajaran dalam teori graf. Dalam bahasa sehari-hari, suatu graf dapat didefinisikan sebagai himpunan dari objek-objek yang dinamakan vertex atau titik dan dihubungkan oleh edge atau garis. Munir (2009) mendefinisikan bahwa graf adalah himpunan (V, E) dan dapat ditulis dengan notasi G = (V, E), V adalah himpunan tidak kosong dari vertex-vertex {v1,v2,...,vn} dan E adalah himpunan edge {e1,e2,...,en} yang menghubungkan sepasang vertex. Salah satu permasalahan yang dapat diselesaikan menggunakan teori graf yaitu Minimum Spanning Tree Problem. Dari studi literatur didapat bahwa penelitian tentang penggunaan suatu algoritma untuk 1

menentukan Minimum Spanning Tree (MST) atau Pohon Rentang Minimum dan implementasinya pada suatu graf berbobot telah dilakukan dan didapat dua algoritma terkenal untuk mencari MST, yaitu Algoritma Prim dan Algoritma Kruskal. Jika MST tersebut diberi tambahan kendala degree (derajat) maka masalah tersebut adalah masalah Degree Contrained Minimum Spanning Tree (DCMST) dan jika DCMST diberi kendala tahap, maka masalah tersebut menjadi masalah MPDCMST atau Multi Period Degree Constrained Minimum Spanning Tree. Untuk masalah MPDCMST, Kawatra (2002) pertama kali mengidentifikasi masalah ini dan menyelesaikannya menggunakan metode hybrid relaksi Lengrange dan branch exchange yang diimplementasikan metode tersebut sampai 100 vertex. Selanjutnya Wamiliana dkk. (2005) mengimplementasi metode greedy MPDCMST dengan menggunakan modifikasi Algoritma Kruskal. Nugraha (2011) mengimplementasikan Algoritma Prim untuk menentukan MST (Minimum Spanning Tree) pada sebuah jaringan berbobot dan mendapati bahwa algoritma ini memiliki efisiensi yang cukup tinggi, yaitu dengan waktu sekitar 2 detik per 80 titik yang dihubungkan. Namun, pada penelitian Nugraha (2011) ini hanya mengimplementasikan Algoritma Prim untuk menyelesaikan masalah MST dan bukan MPDCMST. Pada permasalahan MPDCMST pencarian jalur terpendek antara vertex, dibatasi oleh beberapa kondisi tertentu, misalnya jumlah edge maksimal yang terhubung pada suatu vertex. Kendala ini disebut dengan kendala degree (derajat) titik, yang membatasi inter-koneksi pada vertex tersebut. Selain itu, karena instalasi jaringan dilakukan secara bertahap, maka tiap tahap dibatasi banyaknya titik yang di-install.

2

Pada penelitian ini difokuskan pada masalah MPDCMST yang diselesaikan menggunakan Algoritma Modified Prim. Pada MPDCMST, jika diberikan sebagian yang telah terhubung (misalnya jaringan pipa PDAM), maka dengan dana yang telah dialokasikan untuk pengembangan jaringan tersebut, pemerintah harus menentukan titik atau fasilitas publik mana sajakah yang dihubungkan pada tahap selanjutnya, dan mana yang dapat ditunda sampai akhirnya semua perumahan atau fasilitas publik yang ada terhubung dengan jaringan.

1.2 Rumusan Masalah

Fokus masalah yang diselesaikan pada penelitian ini adalah bagaimana menyelesaikan masalah MPDCMST (Multi Period Degree Constraint Minimum Spanning Tree) yang memiliki sejumlah vertex dan setiap vertex hanya memiliki degree maksimal 3 menggunakan Algoritma Modified Prim.

1.3 Batasan Masalah Beberapa batasan masalah pada penelitian ini yaitu: 1. Penelitian ini hanya dilakukan pengembangan dan penerapan Algoritma Modified Prim untuk menyelesaikan masalah instalasi jaringan multi tahap. 2. Derajat tiap titik (vertex) maksimal 3. 3. Data yang digunakan pada penelitian ini adalah data yang diambil dari penelitian sebelumnya, oleh Wamiliana dkk (2015 a).

3

1.4 Tujuan

Tujuan dari penelitian ini adalah sebagai berikut : 1. Mengembangkan Algoritma Modified Prim untuk menyelesaikan masalah MPDCMST. 2. Mengembangkan source code untuk poin 1. 3. Mengimplementasikan source code pada poin 2 dengan data yang digunakan oleh Wamiliana dkk (2015 a).

1.5 Manfaat

Penelitian ini diharapkan mampu memberikan kontribusi nyata dalam beberapa hal berikut: 1. Turut membantu mengembangkan Algoritma Prim untuk mencari solusi dalam masalah Multi Period Degree Constrain Minimum Spanning Tree 2. Hasil penelitian ini diharapkan bermanfaat untuk menyelesaikan masalah dalam instalasi jaringan multi tahap.

4

BAB II TINJAUAN PUSTAKA

Pada bab dijelaskan istilah-istilah yang digunakan pada penelitian ini.

2.1 Konsep Dasar Graf Graf Graf G didefinisikan sebagai pasangan himpunan (V, E), ditulis dengan notasi G = (V, E). Dalam hal ini, V merupakan himpunan tidak kosong dari titik-titik (vertex), dan E adalah himpunan sisi-sisi (edge) digambarkan dalam garis-garis yang menghubungkan sepasang titik (Munir, 2009). Degree (Derajat) Misalkan v adalah titik suatu graf G, derajat titik v (simbol d(v)) adalah jumlah garis yang berhubungan dengan titik v dan garis suatu loop dihitung dua kali (Wibisono, 2004). Walk Suatu walk dari v ke w adalah barisan titik-titik berhubungan dan garis berselang-seling, diawali dari titik v dan diakhiri pada w. Walk dengan panjang

5

n dari v ke w dituliskan sebagai berikut : v0 e1 v1 e2 v2 . . . vn-1 en vn dengan v0 = v; vn = w; vi-1 dan vi adalah titik-titik diujung garis ei (Wibisono, 2004). Path Path dengan panjang n dari v ke w adalah walk dari v ke w yang semua garisnya berbeda. Path dari v ke w dituliskan sebagai v = v0 e1 v1 e2 v2 . . . vn-1 en vn = w dengan ei ≠ ej untuk i ≠ j (Wibisono, 2004). Sirkuit Sirkuit dengan panjang n adalah path yang dimulai dan diakhiri pada titik yang sama. Sirkuit adalah path yang berbentuk v0 e1 v1 e2 v2 .... vn-1 en vn dengan v0 = vn (Wibosono, 2004). Graf Terhubung Graf G disebut graf terhubung jika untuk setiap pasang titik u dan v di dalam himpunan V terdapat garis dari u ke v. Jika tidak, maka graf G disebut graf tak terhubung (Munir, 2009). Keterhubungan dua titik adalah penting di dalam graf. Jika dua titik terhubung maka pasti titik yang pertama dapat dicapai dari titik yang kedua. Pada graf berarah, graf G dikatakan terhubung jika graf takberarahnya

terhubung

(graf

tak-berarah

dari

G

diperoleh

dengan

menghilangkan arahnya). Keterhubungan dua titik pada graf berarah dibedakan menjadi terhubung kuat dan terhubung lemah. Dua titik, u dan v pada graf berarah G disebut terhubung kuat jika terdapat lintasan garis dari u ke v dan juga sebaliknya garis berarah dari v ke u. Jika u dan v tidak terhubung kuat tetapi tetap terhubung pada graf tak-berarahnya, maka u dan v dikatakan terhubung lemah (Nugraha, 2011).

6

Graf Berbobot Graf berbobot adalah graf yang setiap garisnya diberi suatu nilai. Bobot pada tiap garis dapat berbeda-beda bergantung pada masalah yang dimodelkan dengan graf. Bobot dapat menyatakan jarak antara dua tiang listrik, kapasitas, biaya perjalanan antara dua kota, waktu tempuh pesan (message) dari sebuah titik komunikasi ke titik komunikasi lain, ongkos dan produksi (Nugraha, 2011). Pohon (Tree) Pohon (Tree) didefinisikan sebagai graph terhubung yang tidak mengandung sirkuit, sedangkan hutan (forest) adalah kumpulan dari pohon (tree) dan forest merupakan graf tidak terhubung. Jadi pohon adalah hutan yang terhubung. Terdapat 2 syarat dalam suatu tree : 1) Suatu graf G disebut terhubung apabila untuk setiap dua titik dari graf G selalu terdapat jalur yang menghubungkan kedua titik tersebut. 2) Sirkuit atau cycle adalah suatu lintasan tertutup dengan derajat setiap titik dua. (Astuti, 2006). Gambar 2.1 adalah contoh dari Tree.

7

Gambar 2.1 Contoh Tree Suatu Graf G dengan n buah titik adalah pohon jika : 1) G terhubung dan tak mengandung sirkuit, atau 2) G tidak mengandung sirkuit dan mempunyai n - 1 buah garis, atau 3) G mempunyai n - 1 buah garis dan terhubung Pohon Rentangan (Spanning Tree) Suatu pohon rentangan atau spanning tree adalah suatu subgraf dari graf G yang mengandung semua simpul dari G dan merupakan suatu pohon (Astuti, 2006). Diberi graf G sebagai berikut :

Gambar 2.2 Graf G Semua spanning tree dari G digambarkan pada Gambar 2.3 berikut :

8

Gambar 2.3 Semua spanning tree dari graf G

2.2 Minimum Spanning Tree dan Turunannya Tree dan Forest Pohon (tree) didefinisikan sebagai suatu graf terhubung (connected graph) yang tidak mengandung rangkaian sederhana (simple circuit). Sebagai misal, graf dalam Gambar 2.4 adalah pohon.

Gambar 2.4 Contoh pohon Himpunan pohon-pohon yang terpisah satu sama lain dinamakan hutan (forest). Di dalam suatu pohon, titik (vertex) berderajat 1 dinamakan daun (leaf) atau titik terminal (terminal node), sedangkan vertex yang berderajat lebih besar dari 1 dinamakan titik cabang (branch node) atau titik internal

9

(internal node). Sebagai misal, vertex-vertex b, c, d, e, f, g, dan i di dalam Gambar 2.4 adalah daun, sedangkan vertex a, e, dan h adalah titik cabang. Sifat-sifat yang dimiliki oleh tree ( Liu, 1995): 1. Di dalam suatu pohon, garis antara dua vertex bersifat tunggal (unik, khas). 2. Di dalam suatu pohon, jumlah vertex satu lebih banyak dari pada jumlah garis. 3. Pohon dengan dua atau lebih vertex memiliki sedikitnya dua daun. Pohon Merentang Minimun/Minimun Spaning Tree (MST) Apabila G adalah graf berbobot, maka bobot Spanning Tree atau Pohon Merentang T dari G didefinisikan sebagai jumlah bobot semua sisi di T. Pohon merentang yang berbeda mempunyai bobot yang berbeda pula. Diantara semua pohon merentang dalam graf G, pohon merentang yang berbobot minimum dinamakan Pohon Merentang Minimum atau Minimum Spanning Tree. Pohon Merentang Minimum ini mempunyai terapan yang luas dalam masalah riil (Munir, 2009). DCMST (Degree Constrained Minimum Spanning Tree) DCMST Degree Constrained Minimum Spanning Tree. DCMST adalah suatu permasalahan yang sama halnya dengan MST hanya saja dalam kondisinya terdapat kendala degree (derajat). Degree Constrained adalah kondisi pembatasan jumlah degree yang dimiliki oleh suatu titik. DCMST adalah permasalahan untuk menemukan minimum spanning tree T dari G dimana

10

degree dari tiap titik dibatasi dengan persamaan, di ≤ bi ; (Caccetta dan Hill, 2001). MPDCMST (Multi Period Degree Constrained Minimum Spanning Tree) Multi Period Degree Constrained Minimum Spanning Tree (MPDCMST) adalah masalah lanjutan dari Degree Constrained Minimum Spanning Tree (DCMST). Perbedaaan diantara kedua masalah ini adalah periode saat dilakukanya instalasi jaringan. Biasanya dalam implementasi dikehidupan sehari-hari, instalasi jaringan harus dilakukan dalam beberapa periode karena mengalami kendala kekurangan dana saat instalasi. Pada DCMST, semua vertex (dapat dipresentasikan sebagai komputer, kota, dan lainnya) dapat diinstal dalam satu periode dan tanpa ada titik vertex secara spesifik. Masalah ini diaplikasikan dalam permasalahan kehidupan sehari-hari seperti instalasi, suplay air, suplay gas, listrik, kabel telepon, dan lain-lainnya (Junaidi, 2008). 2.3 Algoritma Prim dan Extreme Programming Algoritma Prim Inisiasi : 𝑇 = ∅ , 𝑉 = ∅. Langkah – langkah 1. Tentukan salah satu titik sebagai ”root” 2. Masukkan root ke V. 3. Tentukan garis minimum yang terhubung dengan root, pilih dan masukkan ke T. Titik ujung garis tersebut masukkan ke V. 4. Pilih garis minimum yang terhubung dengan titik – titik di V dan cek apakah membentuk sirkuit jika ditambahkan ke T. 11

Jika ya , maka buang garis tersebut dan pilih lagi garis minimum berikutnya. Jika tidak, masukkan garis nya di T dan titik nya di V. 5. Cek 𝑇 = 𝑛 − 1? Jika ya STOP. Jika tidak, ulangi langkah 4 (Wamiliana, 2015). Extreme Programming Extreme Programming, atau XP, adalah metode pengembangan perangkat lunak yang berdasarkan nilai-nilai kesederhanaan, komunikasi, umpan balik, dan keberanian. XP dikembangkan oleh Kent Beck pada tahun 1996 yang menulis buku, Extreme Programming Explained. XP dirancang untuk digunakan dengan tim kecil yang melakukan pengembangan perangkat lunak dengan cepat dengan lingkungan yang mudah cepat berubah. XP bekerja dengan membawa keseluruhan tim bersama-sama di hadapan praktek sederhana, dengan umpan balik yang cukup untuk memungkinkan tim dapat melihat kedudukan tim berada dan untuk menyesuaikan praktek sesuai dengan situasi unik mereka (Lamia, 2002).

12

simple design CRC cards

spike solut ions prot ot ypes

user st ories values accept ance t est crit eria it erat ion plan

refact oring pair programming

Release sof t ware increment project velocit y comput ed

unit t est cont inuous int egrat ion accept ance t est ing

Gambar 2.5 Alur Metode Extreme Programming (Pressman, 2009) Java Java diciptakan oleh James Gosling, Patrick Naughton, Chris Warth, Ed Frank, dan Mike Sheridan di Sun Microsystem pada tahun 1991. Bahasa ini awalnya disebut Oak namun kemudian diganti java pada tahun 1995. Dorongan asli dibentuknya java tidak berasal internet, sebaliknya, motivasi utama diciptakannya bahasa ini adalah kebutuhan untuk bahasa platform-independen yang dapat digunakan untuk membuat perangkat lunak untuk dimasukkan dalam berbagai perangkat elektronik konsumen (Oracle, 2016).

13

BAB III METODE PENELITIAN

3.1 Tempat dan Waktu Penelitian

Penelitian ini dilakukan di Jurusan Ilmu Komputer Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Lampung. Waktu penelitian dilakukan pada semester ganjil tahun ajaran 2016-2017.

3.2 Bahan dan Alat

Bahan penelitian yang dibutuhkan untuk mendukung pelaksanaan penelitian ini adalah sebagai berikut : 1. Data masalah graf yang diselesaikan. 2. Berbagai literatur mengenai Algoritma Prim dan implementasinya dalam pemecahan masalah MST. Sedangkan alat yang digunakan pada penelitian ini adalah sebagai berikut : 1. Perangkat keras (Hardware), dengan spesifikasi berikut : a. Processor intel core i5 b. RAM 4 GB c. Hardisk 500 GB 2. Perangkat lunak (Software), diantaranya : 14

a. Sistem Operasi

: Windows 8

b. Bahasa pemrograman

: Java

c. IDE

: Netbeans 8.0

3.3 Tahapan Penelitian

Pada penelitian yang dilakukan menggunakan metode pengembangan perangkat lunak Extreme Programming. Sedangkan tahapan-tahapan yang dilakukan pada penelitian ini digambarkan pada Gambar 3.1:

simple design CRC cards

spike solut ions prot ot ypes

user st ories values accept ance t est crit eria it erat ion plan

refact oring pair programming

Release sof t ware increment project velocit y comput ed

unit t est cont inuous int egrat ion accept ance t est ing

Gambar 3.1 Flowchart Penelitian

15

Berikut ini adalah penjelasan tiap tahapan yang dilakukan pada penelitian ini : 1. Planning Tahapan pertama, yaitu planning atau perencanaan. Tahapan ini terdiri dari tiga sub-tahap. Tahapan pertama yaitu melakukan identifikasi masalah MPDCMST dalam kehidupan sehari-hari. Identifikasi masalah pada penelitian ini bertujuan untuk mencari faktor-faktor yang harus diperhatikan dalam menyelesaikan masalah MPDCMST.

Subtahap selanjutnya adalah studi literatur, yakni dengan mengumpulkan dan

mempelajari

informasi

seputar

masalah

MPDCMST,

serta

implementasi Algoritma Prim dalam menyelesaikan masalah serupa. Informasi yang dikumpulkan berasal dari beberapa sumber seperti buku, jurnal penelitian maupun forum-forum yang terdapat di internet. Sub tahap ketiga adalah melakukan perencanaan kegiatan yang dilakukan selama penelitian.

2. Design Tahapan kedua adalah proses pembuatan algoritma program untuk penyelesaian masalah yang telah dirumuskan. Algoritma yang akan dibuat adalah hasil pengembangan dari Algoritma Prim. Pada tahapan ini juga dilakukan perancangan input, output dan flowchart dari program yang dibuat. Berikut ini adalah pseudo code Algoritma Modified Prim untuk menyelesaikan masalah MPDCMST.

16

inisialisasi V={1}, T=0, n=jumlah_vertex, k=1, kMax=3 begin while k < kMax do if |HVTk| > MaxVTk stop else Tk = 0 while Tk < (|HVTk|-1) do cari edge terpendek dari vertex dalam V simpan edge terpilih kedalam e if vertex yang akan dihubungkan tidak termasuk dalam HVTk lanjutkan ke edge berikutnya else if penambahan e menyebabkan sirkuit lanjutkan ke edge berikutnya else if penambahan e melanggar degree restriction lanjutkan ke edge berikutnya else simpan vertex sumber dari e kedalam V simpan e kedalam T Tk++ endif endif endif end

17

while Tk < (MaxVTk-1) do cari edge terpendek dari vertex dalam V simpan edge terpilih kedalam e if penambahan e menyebabkan sirkuit lanjutkan ke edge berikutnya else if penambahan e melanggar degree restriction lanjutkan ke edge berikutnya else simpan vertex sumber dari e kedalam V simpan e kedalam T Tk++ endif endif end k++; endif endwhile end

Catatan : 

HVTk

= Himpunan vertex-vertex yang harus di-install pada tahap ke-k atau

sebelumnya. 

maxVTk = Maksimal vertex yang dapat di-install pada tahap ke-k.



kMax

= Jumlah maksimal periode instalasi.



V

= Himpunan vertex yang telah terhubung.



T

= Himpunan edge dalam graf.

18



Tk

= Jumlah edge yang telah di-install pada tahapan ke-k.



k

= Periode instalasi sekarang. Pseudo code Algoritma Modified Prim dijelaskan sebagai berikut: 1. Inisialisasi variable V sebagai himpunan vertex dengan nilai awal berisi vertex 1. Inisialisasi variable T sebagai himpunan kosong yang digunakan untuk menyimpan edge. Inisialisasi variable n sebagai jumlah vertex yang di-install. Inisialisasi variable k dengan 1 dan kMax dengan 3. 2. Jika jumlah vertex yang harus di-install pada tahap sekarang (|HVTk|) lebih besar dari jumlah vertex yang dapat di-install pada tahap sekarang, munculkan pesan error dan hentikan program. 3. Cari dan simpan edge terpendek dari vertex dalam V ke variabel e. 4. Jika vertex yang dihubungkan tidak termasuk dalam vertex prioritas maka lanjutkan ke edge berikutnya. 5. Jika penambahan e menyebabkan sirkuit, maka lanjutkan ke edge berikutnya. 6. Jika penambahan e melanggar degree restriction (kendala degree), maka melanjutkan ke edge berikutnya. 7. Simpan vertex sumber dari e kedalam V. 8. Simpan e kedalam T 9. Ubah nilai Tk menjadi nilai k sekarang ditambah 1. 10. Jika edge yang telah di-install pada periode sekarang (Tk) kurang dari jumlah vertex prioritas pada periode ini (|HVTk|) dikurangi satu, maka kembali ke tahap 3.

19

11. Cari dan simpan edge terpendek dari vertex dalam V ke variabel e 12. Jika penambahan e menyebabkan sirkuit, maka lanjutkan ke edge berikutnya. 13. Jika penambahan e melanggar degree restriction, maka lanjutkan ke edge berikutnya. 14. Simpan vertex sumber dari e kedalam V. 15. Simpan e kedalam T 16. Ubah nilai Tk menjadi nilai k sekarang ditambah 1. 17. Jika jumlah edge yang telah di-install pada periode sekarang (Tk) kurang dari jumlah vertex maksimal yang dapat di-install pada periode ini (|MaxVTk|) dikurang satu, maka kembali ke tahap 10. 18. Ubah nilai k menjadi nilai k sekarang ditambah 1. 19. Jika jumlah periode sekarang (k) kurang dari jumlah periode maksimal (kMax), maka kembali ke tahap 2. 3. Coding Pada tahapan ini terdapat flowchart yang menunjukkan beberapa tahapan tertentu selama fase coding. Flowchart pada tahapan coding dijelaskan pada Gambar 3.2.

20

Gambar 3.2 Flowchart tahapan coding Pada tahap coding dibagi menjadi empat fase utama, dimana tiap-tiap fase merupakan pengembangan fase sebelumnya. Sehingga, pada fase ini tidak dapat dilakukan secara paralel. Tiap-tiap fase pada tahapan coding dijelaskan sebagai berikut : a. Pembuatan Modul Pembaca Data Modul Pembaca Data ini dirancang untuk dapat melakukan proses pembacaan data dari file sumber. Pada proses ini juga dilakukan proses ekstraksi data kedalam bentuk objek yang sesuai dengan aturan pemrograman berorientasi objek. Data sumber yang digunakan adalah data penelitian Wamiliana dkk. (2015), pada data ini terdapat 10 folder, yaitu folder 10,20,30,50,60,70,80,90 dan 100 vertex. Pada masingmasing folder terdapat 30 file yang berisi data uji. Contoh isi file data dengan 5 vertex dijelaskan pada Gambar 3.3:

21

Gambar 3.3 Isi file 5 vertex Jika file 1.dat diubah menjadi sebuah objek edge maka hasilnya dijelaskan pada Tabel 3.1 berikut. Tabel 3.1 Edge / sisi pembentuk graf Vertex Sumber

Vertex Tujuan

Bobot

1

2

2

1

3

1

1

4

1

1

5

3

2

3

4

2

4

6

2

5

5

3

4

7

3

5

8

4

5

9

22

Dimana kolom mewakili atribut objek dan baris mewakili objek itu sendiri. Agar lebih mudah dipahami, dari Tabel 3.1 divisualisasikan dalam bentuk graf pada Gambar 3.4.

Gambar 3.4 Visualisasi Tabel 3.1 V adalah simbol vertex atau titik-titik yang ada. Pada gambar 3.4 terdapat 5 vertex yang disimbolkan dengan v1, v2, v3, v4 dan v5. Garis yang saling menghubungkan dari satu titik ke titik lainnya pada gambar disebut dengan edge. Angka-angka yang terdapat pada edge adalah bobot dari satu titik ke titik lainnya.

b. Pembuatan Modul MST Modul MST dirancang untuk dapat menyelesaikan permasalahan MST dengan

menerima

input

sejumlah

edge.

Kemudian

program

memberikan output berupa hasil jalur yang paling efisien. Modul ini dibangun menggunakan Algoritma Prim. Tahapan yang dilakukan untuk

23

menyelesaikan permasalahan MST menggunakan Algoritma Prim adalah sebagai berikut : 1. Pilih vertex awal secara acak untuk ditambahkan ke G. 2. Cari edge terpendek yang terhubung pada vertex di G. 3. Cek apakah vertex target pada edge terpilih, sudah terdapat pada G. 4. Tambahkan vertex ke G jika memenuhi kondisi pada langkah 3. 5. Lakukan langkah 2 sampai 4 hingga semua vertex terhubung. Langkah pengerjaan secara manual pada masalah MST dari file 1.dat dengan 5 vertex dan vertex awal adalah v1: 1. Tambahkan v1 kedalam G G = {v1} 2. Cari edge terpendek pada vertex di G, didapat edge e13 3. Tambahkan v3 ke G G = {v1, v3} 4. Cari edge terpendek pada vertex di G, yaitu edge e14 5. Tambahkan v4 kedalam list G G = {v1, v3, v4} 6. Cari edge terpendek pada vertex di G, didapat edge e12 7. Tambahkan v2 ke G G = {v1, v3, v4, v2} 8. Cari edge terpendek pada vertex di G, yaitu edge e15 9. Tambahkan v5 ke G G = { v1, v3, v4, v2, v5} 10. Selesai

24

Output edge: e13 = 1 e14 = 1 e12 = 2 e15 = 3 Total bobot = 7 Visualisasi dari graf yang dihasilkan pada masalah MST, digambarkan pada Gambar 3.5

Gambar 3.5 Visualisasi MST

c. Modul DCMST Modul DCMST ini adalah pengembangan dari modul MST dengan menambahkan masalah pembatasan degree pada tiap vertex-nya. Tahapan yang dilakukan untuk menyelesaikan permasalahan DCMST menggunakan Algoritma Modified Prim untuk DCMST sebagai berikut: 1. Pilih vertex awal secara acak untuk ditambahkan ke G. 2. Cari edge terpendek yang terhubung pada vertex di G. 3. Cek apakah vertex target pada edge terpilih sudah terdapat pada G.

25

4. Cek apakah jumlah degree atau edge yang terhubung pada vertex sumber lebih kecil dari maximum degree. 5. Tambahkan vertex ke G jika memenuhi kondisi pada langkah 3 dan 4. 6. Lakukan langkah 2 sampai 5 hingga semua vertex terhubung. Langkah pengerjaan secara manual pada masalah DCMST dari file 1.dat dengan jumlah 5 dan vertex awal adalah v1 serta maksimum degree adalah 3 : 1. Tambahkan v1 ke G G = {v1} 2. Cari edge terpendek pada vertex di G, didapat edge e13. 3. Tambahkan v3 ke G karena v1 sebagai vertex sumber masih memiliki degree atau jumlah vertex terhubung kurang dari maksimum degree. G = {v1, v3} 4. Cari edge terpendek pada vertex di G, yaitu edge e14. 5. Tambahkan v4 ke G karena masih memenuhi batas maksimum degree pada v1. G = {v1, v3, v4} 6. Cari edge terpendek pada vertex di G, didapat edge e12. 7. Tambahkan v2 ke G karena masih memenuhi batas maksimum degree pada v1 G = {v1, v3, v4, v2}

26

8. Cari edge terpendek pada vertex di G, yaitu edge e25, karena untuk edge e15. V1 sebagai vertex sumber telah mencapai batas maksimum degree. 9. Tambahkan v5 ke G G = {v1, v3, v4, v2, v5} 10. Selesai Output edge : e13 = 1 e14 = 1 e12 = 2 e25 = 5 Total bobot = 9 Visualisasi dari graf yang dihasilkan pada masalah DCMST digambarkan pada Gambar 3.6.

Gambar 3.6 Visualisasi DCMST

d. Modul MPDCMST

27

Modul MPDCMST ini adalah pengembangan dari modul DCMST dengan menambahkan kendala jumlah tahapan instalasi serta vertex prioritas. Tahapan yang dilakukan untuk menyelesaikan permasalahan MPDCMST menggunakan Algoritma Modified Prim untuk MPDCMST dijelaskan sebagai berikut: 1. Mulai periode 1. 2. Pilih vertex awal secara acak untuk disimpan ke G. 3. Cari edge terpendek yang terhubung pada vertex di G, dengan mengutamakan untuk memilih vertex yang diprioritaskan pada periode ini. 4. Cek apakah vertex target pada edge terpilih sudah terdapat pada G. 5. Cek apakah jumlah degree atau edge yang terhubung pada vertex sumber lebih kecil dari maximum degree. 6. Tambahkan vertex ke G jika memenuhi kondisi pada langkah 4 dan 5. 7. Lanjutkan ke periode berikutnya jika jumlah vertex pada periode ini telah mencapai jumlah yang ditentukan. 8. Lakukan langkah 2 sampai 7 hingga semua vertex terhubung. Berikut diberikan contoh pengerjaan secara manual pada masalah MPDCMST dengan batasan berikut : a. gunakan data dari file 1.dat b. jumlah vertex 5 c. sumber vertex = v1 d. maksimum degree = 3

28

e. jumlah tahapan 2; periode-1 install 2 vertex serta vertex prioritasnya adalah 5, periode-2 install 4 vertex Langkah-langkah pengerjaan dijelaskan sebagai berikut : 1. Tambahkan v1 ke G dan mulai periode-1. G = {v1} 2. Cari edge terpendek pada vertex di G dengan mengutamakan v5 yang menjadi prioritas pada tahap ini, didapat edge e15. 3. Tambahkan v5 ke G. G = {v1, v5} 4. Mulai periode-2 karena jumlah vertex maksimal pada periode-1 telah terpenuhi. 5. Cari edge terpendek pada vertex di G, didapat edge e14. 6. Tambahkan v4 ke G. G = {v1, v5, v4} 7. Cari edge terpendek pada vertex di G, yaitu edge e12. 8. Tambahkan v2 ke G karena masih memenuhi batas maksimum degree pada v1. G = {v1, v5, v4, v2} 9. Cari edge terpendek pada vertex di G, didapat edge e23, karena untuk edge e13. V1 telah mencapai batas maksimum degree. 10. Tambahkan v3 kedalam list G G = {v1, v5, v4, v2, v3} 11. Selesai Output edge :

29

Periode 1 e15 = 3 Periode 2 e14= 1 e12 = 2 e23 = 4 Total bobot = 10 Visualisasi dari graf yang dihasilkan pada masalah MPDCMST digambarkan pada Gambar 3.7 berikut.

Gambar 3.7 Visualisasi MPDCMST Vertex dengan warna hijau di-install pada periode 1 sedangkan yang berwarna biru di-install pada periode 2.

4. Testing Tahapan terakhir adalah pengujian program, dimana tujuan dari pengujian ini adalah untuk memastikan apakah program telah berfungsi sesuai dengan yang diharapkan. Apabila dari proses pengujian program didapati beberapa 30

kekurangan pada program, maka dilakukan revisi ulang untuk memperbaiki program tersebut. Selanjutnya jika program telah memenuhi pengujian awal maka dilakukan pengujian akhir program. Pada tahap ini program yang sudah dibuat perlu diuji coba sepenuhnya dengan menggunakan seluruh data yang ada. Dalam penelitian ini data yang digunakan adalah data dari penelitian Wamiliana dkk. (2015) sebelumnya, dan terdapat 300 file data.

Pengujian dibagi menjadi 10 kasus uji, dimana setiap kasus uji program diuji menggukan jumlah vertex yang berbeda-beda. Mulai dari jumlah vertex 10 ,20 ,30 ,40 ,50 ,60, 70, 80 ,90 sampai 100. Untuk setiap kasus uji, pengujian tidak hanya dilakukan pada masalah MPDCMST melainkan pada masalah DCMST dan MST. Hal ini bertujuan untuk melihat perbandingan bobot minimum yang dihasilkan dari ketiga metode tersebut. Selain itu pada setiap kasus uji, pengujian dilakukan terhadap 30 file uji berbeda. Selanjutnya dicari bobot minimum rata-rata yang didapatkan.

Kemudian dari hasil pengujian ini perlu didapatkan kesimpulan seputar hasil yang didapatkan dari program yang dibuat menggunakan Algoritma Modified Prim pada penelitian ini.

31

BAB V KESIMPULAN DAN SARAN

Penelitian pengembangan Algoritma Modified Prim untuk menyelesaikan masalah instalasi jaringan multi tahap telah selesai dilakukan. Berikut ini adalah beberapa kesimpulan dan saran yang dapat digunakan sebagai rujukan untuk penelitian selanjutnya.

5.1 Kesimpulan Berdasarkan hasil penelitan yang telah dilakukan, didapatkan beberapa kesimpulan sebagai berikut : 1. Solusi optimal MPDCMST dengan menggunakan Algoritma Modified Prim memiliki total bobot yang lebih besar dibandingkan MST dan DCMST yang diselesaikan menggunakan Algoritma Prim atau Modified Prim. Karena adanya kendala tambahan tahap pada MPDCMST. 2. Pada Algoritma WAC2, WAC4, WAC5 dan WAC6 rata-rata solusi yang dihasilkan memiliki kecenderungan mendekati DCMST seiring dengan semakin bertambahnya vertex. 3. Pada penelitian ini Algoritma Modified Prim yang memiliki hasil paling baik dalam menyelesaikan masalah MPDCMST adalah Algoritma WAC6,

65

jika dibanding dengan Algoritma WAC1, WAC2, WAC3, WAC4 dan WAC5. 4. Solusi yang didapatkan dari masalah MPDCMST menggunakan Algoritma WAC6 memiliki rata-rata bobot total yang lebih kecil dibanding menggunakan Algoritma WADR2 yang dikembangkan pada penelitian sebelumnya.

5.2 Saran Berikut ini adalah beberapa saran yang dapat digunakan untuk penelitian selanjutnya : 1. Memberikan tampilan GUI yang rapih serta informatif agar lebih memudahkan dalam melakukan pengujian. 2. Menambahkan fitur visualisasi graf menggunakan Java Native untuk memudahkan proses pengecekan secara manual. 3. Mengimplementasikan konsep Thread pada program agar dapat melakukan pencarian solusi dengan lebih cepat.

66

DAFTAR PUSTAKA

Astuti, Yuni Dwi. 2006. Logika dan Algoritma BAB 3. Jakarta : Universitas Gunadarma. Caccetta, L. and S.P. Hill. (2001). “A Branch and Cut Method for the DegreeConstrained Minimum Spanning Tree Problem.” Networks 37(2), 74–83. Junaidi A., Wamiliana, Dwi Sakethi, and Edy Tri Baskoro, 2008. ‘Computational Aspects for multiperiod degree constrained minimum spanning tree problem, Jurnal Sains MIPA, Special Edition, January 2008, pp. 1-5. Kawatra . 2002. ‘A Multiperiod degree constrained minimum spanning tree problem’, European Journal of Operational Research, Vol. 143, pp. 53-63. Lamia dkk. 2002. Extreme Programming. Software Enginering CSS 423 B – MWF 11-12. Liu, C.L. 1995. Dasar-dasar Matematika Diskrit. Jakarta : Penertbit PT Gramedia Pustaka Utama. Munir, Rinaldi. 2009. Matematika Diskrit. Edisi Ketiga. Bandung:Informatika. Nugraha, Deny Wiria. 2011. ‘Aplikasi Algoritma Prim untuk Menentukan Minimum Spanning Tree Suatu Graf Berbobot dengan Menggunakan Pemrogrograman Berorientasi Objek’. Jurnal Ilmiah Foristek Vol.1, No.2. pp 70-79. Oracle. 2016. Java Fundamentals BAB 1. Pressman, Roges S. 2010. ‘Software Enginering’. New York. McGraw-Hill Company. Wamiliana. 2015. Modul Kuliah Matematika Diskrit. Jurusan Matematika FMIPA Universitas Lampung. Wamilana, Dwi Sakethi, Akmal J., and Edy Baskoro. 2005. ‘The Design of

67

Greedy Algorithm for Solving the Multiperiod Degree Constrained Minimum Spanning Tree Problem’. Jurnal Sains dan Teknologi, Vol. 11 No. 2. pp 9396. Wamiliana, Faiz A. M. Elfaki, Mustofa Usman, and M. Azram, 2015 a. Some Greedy Based Algorithms for Multi Periods Degree Constrained Minimum Spanning Tree Problem. ARPN Journal of Engineering and Applied Science, Vol. 10 Issue 21, pp. 10147-10152. Wamiliana, Mustofa Usman, Dwi Sakethi, Restu Yuniarti and Ahmad Cucus, 2015 b. The Hybrid of Depth First Search Technique and Kruskal’s Algorithm for Solving The Multi Period Degree Constrained Minimum Spanning Tree Problem. IEEE Explore, 2016. http://ieeexplore.ieee.org/xpl/articleDetails.jps?arnumber=7516333&newsea rch=true&queryText=wamiliana Wibisono, Samuel. 2004. Matematika Diskrit. Yogyakarta : Penerbit Graha Ilmu.

68

PENGEMBANGAN ALGORITMA MODIFIED PRIM UNTUK MENYELESAIKAN MASALAH INSTALASI JARINGAN MULTI TAHAP

Recommend Documents