IMPLEMENTASI PENENTUAN MINIMUM SPANNING TREE (MST) DENGAN MENGGUNAKAN ALGORITMA PRIM
SKRIPSI
Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar Sarjana Sains
RUDI SURENDRO 041421011
Departemen Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara Medan 2008
Universitas Sumatera Utara
PERSETUJUAN
Judul
:
Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas
: : : : : :
IMPLEMENTASI PENENTUAN MINIMUM SPANNING TREE (MST) DENGAN MENGGUNAKAN ALGORITMA PRIM SKRIPSI RUDI SURENDRO 041421011 SARJANA S(1) MATEMATIKA MATEMATIKA MATEMATIKA DAN ILMU PENGETAHUAN ALAM (FMIPA) UNIVERSITAS SUMATERA UTARA
Diluluskan di Medan, Juni 2008 Komisi Pembimbing Pembimbing 2
Drs. Henry Rani Sitepu, M.Si NIP 131 12837 29
: Pembimbing 1
Drs. Marihat Situmorang, M.Kom NIP 131 8594 87
Diketahui/Disetujui oleh Departemen Matematika FMIPA USU Ketua,
DR. Saib Suwilo, M.Sc NIP 131 7961 49
Universitas Sumatera Utara
PERNYATAAN
IMPLEMENTASI PENENTUAN MINIMUM SPANNING TREE (MST) DENGAN MENGGUNAKAN ALGORITMA PRIM
SKRIPSI
Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.
Medan,
Juni 2008
RUDI SURENDRO 041421011
Universitas Sumatera Utara
PENGHARGAAN
Puji dan syukur penulis ucapkan pada Yang Maha Pemurah dan Maha Penyayang, dengan limpah karunia-Nya Tugas Akhir ini berhasil diselesaikan dalam waktu yang telah ditetapkan.
Ucapan terima kasih saya sampaikan pada Drs. Marihat Situmorang, M.Komp dan Drs. Henry Rani Sitepu, M.Si selaku pembimbing pada penyelesaian Tugas Akhir ini yang telah memberikan panduan penuh kepercayaan kepada saya untuk menyempurnakan Tugas Akhir ini. Panduan ringkas, padat dan profesional telah diberikan kepada saya agar penulis dapat menyelesaikan Tugas Akhir ini. Ucapan terima kasih juga ditujukan kepada Ketua dan Sekretaris Departemen Matematika, DR. Saib Suwilo, MSc dan Drs. Henry Rani Sitepu, M.Si, Dekan dan Pembantu Dekan FMIPA USU, semua dosen pada Departemen Matematika FMIPA USU, pegawai di FMIPA USU dan rekan-rekan kuliah. Akhirnya, tidak terlupakan kepada Bapak, Ibu dan semua sanak keluarga yang selama ini memberikan bantuan dan dorongan yang diperlukan. Semoga Tuhan Yang Maha Esa akan membalasnya.
Universitas Sumatera Utara
DAFTAR ISI
Halaman HALAMAN JUDUL
i
HALAMAN PERSETUJUAN
ii
PERNYATAAN
iii
PENGHARGAAN
iv
ABSTRAK
v
DAFTAR ISI
vi
DAFTAR GAMBAR
vii
BAB I PENDAHULUAN
1
1.1 Latar Belakang
1
1.2 Perumusan Masalah
2
1.3 Batasan Masalah
2
1.4 Tujuan Penelitian
2
1.5 Metode Penelitian
2
1.6 Sistematika Penulisan
3
BAB II LANDASAN TEORI
4
2.1 Definisi Graf
4
2.2 Jenis-jenis Graf
5
2.3 Terminologi Dasar Graf
7
2.4 Representasi Graf
10
2.5 Pohon (Tree)
12
2.5.1 Definisi Pohon
12
2.5.2 Sifat-Sifat Pohon
13
2.5.3 Pohon Merentang (Spanning Tree)
14
2.5.4 Pohon Merentang Minimum (Minimum Spanning Tree)
15
2.5.5 Algoritma Prim
16
BAB III PEMBAHASAN
Universitas Sumatera Utara
3.1 Implementasi Algoritma Prim Untuk Menentukan Minimal Spanning
17
Tree 3.2 Contoh Kasus Graf Berbobot Tidak Berarah
17
3.3 Pembahasan
21
3.4 Program Windows QM
33
3.5 Langkah-Langkah Penyelesaian
35
3.6 Hasil Perhitungan
37
BAB IV KESIMPULAN DAN SARAN
42
4.1 Kesimpulan
42
4.2 Saran
42
DAFTAR PUSTAKA LAMPIRAN
Universitas Sumatera Utara
DAFTAR GAMBAR
Halaman Gambar 2.1
(a) graf sederhana, (b) graf ganda, dan (c) graf semu
4
Gambar 2.2
(a) graf berarah, (b) graf ganda berarah
7
Gambar 2.3
Graf yang digunakan untuk menjelaskan terminologi pada graf
7
Gambar 2.4
Graf kosong N 5
8
Gambar 2.5
Graf Berbobot (Weighted Graph)
10
Gambar 2.6
Tiga buah graf dengan matriks ketetanggannya masing-masing
11
Gambar 2.7
Graf (atas) dan matriks bersisiannya (bawah)
12
Gambar 2.8
G 1 dan G 2 adalah pohon, sedangkan G 3 dan G 4 bukan pohon
13
Gambar 2.9
G adalah Graf, T 1 dan T 2 adalah Pohon Merentang dari Graf
14
G Gambar 2.10 G adalah Graf Berbobot, T 1 dan T 2 adalah Pohon Merentang
15
Berbobot dari Graf G. Gambar 3.1
Graf Jaringan listrik di 8 (delapan) kota
18
Gambar 3.2
Graf Jaringan Listrik 29 Kota (Rinaldi, 2005)
19
Gambar 3.3
Tampilan Sementara (splash) dari program QM for Windows
33
Gambar 3.4
Tampilan Awal Program QM for Windows
34
Gambar 3.5
Pilihan Modul yang tersedia pada program QM for Windows
34
Gambar 3.6
Tampilan Awal Modul Networks
35
Gambar 3.7
Tampilan Modul Networks setelah beberapa pilihan diisikan
36
Gambar 3.8
Tampilan untuk mengisikan angka-angka sesuai dengan
36
contoh kasus Gambar 3.9
Output dari penyelesaian Minimum Spanning Tree Jaringan
38
Listrik Antar Kota Gambar 4.0
Jalur Terpilih Pemasangan Jaringan Kabel Listrik di 8
39
(delapan) Kota Gambar 4.1
Jalur Alternatif Pemasangan Jaringan Kabel Listrik di 8
39
(delapan) Kota Gambar 4.2
Output dari penyelesaian Minimum Spanning Tree Jaringan
41
Listrik 29 (dua puluh sembilan) Kota di Jawa Tengah Gambar 4.3
Jalur Terpilih Pemasangan Jaringan Kabel Listrik 29 (dua
41
Universitas Sumatera Utara
puluh sembilan) Kota di Jawa Tengah
ABSTRAK
Graf merupakan salah satu metode untuk mencari solusi dari permasalahan diskrit yang ditemui dalam dunia nyata. Graf memilik banyak konsep. Salah satu diantaranya adalah konsep pohon. Konsep pohon merupakan konsep yang paling penting dan populer karena konsep ini mampu mendukung penerapan graf dalam berbagai bidang ilmu. Implementasi yang menggunakan konsep graf diantaranya adalah pemasangan jaringan kabel listrik. Menghadirkan graf dengan konsep pohon untuk memecahkan masalah yaitu dengan membangun graf menjadi pohon merentang minimum (MST). Salah satu algoritma yang dipakai dalam membangun pohon merentang minimum (MST) adalah algoritma Prim. Algoritma Prim mengeksplorasi banyak pilihan pada tiap langkah dan akan selalu menghasilkan pohon merentang minimum (MST). Dengan menggunakan Algoritma Prim, diharapkan nantinya didapat hasil akhir pohon merentang yang mempunyai jumlah jalur terpendek, dengan kata lain pohon merentang minimum.
Universitas Sumatera Utara
