TUGAS AKHIR
PENCARIAN POHON MERENTANG MINIMUM MENGGUNAKAN ALGORITMA PRIM DAN ALGORITMA KRUSKAL TERHADAP PEMECAHAN MASALAH OPTIMASI JALUR REL PADA RENCANA PEMBANGUNAN P E R K E R E T AA P I A N D I B A L I
KOMPETENSI TERAPAN [ SKRIPSI ]
GABRIELLA WIBOWO 0708405039
JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS UDAYANA BUKIT JIMBARAN 2011
TUGAS AKHIR
PENCARIAN POHON MERENTANG MINIMUM MENGGUNAKAN ALGORITMA PRIM DAN ALGORITMA KRUSKAL TERHADAP PEMECAHAN MASALAH OPTIMASI JALUR REL PADA RENCANA PEMBANGUNAN P E R K E R E T AA P I A N D I B A L I
KOMPETENSI TERAPAN [ SKRIPSI ]
GABRIELLA WIBOWO 0708405039
JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS UDAYANA BUKIT JIMBARAN 2011
i
LEMBAR PENGESAHAN JUDUL
: Pencarian Pohon Merentang Minimum Menggunakan Algoritma Prim dan Algoritma Kruskal Terhadap Pemecahan Masalah Optimasi Jalur Rel pada Rencana Pembangunan Perkeretaapian di Bali.
NAMA
: Gabriella Wibowo
NIM
: 0708405039
JURUSAN
: Matematika
KOMPETENSI
: Finansial
TANGGAL UJIAN
: 24 Oktober 2011 Disetujui oleh:
Pembimbing II
Pembimbing I
I Made Eka Dwipayana, S.Si., M.Si.
Ni Ketut Tari Tastrawati, S.Si., M.Si.
NIP 19820514 200812 1 001
NIP 19740528 200212 2 002
Penguji III
Penguji II
Penguji I
Ir. I Putu Eka N. Kencana, M.T.
Drs. G.K. Gandhiadi, M.T.
Drs. I Nyoman Widana, M.Si.
NIP 19650614 199203 1 004
NIP 19620930 198803 1 002
NIP 19640808 199103 1 004
Mengetahui, Ketua Jurusan Matematika FMIPA Universitas Udayana
Drs. G.K. Gandhiadi, M.T. NIP 19620930 198803 1 002
iv
Judul
: Pencarian Pohon Merentang Minimum Menggunakan Algoritma
Prim
dan
Algoritma
Kruskal
Terhadap
Pemecahan Masalah Optimasi Jalur Rel pada Rencana Pembangunan Perkeretaapian di Bali. Penulis
: Gabriella Wibowo
Dosen Pembimbing
: 1. Ni Ketut Tari Tastrawati, S.Si., M.Si. 2. I Made Eka Dwipayana, S.Si., M.Si.
ABSTRAK Algoritma Prim dan algoritma Kruskal merupakan algoritma yang paling sering digunakan dalam pemecahan masalah pohon merentang minimum. Secara umum, kedua algoritma ini memberikan hasil pohon merentang minimum yang berbobot sama. Beberapa persoalan dalam dunia nyata, seperti: perancangan jaringan komputer, pemasangan kabel listrik, pengadaan saluran air, pembuatan jalan raya, pembangunan rel kereta api dan lain-lain, dapat direpresentasikan ke dalam bentuk graf untuk kemudian dipecahkan melalui pencarian pohon merentang minimum dengan menggunakan algoritma Prim dan algoritma Kruskal. Misalkan pada pembangunan rel kereta api, untuk menghubungkan kota-kota yang ada di suatu wilayah, sebenarnya kita tidak perlu menghubungkan seluruhnya melainkan cukup dengan menghubungkan beberapa kota di antaranya saja, yaitu dengan memanfaatkan algoritma Prim dan algoritma Kruskal. Namun, kedua algoritma tersebut memiliki kelebihan dan kekurangan masing-masing. Kelebihan dan kekurangan ini memungkinkan penggunanya memilih algoritma mana yang lebih efektif untuk diterapkan pada jenis graf tertentu. Dalam makalah ini akan dibahas dan dibandingkan keefektifan dari kedua algoritma tersebut secara umum. Kata kunci: algoritma Prim, algoritma Kruskal, pohon merentang minimum, graf.
v
Title
: Minimum Spanning Tree Search Using Prim's Algorithm and Kruskal's Algorithm Against Optimization Problem Solution of Rail Line in The Development Plan Railroad in Bali.
Author
: Gabriella Wibowo
Tutors
: 1. Ni Ketut Tari Tastrawati, S.Si., M.Si. 2. I Made Eka Dwipayana, S.Si., M.Si.
ABSTRACT Prim’s algorithm and Kruskal’s algorithm are the most frequently used algorithms in solving the minimum spanning tree problem. In general, both these algorithms give the minimum spanning tree results are weighted the same. Some problems in the real world, such as: designing computer networks, electrical wiring, water supply lines, making roads, construction of railroads, and others can be represented in graph form and then solved by searching the minimum spanning tree using the Prim’s algorithm and Kruskal’s algorithm. Suppose that in the construction of railroads, to connect the cities in a region, we actually do not need to interconnect all but simply by connecting several cities in among, that is by using Prim's algorithm and Kruskal’s algorithm. However, both these algorithms has advantages and disadvantages of each. Advantages and disadvantages of this algorithms allows users to choose which is more effectively to apply to certain types of graphs. In this paper will be discussed and compared the effectiveness of both algorithms in general. Key words: Prim's algorithm, Kruskal's algorithm, minimum spanning tree, graph.
vi
KATA PENGANTAR
Puji syukur penulis panjatkan ke hadirat Tuhan Yang Maha Esa, karena atas rahmat dan karunia-Nya penulis dapat merampungkan tugas akhir ini dengan lancar dan tepat waktu. Skripsi ini disusun sebagai upaya untuk menerapkan pemahaman mengenai berbagai mata kuliah yang telah didapat selama ini, dalam rangkaian kegiatan pelaksanaan tugas akhir di Jurusan Matematika, Fakultas MIPA, Universitas Udayana. Dimana, pada kesempatan ini penulis mengangkat judul “PENCARIAN POHON MERENTANG MINIMUM MENGGUNAKAN ALGORITMA PRIM DAN ALGORITMA KRUSKAL TERHADAP PEMECAHAN MASALAH OPTIMASI
JALUR
REL
PADA
RENCANA
PEMBANGUNAN
PERKERETAAPIAN DI BALI”. Pada kesempatan ini pula, tidak lupa penulis mengucapkan terima kasih yang sebesar-besarnya kepada seluruh pihak yang telah membantu terwujudnya tugas akhir ini, diantaranya: 1. Bapak Drs. G.K. Gandhiadi, M.T. selaku Ketua Jurusan Matematika, Fakultas MIPA, Universitas Udayana. 2. Bapak Ir. I Putu Eka Nila Kencana, M.T. selaku Ketua Komisi Tugas Akhir Jurusan Matematika. 3. Ibu Ni Ketut Tari Tastrawati, S.Si., M.Si. selaku dosen pembimbing I dan Bapak I Made Eka Dwipayana, S.Si., M.Si. selaku dosen pembimbing II, yang dengan sukarela telah meluangkan banyak waktu untuk memberikan
vii
bimbingan, arahan, bantuan, motivasi, dan kontribusi dalam menyusun tugas akhir ini hingga selesai. 4. Bapak Drs. I Nyoman Widana, M.Si. selaku dosen penguji I, Bapak Drs. G.K. Gandhiadi, M.T. selaku dosen penguji II, Bapak Ir. I Putu Eka Nila Kencana, M.T. selaku dosen penguji III, yang telah bersedia untuk menguji dan bermurah hati dalam memberikan penilaian tugas akhir ini.. 5. Para Dosen Jurusan Matematika, yang telah menjadi pengajar matematika yang baik dan senantiasa membagikan ilmu dengan sukarela, beserta segenap staf/pegawai. 6. Bapak Ir. I Gusti Bagus Putra Budiartha, M.M. selaku Kepala Dinas Pekerjaan Umum Pemerintah Provinsi Bali yang telah memberikan ijin untuk melakukan pencarian data demi kepentingan tugas akhir ini. 7. Orang Tua dan seluruh keluarga besar, yang selalu mendoakan, mencintai, menyayangi, mendanai, dan mendukung setiap langkah yang penulis tempuh, khususnya dalam mengerjakan tugas akhir ini. 8. Teman-teman seangkatan dan keluarga besar HIMATIKA, yang selama ini selalu bersikap baik dan telah banyak memberikan pelajaran mengenai watak/karakter manusia yang berbeda-beda. 9. Artikel yang sangat menginspirasi, yang tanpa sengaja penulis temukan hingga akhirnya diperoleh ide untuk mengangkat kasus tersebut sebagai permasalahan skripsi. 10. Seluruh pihak yang telah memberikan sumbangsih dalam bentuk moral dan moril, yang tidak dapat penulis sebutkan satu per satu.
viii
Sehingga, karena bantuan mereka itulah tugas akhir ini telah rampung dan dapat tersusun dengan sebaik mungkin. Namun, dikarenakan keterbatasan kemampuan dan kurangnya pengalaman, penulis menyadari bahwa skripsi ini masih jauh dari sempurna, sebagaimana pepatah mengatakan, “Tiada Gading yang Tak Retak”. Oleh karena itu, dengan segala kerendahan hati penulis mengharapkan kritik dan saran dari pembaca untuk memperbaiki tugas akhir ini agar jauh lebih baik dari sebelumnya. Sekian dan Terima Kasih.
Denpasar, September 2011
Penulis
ix
DAFTAR ISI
LEMBAR JUDUL ………………………………………………………....
i
LEMBAR PERSEMBAHAN ……………………………………………..
ii
LEMBAR PERNYATAAN ……………………………………………….
iii
LEMBAR PENGESAHAN …………………………………………….....
iv
ABSTRAK ………………………………………………………………...
v
KATA PENGANTAR …………………………………………………… .
vii
DAFTAR ISI ………………………………………………………………
x
DAFTAR TABEL …………………………………………………………
xiv
DAFTAR GAMBAR …………………………………………………….. .
xv
DAFTAR LAMPIRAN …………………………………………………... .
xvi
BAB I : PENDAHULUAN ……………………………………………..
1
1.1 Latar Belakang ………………………………………………………...
1
1.2 Rumusan Masalah ……………………………………………………..
4
1.3 Batasan Masalah ………………………………………………………
4
1.4 Tujuan Penelitian ……………………………………………………...
4
1.5 Manfaat Penelitian …………………………………………………….
5
BAB II : TINJAUAN PUSTAKA ………………………………………
6
2.1 Graf (Graph) …………………………………………………………..
6
2.2 Upagraf (Subgraph) …………………………………………………...
6
2.3 Terminologi dalam Graf ………………………………………………
7
x
2.3.1 Ketetanggaan (Adjacent) ……………………………………….
7
2.3.2 Keterkaitan (Incident) …………………………………………..
7
2.3.3 Derajat (Degree) ………………………………………………..
8
2.3.4 Gelang (Loop) ………………………………………………….
8
2.3.5 Jalan (Walk) …………………………………………………….
8
2.3.6 Lintasan (Path) …………………………………………………
8
2.3.7 Jejak (Trail) …………………………………………………….
9
2.3.8 Siklus (Cycle) ………………………………………………......
9
2.3.9 Sirkuit (Circuit) ………………………………………………...
9
2.4 Jenis-Jenis Graf ……………………………………………………….
9
2.4.1 Berdasarkan Ada Tidaknya Sisi Ganda ………………………..
10
2.4.1.1 Graf Sederhana (Simple Graph) ………………………
10
2.4.1.2 Graf Tak-Sederhana (Unsimple Graph) ……………....
10
2.4.2 Berdasarkan Ada Tidaknya Orientasi Arah ……………………
11
2.4.2.1 Graf Berarah (Directed Graph) ……………………….
11
2.4.2.2 Graf Tak-Berarah (Undirected Graph) ……………….
12
2.4.3 Berdasarkan Ada Tidaknya Keterhubungan …………………...
12
2.4.3.1 Graf Terhubung (Connected Graph) ………………….
12
2.4.3.2 Graf Tak-Terhubung (Disconnected Graph) ………….
12
2.4.4 Graf Lingkaran (Circle Graph) ………………………………...
13
2.4.5 Graf Lengkap (Complete Graph) ………………………………
14
2.4.6 Graf Berbobot (Weighted Graph) ……………………………...
14
2.5 Representasi Graf ……………………………………………………..
15
xi
2.5.1 Matrik Ketetanggaan (Adjacency Matrix) ……………………..
15
2.5.2 Matrik Keterkaitan (Incidency Matrix) ………………………...
16
2.6 Pohon (Tree) …………………………………………………………..
16
2.7 Sifat-Sifat Pohon (Tree’s Properties) …………………………………
17
2.8 Pohon Merentang (Spanning Tree) ……………………………………
17
2.9 Pohon Merentang Minimum (Minimum Spanning Tree) ……………..
18
2.10 Hutan (Forest) ……………………………………………………….
19
2.11 Algoritma (Algorithm) ……………………………………………….
19
2.12 Algoritma Prim (Prim’s Algorithm) …………………………………
20
2.12.1 Sejarah Algoritma Prim ……………………………………..
20
2.12.2 Konsep Algoritma Prim ……………………………………..
20
2.13 Algoritma Kruskal (Kruskal’s Algorithm) …………………………..
21
2.13.1 Sejarah Algoritma Kruskal ………………………………….
21
2.13.2 Konsep Algoritma Kruskal ………………………………….
22
2.14 Optimasi …………………………………………………………….
23
2.15 Pemecahan Masalah Optimasi …...………………………………….
23
BAB III : METODE PENELITIAN …………………………………….
24
3.1 Tempat dan Waktu Penelitian ………………………………………...
24
3.2 Jenis Penelitian ………………………………………………………..
24
3.3 Jenis Data ……………………………………………………………..
24
3.4 Sumber Data …………………………………………………………..
25
3.5 Metode Pengumpulan Data …………………………………………...
25
3.6 Variabel Penelitian ……………………………………………………
26
xii
3.7 Langkah-Langkah Penelitian ………………………………………....
26
BAB IV : HASIL DAN PEMBAHASAN ……………………………..
29
4.1 Data dan Fakta ………………………………………………………..
29
4.2 Pemecahan Rumusan Masalah Pertama ………………..…………….
32
4.2.1 Dengan menggunakan algoritma Prim ………………………...
32
4.2.2 Dengan menggunakan algoritma Kruskal ……………………..
37
4.3 Pembobotan …………………………………………………………..
44
4.3.1 Pembobotan Terhadap Jarak …………………………………..
44
4.3.2 Pembobotan Terhadap Medan Jalan …………………………..
45
4.4 Pemecahan Rumusan Masalah Kedua …………………….………….
51
4.4.1 Dengan menggunakan algoritma Prim ………………………...
51
4.4.2 Dengan menggunakan algoritma Kruskal ……………………..
56
4.5 Perbandingan-Perbandingan ………………………………………….
62
4.5.1 Perbandingan Dari Segi Proses ………………………………..
62
4.5.2 Perbandingan Dari Segi Hasil …………………………………
63
BAB V : KESIMPULAN DAN SARAN ……………………………...
65
5.1 Kesimpulan …………………………………………………………...
65
5.2 Saran ………………………………………………………………….
65
DAFTAR PUSTAKA ……………………………………………………..
67
LAMPIRAN
xiii
DAFTAR GAMBAR
Gambar 2.1 Graf G …………………………………………………….…..
6
Gambar 2.2 Graf G dan 3 Contoh Upagrafnya H1, H2, H3 …………….…..
7
Gambar 2.3 Adjacent dan Incident …………………………………….…..
7
Gambar 2.4 Loop …………………………………………………….…….
8
Gambar 2.5 Walk, Path, Trail, Cycle, dan Circuit ………………….……..
9
Gambar 2.6 Graf Sederhana ………………………………………….……
10
Gambar 2.7 Graf Tak-Sederhana (Graf Ganda) …………………….……..
11
Gambar 2.8 Graf Tak-Sederhana (Graf Semu) ……………………….…...
11
Gambar 2.9 Graf Berarah ………………………………………………….
12
Gambar 2.10 Graf Tak-Berarah …………………………………………...
12
Gambar 2.11 Graf Terhubung ……………………………………………..
13
Gambar 2.12 Graf Tak-Terhubung ………………………………………...
13
Gambar 2.13 Graf Lingkaran ……………………………………………...
13
Gambar 2.14 Graf Lengkap ……………………………………………….
14
Gambar 2.15 Graf Berbobot ………………………………………………
14
Gambar 2.16 Matrik Ketetanggaan ……………………………………….
15
Gambar 2.17 Matrik Keterkaitan ………………………………………….
16
Gambar 2.18 Pohon ……………………………………………………….
16
Gambar 2.19 Graf G dan 4 Contoh Pohon Merentangnya T1, T2, T3, T4 ….
18
Gambar 2.20 Graf dan Pohon Merentang Minimumnya ………………….
18
Gambar 2.21 Hutan ………………………………………………………..
19
xv
DAFTAR LAMPIRAN
Lampiran 1
Surat Permohonan Ijin Pencarian Data. (Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Udayana)
Lampiran 2
Surat Pemberian Ijin Pencarian Data. (Dinas Pekerjaan Umum Pemerintah Provinsi Bali)
Lampiran 3
Data Jarak Antar Ibukota Kabupaten di Provinsi Bali.
Lampiran 4
Data Medan Jalan Antar Ibukota Kabupaten di Provinsi Bali.
Lampiran 5
Artikel-Artikel yang Mendukung Penelitian: Bali Bakal Punya Jalur Kereta Api. Tunjang Pariwisata, Kereta Api Bakal Dibangun di Bali. Bali Akan Bangun Jalur Kereta Api Keliling Pulau.
xvi
