Download - Minimum Spanning Tree Problem
MINIMUM SPANNING TREE PROBLEMRiset OperasiProgram Studi StatistikaUniversitas Brawijaya
Definisi• Definisi Spanning tree : Untuk suatu jaringan dengan n node, spanning tree adalah sekumpulan dari n-1 arc yang menghubungkan semua node dalam jaringan dan tidak mengandung loop• Definisi Minimum Spanning Tree:Minimum spanning tree adalah spanning tree dengan panjang minimum dalam suatu jaringan
Gambaran• 12
7 4
1
3
2Perhatikan Contoh jaringan di samping.Terdapat 3 spanning tree, yaitu:1. Arc (1,2) dan (2,3)2. Arc (1,2) dan (1,3)3. Arc (1,3) dan (2,3)Spanning tree ketiga adalah minimum spanning tree
4
Algoritma• Untuk menemukan spanning tree dapat digunakan
algoritma berikut:• Mulailah dengan memilih arc terkecil (terpendek) dan membuat
himpunan arc yang terhubungkan• Pada setiap iterasi tambahkan arc terkecil yang belum terpilih yang
memiliki koneksi dengan himpunan yang telah terhubungkan (connected set), tapi tidak menciptakan
• Algoritma selesai jika semua node telah terhubungkan dan terdapat n -1 arc yang masuk dalam himpunan arc yang terhubungkan(connected arc)
Contoh• Kota Vancouver berencana mengembangkan sistem
transportasi kereta api baru.
Sistem tersebut harus menghubungkan 8 pusat-pusat perumahan dan komersial.
Distrik Metropolitan Transit perlu memilih set garis yang akan menghubungkan semua pusat dengan total biaya minimum.
6
Pusat Perbelanjaan
Loop
2 6
4
7
8
Bagian Barat
Bagian Utara
Universitas
PusatBisnis
BagianTimur
Bagian Selatan
Pusat Kota
50
30
55
34
28
32
35
39
45
38
43
44
41
3736
40
Biaya Total = $236 juta
REPRESENTASIJARINGAN
5
LoopLoopLoopLoopLoopLo
op Loop Lo
op LoopLoop Loop LoopLoopLoop
Loop
1
3
33
2832
30
33
7
Pusat Perbelanjaan
4
7
8
Bagian Barat
Bagian Utara
Universitas
Pusat Bisnis
Bagian Timur
Bagian Selatan
Pusat Kota
50
30
55
34
28
32
35
39
45
38
43
44
41
3736
40
Biaya Total= $236 juta
OPTIMAL SOLUTIONNETWORKREPRESENTATION 53
33Loop
1
62