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