Minimum Spanning Tree

Minimum Spanning Tree

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.

Gambar ini adalah graf berbobot awal. Pada awalnya graf tersebut bukan pohon karena terdapat sirkuit. Setelah penjelasan sebelumnya dilakukan, maka akan terdapat suatu jalur dan itu disebut minimum spanning tree. Salah satu contohnya adalah perusahaan TV kabel yang memasang kabel ke lingkungan baru. Jika dibatasi untuk mengubur kabel hanya di sepanjang jalan tertentu, maka ada graf yang mewakili suatu jalur. Beberapa jalur tersebut mungkin akan lebih lama, karena memerlukan kabel yang akan dikubur lebih dalam, sehingga membutuhkan biaya yang lebih mahal. Dengan adanya minimum spanning tree, maka akan didapatkan total biaya yang lebih rendah.

Kemungkianan Keseragaman

Dalam suatu graf memungkinkan adanya kesamaan bobot pada setiap ruas untuk menuju simpul tujuan. Dengan ini, maka akan adanya perbedaan jalur, tetapi stiap jalur tersebut memiliki total bobot yang sama.

Keunikan

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.

Sirkuit

Pada dasarnya dalam sebuah pohon, tidak diperkenankan adanya sirkuit. Untuk mendapatkan minimum spanning tree maka akan ditelusuri suatu jalur yang memiliki bobot terkecil dengan menghindari adanya sirkuit.

Algoritma

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.

Source article :

http://en.wikipedia.org/wiki/Minimum_spanning_tree