Minimum Spanning Tree

Minimum Spanning Tree

Minimum spanning tree adalah suatu pohon yang dapat didefinisikan dengan sebuah graf. Grafberarah 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.

Minimum Spanning Tree (MST) / Pohon Rentangan Minimum

Apabila G suatu graf berbobot (suatu Network), maka Minimun Spanning Tree dari G adalah Spanning Tree dengan jumlah bobot terkecil.

Dalam aplikasinya problem ini misalnya :

• Hendak direntangkan jaringan kabel listrik yang menghubungkan sejumlah lokasi dengan panjang kabel yang digunakan sependek-pendeknya mungkin.

• Melihat pengelompokan data yang tersebar pada suatu ruang.

• Perencanaan jaringan transportasi/distribusi barang.

Untuk mendapatkan Minimum Spanning Tree, dapat digunakan algoritma :

1. Algoritma Solin

2. Algoritma Kruskal