Pohon Rentang Minimum

                                                    

      Pohon rentang minimum (minimal spanning tree) adalah teknik mencari jalan penghubung yang dapat menghubungkan semua titik dalam jaringan secara bersamaan sampai diperoleh jarak minimum.

      Masalah pohon rentang minimum serupa dengan masalah rute terpendek (shortest route), kecuali bahwa tujuannya adalah untuk menghubungkan seluruh simpul dalam jaringan sehingga total panjang cabang tersebut diminimisasi. Jaringan yang dihasilkan merentangkan (menghubungkan) semua titik dalam jaringan tersebut pada total jarak (panjang) minimum.

Langkah-langkah dari pohon rentang minimum adalah :

1. pilih secara arbitrer sebuah node dalam jaringan
2. hubungkan node tersebut dengan node terdekat yang dapat meminimalkan total jarak
3. perhatikan semua node apakah terdapat node yang belum terhubung, temukan dan hubungkan node terdekat yang belum terhubung
4. ulangi langkah ketiga sampai seluruh node dapat terhubung

       Sebagai contoh, gedung Istec Corporation yang baru memiliki beberapa ruangan dan tiap ruangan membutuhkan 1 lubang aliran listrik (atau biasa disebut sebagai steker). Teknisi listrik akan menyalurkan listrik dari ruang bagian depan sampai keseluruh ruangan dengan total panjang kabel yang seefisien mungkin. Adapun jarak antar ruangan dapat digambarkan dalam gambar jaringan berikut ini, sedangkan ruang bagian depan digambarkan sebagai node-1.

           Karena node-1 adalah ruangan terdepan yang menjadi sumber aliran listrik utama, maka node-1 akan dijadikan sebagai patokan dalam jaringan. Node yang paling dekat dengan node-1 adalah node dengan jarak 2 meter, sehingga kita hubungkan node 1 dengan node-3.

           Kemudian kita lihat node-node terdekat yang belum terhubung dengan node 1 dan 3, yaitu node 7, 6 dan 2. Yang terdekat dengan node 3 adalah node 7 dengan jarak 3 meter. Kemudian node 3 dan node 7 dapat dihubungkan.

             Node yang belum terhubung terdekat dengan node 1, 3 dan 7 adalah node 6 dengan panjang 2 meter.



           Node yang belum terhubung dan dekat dengan node 1,3,7 dan 6 adalah 5 dan 2. Node 5 dapat terhubung dengan node 6 dengan jarak 3 meter, sedangkan node 3 dapat dihubungkan dengan node-1 dengan jarak 3 meter.


              Sisa node yang belum terhubung adalah node 8, 4 dan 9. Node 4 dapat dihubungkan dengan node 5 dengan jarak 3 meter, dan untuk mencapai node 9 total jarak terdekat lebih pendek jika ditempuh dari node 8 ke 9 dari pada melalui node 4.

           Karena seluruh node telah terhubung atau telah terkait dalam satu jaringan, maka solusi di atas telah optimum. Jadi teknisi listrik dapat memulai merentangkan kabelnya dengan menghubungkan node 1 – 2, 1 – 3, 3 – 7, 6 – 7, 5 – 6, 4 – 5,6 – 8, 8 – 9

Panjang kabel yang dibutuhkan adalah : 21 meter