Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size blue color orange color green color Sign In

Matematika IPB

Beranda arrow Akademik arrow S-1 Matematika arrow Karya Ilmiah Alumni
 
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.

Random Quotes

Perbaikilah dirimu sendiri, niscaya orang lain akan berbuat baik kepadamu

anonim