SPANING TREE

1. Cara membuat minimum spanning tree pada jaringan diatas :

















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.

2. Menghitung total cost diatas dengan cara menambahkan nilai semua cost dengan rumus:

Σ Cost = cost1 + cost2 + cost3 + cost4 + cost5
= 2 + 4 + 4 + 5 +5
= 20