1. Sebuah pohon mempunyai 2n buah simpul berderajat 1, 3n buah simpul berderajat 2 dan n buah simpul berderajat 3. Tentukan banyaknya simpul dan sisi di dalam pohon tersebut !
Jawab:
Berdasarkan lemma jabat tangan :
jumlah semua simpul di dalam graf adalah 2 kali jumlah sisi di dalam graf tersebut
(2n x 1) + (3n x 2) + (n x 3) = 2 |E|
11n = 2 |E| …… (1)
Jumlah sisi pada sebuah pohon adalah jumlah simpul minus satu, sehingga :
|E| = (2n + 3n + 1) – 1 = 6n – 1 …… (2)
Persamaan (1) dan (2) menjadi :
11n = 2 (6n – 1)
11n = 12n – 2
n = 2
Jadi :
Jumlah simpul pada pohon 6n = 6 x 2 = 12 buah simpul
Jumlah sisi 6n – 1 = 11 buah sisi
2. Tentukan bobot minimum pohon dibawah dengan menggunakan algoritma Prim :
Tabel Pembentukan Pohon Merentang Minimum Dengan Menggunakan Algoritma Prim
Bobot pohon merentang minimum yang diperoleh dengan menggunakan algoritma Prim:
10 + 25 + 15 + 20 + 35 = 105
3. Selesaikan dan tentukan bobot minimum dengan menggunakan algoritma Kruskal :
Sisi-sisi graf diurut menaik berdasarkan bobotnya :
Tabel Pembentukan Pohon Merentang Minimum Dengan Menggunakan Algoritma Kruskal
Bobot pohon merentang minimum yang diperoleh dengan menggunakan algoritma Kruskal :
10 + 25 + 15 + 20 + 35 = 105
4. Kita akan menyambungkan 19 buah lampu pada satu stop kontak dengan menggunakan sejumlah kabel ekstensi yang masing-masing mempunyai 4 outlet.
Penyelesaian :
Diketahui : t = 19 à banyaknya simpul daun
m = 4 à pohon 4-ary
Karena penyambungan merupakan pohon 4-ary dengan stop kontak sebagai akar pohon, maka :
(m – 1) i = t – 1
(4 – 1) i = 19 -1
i = 6
Jadi dibutuhkan 6 buah kabel ekstensi
5. Diketahui 8 buah koin uang logam. Satu dari delapan koin ternyata palsu. Koin yang palsu mungkin lebih ringan atau lebih berat daripada koin yang palsu. Misalkan tersedia sebuah timbangan neraca yang sangat teliti. Buatlah pohon keputusan untuk mencari uang palsu dengan cara menimbang paling banyak hanya 3 kali saja!
Penyelesaian :
Misalkan 8 koin itu dinamai a,b,c,d,e,f,g,h. Daun menyatakan koin yang palsu. Pohon keputusan untuk mencari koin yang palsu ditunjukkan sbb :
