TUGAS MATEMATIKA DISKRIT TENTANG POHON

Soal

1. Perhatikan gambar di bawah ini. Gambarlah tiga buah pohon (Tree) yang masing-masing akarnya b, d dan e.

2. Pada gambar soal No.1 di atas apabila g sebagai akar pohonnya,tentukan :

a. Anak (Child) dari b

b. Saudara Kandung (Sibling) dari e

c. Panjang Lintasan (Path) dari g ke a

d. Simpul mana yang memiliki derajat (Degree) 0 dan 3

e. Himpunan simpul dan himpunan sisi dari Upapohon (Subtree) dimana d sebagai akarnya.

3. Kepala Desa Pasirwangi di Garut akan membangun jalan desa agar ke 8 tempat yaitu a,b,c,d,e,f,g dan h seperti gambar di bawah dapat dilalui motor. Salah seorang mahasiswa Jurusan Matematika STKIP Garut yang sedang KKNM (Kuliah Kerja Nyata Mahasiswa) di desa tsb memberikan pendapat kepada Kepala Desa untuk pembangunan jalan tsb dengan biaya yang minimum. Untuk itu mahasiswa tsb membuat pohon merentang minimum (minimun spanning tree) sebagai solusinya.

Misal dari tempat a ke b memerlukan biaya Rp. 5 juta, dari a ke c Rp. 4 juta dan seterusnya. Berapa biaya minimum yang diperlukan dan gambarlah langkah-langkahnya dengan menggunakan Algoritma Prim.

4. Dari 8 batang logam yang berwarna kuning emas yaitu A,B,C,D,E,F,G dan H dimana diperkirakan hanya terdapat 1 (satu) diantara 8 batang tsb yang merupakan batang emas asli sebagai logam mulia yang memiliki nilai jual tinggi. Untuk mengetahui asli atau palsunya batang emas tsb digunakan timbangan neraca yang sangat teliti sebagai salah satu alatnya. Batang emas asli mungkin lebih berat atau lebih ringan daripada batang emas palsu.

Buatlah Pohon Keputusan untuk menentukan batang emas asli dengan cara menimbang paling banyak 3 (tiga) kali.

Penyelesaian :

1.

2. A. Anak (child) dari b yaitu a dan c

B. Saudara kandung (sibling) dari e yaitu b dan h

C. Panjang lintasan (path) dari g ke a yaitu 3

D. Simpul yang memiliki derajat (degree) 0 yaitu a,c,f,g,h dan sampul yang memiliki derajat (degree) 3 yaitu d

E. Himpunan simpul dan himpunan sisi dari upapohon (subtree) dimana d sebagai akar yaitu V’={d,e,g,h,f} dn E’={(d,e),(d,g),(d,h),(e,f)}.

3.

Langkah	Sisi	Bobot	Pohon merintang
1	(f,g)	2
2	(f,e)	3
3	(g,h)	4
4	(e,a)	4
5	(a,c)	4
6	(c,b)	3
7	(a,d)	4

4. Misalkan 8 batang logam berwarna kuning emas dinamai a,b,c,d,e,f,g dan h. pohon keputusan untuk mencari batang emas asli ditunukkan di bawah ini.

Daun menyatakan batang emas asli

Jika ada kekeliruan mohon koreksiannya, Semoga Bermanfaat…!!