GRAF [PDF]

Citation preview

1. Diketahui 8 buah koin logam. Satu dari delapan koin itu ternyata palsu. Koin yang palsu mungkin lebih ringan atau lebih berat daripada koin yang asli. Misalkan tersedia sebuah timbangan neraca yang sangat teliti. Buatlah pohon keputusan untuk mencari uang palsu dengan cara menimbang paling banyak hanya 3 kali saja. Jawab : 8 koin dimisalkan koin A, B, C, D, E, F, G DAN H



AB:CD AB=CD



AB:EF



AB:EF



AB=EF



AB=EF



A:G A=G H PALSU



A=G



A=G G PALSU



F PALSU



A:E



C:E



A:E



E PALSU



D PALSU



A=G C PALSU



B PALSU



A PALSU



2. Tentukan hasil kunjungan preorder, inorder, dam postorder pada pohon 4-ary berikut ini : a



c



b



e



n



f



g



h



o



Jawab : Lintasan :  Preorder : A, B, E, N, O, F, G, C, H, I, D, J, K, L, P, Q, M  Inorder : N, E, O, B, F, G, A, H, C, I, J, D, K, P, L, Q ,M  Postorder : N, O, E, F, G, B, H, I, C, J, K, P, Q, L, M, D, A



d



i



j



k



p



l



m



q



3. Gunakan pohon berakar untuk menggambarkan semua kemungkinan hasil dari pertandingan tenis antara dua orang pemain, Anton dan Budi, yang dalam hal ini pemenangnya adalah pemain yang pertama memenangkan dua set berturut-turut atau pemain yang pertama memenangkan total tiga set. Jawab : Dinyatakan dalam bentuk Graf



A



B B



A



B



A



A



A



B



B



A



B



A



B



A



B



A



B



Simpul menyatakan pemenang dalam satu set. Ada 10 lintasan yang menyatakan kemungkinan hasil pertandingan, yaitu : AA, ABAA, ABB, ABABA, ABABB, BAA, BABAA, BABAB, BABB, BB



4. Tentukan dan gambarkan pohon merentang minimum dari graf di bawah ini (tahapan pementukkannya tidak perlu ditulis)



Jawaban :



Pohon merentang minimum : 1 + 2 + 2 + 3 + 3 + 3 + 4 + 4 = 22