masalah pohon rentang

MASALAH POHON RENTANG MINIMUM

NI’MATULLAH (1000131)

LIS ENDAH P. (1002379)

FIQA ADHA D. (1003117)

ELTINE REGIENA (1006658)

DEWI FENNY (1002477)

ISHMA FADLINA U (1005324)

IRFAN PRADIPTA (1005294)

• Masalah 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

lintasan terpendek, perbedaannya masalah pohon rentang

minimum merupakan pengadaan busur-busur dalam jaringan

kerja, bukannya penentuan lintasan dalam jaringan kerja.

JARINGAN POHON RENTANG MINIMUM

FIQA ADHA -1003117

• Gambar diatas bukan pohon rentang karena simpul O, A, B

dan C tidak terhubungkan dengan simpul D, E dan T.

• Terdiri atas dua buah pohon.


O

A

B

C

D

E

T

FIQA ADHA -1003117

Gambar ini membuat jaringan kerja tersebut terhubungkan, namun ini

bukan merupakan suatu pohon karena terdapat dua daur (O-A-B-C-O dan

D-E-T).

Pada Subbab pengantar (10.2) dijelaskan bahwa jaringan kerja harus

memiliki tepat buah busur tak berarah, tanpa adanya daur,

untuk dapat disebut sebagai pohon rentang.


O

A

B

C

D

E

T

6)1( n

DEWI FENNY -1002477

O

A

B

C

D

E

T


Gambar diatas merupakan penyelesaian yang layak untuk

masalah pohon rentang minimum.

Akan kita ketahui bahwa pohon rentang ini tidak optimal.

DEWI FENNY -1002477

Algoritma untuk Masalah Pohon Penjangkau Minimum

1. Pilih secara sembarang sebuah simpul dalam jaringan.

2. Hubungkan simpul tersebut dengan simpul terdekat

yang dapat meminimalkan total jarak.

3. Perhatikan semua simpul apakah terdapat simpul yang

belum terhubung, temukan dan hubungkan simpul

terdekat yang belum terhubung.

4. Ulangi langkah ketiga sampai seluruh simpul dapat

terhubung.


IRFAN P -1005294

A

B

C

D

E F

13

4

5

5

3

Karena jaraknya sama, maka pilih salah satu saja.misalnya ...

Atau …

Pohon rentang minimum

IRFAN P -1005294

Kasus I

• Pengelola Taman Seervada ingin menentukan

pada ruas jalan mana, kabel telepon harus

dipasang untuk menghubungkan seluruh pos

dengan panjang kabel sependek mungkin.

dengan data sebagai berikut:


ELTINE REGIENA -1006658

2 27

4

5 4

1

4

3 1

5

7O

A

B

C

D

E

2



Taman Servada

BD

EC

2

5

27

4

5

71

41

4

3

O

T

A

Pohon Penjangkau Minimum


Taman Seervada

BD

EC

2

5

27

4

5

71

41

4

3

O

T

A

Pohon Penjangkau Minimum

ISHMA FADLINA U -1005324

Soal 1Midwest TV Cable Company sedang berada dalam proses perencanaan

penyediaan jaringan jasa TV kabel ke lima wilayah perumahan yang baru.

Jaringan sistem kabel tersebut diringkaskan dalam Gambar berikut. Angka-

angka yang berkaitan dengan setiap cabang mewakili jumlah mil kabel yang

diperlukan untuk menghubungkan setiap dua lokasi. Node 1 mewakili stasiun

relayTV kabel dan node lainnya (2 sampai 6) mewakili lima wilayah

pengembangan. Tidak adanya sebuah cabang diantara dua node menyiratkan

biaya yang sangat tinggi atau ketidakmungkinan fisik untuk menghubungkan

kedua wilayah pengembangan yang bersangkutan. Yang diperlukan adalah

menentutakn hubungan-hubungan yang akan menghasilkan penggunaan

kabel minimum sambil menjamin bahwa semua wilayah dihubungkan (secara

langsung atau tidak langsung) ke stasiun TV kabel tersebut.

14

9

6

5

7

3 (mil)

10

58

3

A

B

D

C

E

F

NI’MATULLAH -1000131

14

9

6

5

7

3

10

58

3

A

B

D

C

F

E

NI’MATULLAH -1000131

Pohon rentang minimum= 1+3+4+5+3 = 16

Soal 2Sebuah Bank akan menghubungkan terminal komputer pada

setiap kantor cabang ke suatu komputer di kantor pusat

dengan menggunakan saluran telepon khusus dengan

peralatan telekomunikasi. Saluran telepon dari suatu kantor

cabang tidak harus dihubungkan secara langsung ke kantor

pusat. Hubungan ini bisa saja merupakan hubungan tak

langsung dengan menghubungkannya kepada kantor cabang

lain yang telah terhubungkan (secara langsung atau tidak)

kepada kantor pusat. Satu-satunya persyaratan adalah setiap

kantor cabang harus dihubungkan dengan rute yang sama

menuju kantor pusat.

Biaya untuk saluran telepon khusus ini berbanding lurus terhadap jarak yang harus

ditempuh. Tabel berikut memberikan jarak (dlm mil) antara pasangan kantor cabang.

Masalahnya adalah menentukan pasangan kantor mana yang harus dihubungkan

secara langsung oleh saluran telepon khusus dalam upaya menghubungkan setiap

cabang (secara langsung atau tidak) kepada kantor pusat dengan biaya total minimum.

Jelaskan bagaimana masalah ini sesuai dengan masalah pohon pejangkau minimum.

K.P.(A)

CB1(B)

CB2(C)

CB3(D)

CB4(E)

CB5(F)

Kantor Pusat (A) - 190 70 115 270 160

Cabang 1 (B) 190 - 100 240 215 50

Cabang 2 (C) 70 100 - 140 120 220

Cabang 3 (D) 115 240 140 - 175 80

Cabang 4 (E) 270 215 120 175 - 310

Cabang 5 (F) 160 50 220 80 310 -

A

B

D

C E

115

50

100

120

F

LIS ENDAH P. -1002379

A

D

C E

115

50

100

120

FB

LIS ENDAH P. -1002379

Pohon rentang minimum= 50+100+80+120+70 = 420

masalah pohon rentang

Documents