Pohon Perentangan minimal adalah sebuah jaringan yang menghubungkan semua node
Contoh
Jaringan
1
5
4
3
2
Contoh (lanjutan)
Jalur : yang menghubungkan node 1 dan 4 dihubungkan oleh busur (1,3),(3,2),(2,4)
Loop : (2,3)→(3,4) →(4,2)
Pohon Pohon perentangan
1
3
4
2
1
3
5
4
2
Contoh kasus
Seorang pengusaha yang bergerak dibidang pemasangan kabel pada suatu daerah tertentu , memperoleh pesanan untuk memasang kabel pada enam gardu listrik yang mewakili enam kota, mengingat akhir akhir ini semua biaya peralatan naik cukup meningkat , maka dia berusaha agar pemasangan kabel tersebut ditekan dengan biaya semurah mungkin , dengan cara pemasangan kabel cukup satu jalur saja tanpa ada tumpah tindih antara satu kabel dengan kabel lain tetapi seluruh kota terhubung . jika rancangan tersebut dapat dilihat pada gambar berikut lengkap dengan kebutuhan kabel yang diperlukan ( km).Tentukanlah berapa total biaya yang dibutuhkan jika 1 km kabel adalah Rp 1000.000,-dibutuhkan menghubungkan keenam kota tersebut
Gambar rancangan
1
2
4
3
6
5
1
3km
4
6km
9km
7
5
5
10
8
3
Algorithma rute terdekat
Algorithma Asiklis (tanpa loop)
Uj = Jarak terdekat dari node 1 ke node 2
Dimana U1 = 0,Nilai Uj ,j = 1,2,3 …..n dihitung secara rekursif dengan rumus berikut: