PENERAPAN ALGORITMA POHON MERENTANG MINIMUM PADA GRAF TERHUBUNG BERBOBOT TAK BERARAH DENGAN MATLAB R2012B
| Main Author: | NURHAM, HAMIM AFIF |
|---|---|
| Format: | Thesis NonPeerReviewed Book |
| Bahasa: | eng |
| Terbitan: |
, 2015
|
| Subjects: | |
| Online Access: |
http://eprints.umm.ac.id/25738/1/jiptummpp-gdl-hamimafifn-38315-1-pendahul-n.pdf http://eprints.umm.ac.id/25738/2/jiptummpp-gdl-hamimafifn-38315-2-babi.pdf http://eprints.umm.ac.id/25738/ |
Daftar Isi:
- Pohon merentang merupakan salah satu konsep yang dikembangkan dalam teori graf. Pohon merentang membentuk sebuah graf dengan semua titiknya terhubung tetapi memuat lintasan tertutup atau siklus. Pohon merentang diterapkan dibeberapa bidang ilmu seperti komputer, teknik sipil, dan industri. Sebuah pohon merentang dengan jumlah bobot seluruh sisinya terkecil diantara pohon merentang lainnya disebut dengan pohon merentang minimum. Pohon merentang minimum dari sebuah graf terhubung berbobot dapat dicari dengan menggunakan dua algoritma yaitu algoritma Kruskal dan algoritma Prim. Algoritma Kruskal membentuk pohon merentang minimum dari sebuah graf terhubung berbobot dengan mengurutkan bobot sisi dari terkecil hingga terbesar kemudian memasukkan satu per satu sisi dengan bobot minimum ke dalam himpunan sisi pohon merentang minimum hingga semua titik terhubung dan tidak membentuk siklus. Sedangkan algoritma Prim membentuk pohon merentang minimum dari sebuah graf dengan menentukan titik awal kemudian mencari sisi-sisi berbobot minimum yang bersisian dengan titik awal dan titik selanjutnya, hingga semua titik terhubung dan tidak membentuk siklus. Penentuan pohon merentang minimum dari sebuah graf dengan jumlah titik yang besar dapat dipermudah dengan menggunakan bantuan program komputer, salah satunya adalah dengan bahasa pemrograman berbasis matriks yaitu MATLAB R2012b. Algoritma pohon merentang minimum disusun ke dalam bahasa pemrograman MATLAB R2012b sehingga menghasilkan program yang dapat mencari pohon merentang minimum dari sebuah graf. Hasil perhitungan yang ditampilkan berupa gambar pohon merentang minimum serta jumlah bobot minimumnya.