Data Skripsi
| Judul | : | ALGORITMA UNTUK MENDAPATKAN POHON PEMBANGKIT MINIMUM |
| Jenis | : | Skripsi |
| Penulis | : | Deri Dayandri |
| NRP | : | G260837 |
| Tanggal Lulus | : | 22 May 1996 |
| Tanggal Seminar | : | |
| Tanggal Sidang | : | |
| Pembimbing | : |
Dr. Ir. Fahren Bukhari, M.Sc. Dr. Ir. Amril Aman, M.Sc. |
| Ringkasan | : | Pohon pembangkit (spaning tree) adalah salah satu bentuk graf yang menarik untuk diamati.Graf tersebut terdiri atas sejumlah simpul dan sejumlah sisi,dimana jumlah sisi minimum untuk membuat graf tersebut tetap terhubung (connected).Pada suatu graf terhubung ,dapat saja dihasilkan beberapa pohon pembangkit.Untuk graf penghubung yang diberi bobot (setiap sisi mempunyai bobot yang biasanya menunjukkan jarak,panjang,waktu,biaya,dan lain-lain) pohon-pohon pembangkit yang dihasilkan akan memiliki bermacam-macam bobot pula tergantung dari sisi-sisi yang terpilih.Pohon pembangkit dengan bobot terkecil disebut dengan pohon pembangkit minimum (minimum spaning tree). Salah satu algoritma yang populer untuk mendapatkan pohon pembangkit minimum dari sembarang graf terhubung adalah Algoritma Kruskal.Algoritma ini dimulai dengan mengurutkan semua sisi graf tersebut dalam urutan tak turun berdasarkan bobot sisi-sisi itu sendiri.Proses pengurutan sisi yang dilakukan oleh Algoritma Kruskal tentunya merupakan proses yang cukup rumit dan memerlukan langkah yang cukup banyak.Proses pengurutan yang paling baik mempunyai kompleksitas 0(n log n),dengan n menunjukkan jumlah item yang diproses.Proses berikutnya adalah proses pemeriksaan putaran untuk setiap sisi yang ditambahkan pada graf target.Proses ini pun memerlukan langkah.Dengan struktur data yang cukup baik,pemeriksaan putaran mempunyai kompleksitas O(log n),dengan n menunjukkan jumlah item yang diperiksa.Secara sederhana dan dapat dibuktikan,Algoritma Kruskal mempunyai kompleksitas 0(n log n) dengan n menunjukkan jumlah sisi yang diproses. |
Copyright © 2024 Matematika IPB
