Minimum
Spanning Tree
1.1.1 Pengertian
Minimum
spanning tree adalah suatu pohon yang dapat didefinisikan dengan sebuah graf.
Graf berarah dan graf tidak berarah adalah subgraf yang setiap
node/simpulnya terkoneksi satu sama lain. Sebuah graf, dapat memberikan pohon
rentang yang berbeda. Pada setiap ruas/edge, kita dapat memberikan suatu bobot
untuk menentukan suatu nilai. Setiap bobot tersebut akan dibandingkan dengan
bobot yang lain yang mengarah pada simpul berikutnya, selanjutnya akan dipilih
bobot yang terkecil. Hal ini akan terus dilakukan sampai menuju simpul tujuan.
Ini yang disebut dengan minimum spanning tree.
1.1.2 Sejarah Singkat
Algoritma pertama untuk mencari
pohon rentang minimum dikembangkan oleh ilmuwan Ceko Otakar Borůvka pada tahun
1926 (lihat algoritma Borůvka's). Tujuannya adalah cakupan listrik efisien
Moravia. Sekarang ada dua algoritma yang umum digunakan, algoritma Prim dan
algoritma Kruskal's. Ketiga adalah algoritma greedy yang dijalankan dalam waktu
polynomial. Algoritma greedy lainnya tidak umum digunakan adalah algoritma
reverse-delete, yang merupakan kebalikan dari algoritma Kruskal's. Algoritma
minimumspanning tree tercepat sampai saat ini dikembangkan oleh Bernard
Chazelle, dengan running time adalah O (m α (m, n)), di mana m adalah jumlah
ruas, n adalah jumlah simpul dan α adalah kebalikan fungsional klasik dari
fungsi Ackermann. Fungsi ini tumbuh sangat lambat.
Baru-baru ini, penelitian telah
difokuskan pada pemecahan masalah minimum spanning tree dengan cara yang sangat
parallelized. Dengan jumlah prosesor linier yang mungkin untuk memecahkan
masalah dalam O (logn) kali. Sebuah penulisan pada tahun 2003 "Fast
Shared-Memory Algorithms for Computing the Minimum Spanning Forest of Sparse
Graphs" oleh David A. Bader dan Guojing Cong mendemonstrasikan
algoritma pragmatic yang dapat mengkomputasi MST 5 kali lebih cepat
didalam 8 prosesor daripada algorima optimized sequential.
Algoritma khusus lainnya telah
dirancang untuk komputasi pohon rentang minimum dari suatu graf begitu besar
sehingga sebagian besar harus disimpan pada disk setiap saat. Algoritma
penyimpanan eksternal ini, misalnya seperti yang dijelaskan dalam
"Rekayasa sebuah Memori Eksternal Minimum Spanning Tree Algoritma"
oleh Romawi Dementie dapat beroperasi setidaknya 2 sampai 5 kali lebih lambat
dari algoritma tradisional di memori. mereka mengklaim bahwa "minimum
spanning tree masalah besar mengisi beberapa hard disk dapat diatasi semalam di
PC."Mereka mengandalkan efisien algoritma pengurutan penyimpanan eksternal
dan teknik grafik kontraksi untuk mengurangi ukuran grafik secara
efisien. Masalahnya juga dapat didekati dengan cara yang didistribusikan.
Jika masing simpul dianggap komputer dan simpul tidak tahu apa-apa kecuali link
terhubung, kita masih dapat menghitung distribusi pohon rentang minimum.
1.2 Keunggulan
Jika setiap ruas
memiliki bobot yang berbeda, maka akan ada satu minimum spanning tree yang
unik. Hal ini dapat dibuktikan dengan induksi atau kontradiksi. Hal
ini berlaku dalam situasi yang realistis, seperti contoh perusahaan TV kabel di
atas, dimana tidak ada dua jalur yang memiliki biaya yang sama persis.
Minimum Spanning
tree juga dapat disebut sebagai biaya graf minimum. Sebagai contoh, apabila
kita akan menuju suatu tempat dengan banyak jalur yang ada, kita akan
membutuhkan biaya yang mahal untuk mencapai suatu tempat tersebut dengan jalur
yang tidak optimal. Dengan adanya minimum spanning tree ini, kita dapat
mengetahui jalur mana yang harus dilewati sehingga hanya memerlukan biaya yang
murah, dan waktu yang lebih cepat.
Minimum
Spanning Tree juga dapat menyediakan system jalur backup &
juga mencegah loop yang tidak diinginkan pada jaringan yang memiliki beberapa
jalur menuju ke satu tujuan dari satu host. Loop terjadi bila ada route/jalur alternative di antara
host-host. Untuk menyiapkan jalur back up, Spanning tree membuat status jalur
back up menjadi stand by atau diblock. Spanning tree hanya membolehkan satu
jalur yang active (fungsi pencegahan loop) di antara dua host namun menyiapkan
jalur back up bila jalur utama terputus. Bila "cost" spanning tree berubah atau ada
jalur yang terputus, algoritma spanning tree mengubah topology spanning tree
dan mengaktifkan jalur yang sebelumnya stand by. Tanpa spanning tree pun sebenarnya memungkinkan koneksi
antara dua host melewati beberapa jalur sekaligus namun dapat juga membuat
looping yang tidak pernah akan selesai di dalam jaringan anda. Yang pasti akan
menghabiskan kapasitas jalur yang ada hanya untuk melewatkan packet data yang
sama secara berulang dan berlipat ganda.
1.3 Proses Pengubahan
Langkah-langkah dalam membuat
spanning tree adalah sebagai berikut:
a. Langkah pertama, cari nilai cost
yang terkecil. Dengan cost yang kecil maka biaya yang dibutuhkan lebih murah.
Karena cost diatas yang terkecil nilainya 2 maka harus didahulukan terlebih
dahulu.
b. Langkah kedua, mencari nilai cost yang
terkecil pula. Terdapat 3 nilai edge yang kecil yaitu antara CE, DE, dan AF.
Kita boleh mempergunakan salah satu dari edge tersebut. Saya mengambil edge
antara DE.
c. Langkah ketiga, sekarang edge yang
costnya terkecil tinggal CE dan AF. Untuk mencari nilai spanning tree harus
membentuk cabang/pohon maka saya mempergunakan edge yang AF, karena jika saya
mengabil edge CE maka spanning tree akan membentuk sebuah loop. Secara teori
jika spanning tree membentuk sebuah loop maka costnya menjadi lebih besar. Oleh
karena itu saya mengambil edge AF agar costnya menjadi murah.
d. Langkah keempat, mencari nilai
cost yang lebih murah. Karena nilai cosnya bernilai 4 sudah tidak ada, maka
saya mencari alternative cost yang lebih murah. Terdapat edge BC, BE, FE. Maka
saya mengambil edge BC, FE, atau BE secara sembarang. Saya mengambil edge BC.
e. Langkah kelima, hasil akhir dari
spanning tree sudah terlihat yaitu tinggal menghubungkan edge FE. Karena nilai
costnya yang paling murah dibandingkan dengan nilai cost yang lainnya.
f.
Kesimpulan, jika kita ingin membuat route spanning tree kita yang kita
harus lakukan adalah mecari nlai cost yang terkecil, lalu jangan membuat suatu
loop karena akan terjadi pemborosan.
1.4 Print
Out Minumum Spaning Tree
