Soal dan Pembahasan Pohon

Soal Latihan Matematika Diskrit
Kelas A-D Tgl 2 Mei 2015

KELOMPOK 1

Ayunita A W  13512023

Haryati Nurarapah 13512028

Intan Pandini 12512047

M. Rahmi N  13512045

Mutia S A 13512042

Ratna Sumyati 13512039

Visny Audria 13512048

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.   

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

SEMOGA BERMANFAAT