TUGAS 10 SOAL MATEMATIKA INFORMATIKA

MATEMATIKA INFORMATIKA

Contoh Soal Tree

Gambar 1

1. Dari gambar diatas yang merupakan tree adalah

Jawaban : G1 dan G2

Pembahasan  :

Yang merupakan tree adalah graf tak berarah terhubung yang tidak mengandung sirkuit. Sehingga pada gambar G1 dan G2 merupakan tree

Gambar G3 : mengandung sirkuit pada titik adf

Gambat G4 : merupakan forest karena msngandung 2 tree yang tidak saling terhubung

Gambar 2

2. Tingkatan (level) pada gambar diatas adalah

Jawaban : 4

Pembahasan :

a mempunyai level 0

b, c , d mempunyai level 1

e, f, g mempunyai level 2

h, i, j, k mempunyai level 3

l, m mempunyai level 4

Tingkatan (level) pada tree dapat dilihat padadaun yang paling bawah, sehingga tingkatan pada tree tersebut adalah 4

3. Panjang lintasan dari a ke j pada tree diatas (gambar 2) adalah ...

Jawaban : 3

Pembahasan :

Lintasan a ke j adalah ab, be, ej. Sehingga panjang lintasan a ke j adalah 3

4. Ruas pada tree diatas (gambar2) adalah ...

Jawaban : 12

Pembahasan :

Jika pohon mempunyai simpul sebanyak n, maka banyaknya ruas = (n-1).

Sehingga ruas = 13 - 1 = 12

5. Ketinggian pada Tree diatas (gambar 2)  adalah...

Jawaban : 5

Pembahasan :

Pohon/tree mempunyai ketinggian (kedalaman/height) yaitu = level tertinggi + 1

Ketinggian pohon = 4 + 1 = 5

6. Derajat maksimum pada tree diatas (gambar 2) adalah ...

Jawaban : 3

Pembahasan :

Derajat maksimum dari semua simpul merupakan derajat pohon itu sendiri.

Derajat sebuah simpul adalah jumlah upapohon (atau jumlah anak) pada simpul tersebut.

Derajat a adalah 3, derajat b adalah 2, derajat d adalah satu dan derajat c adalah 0.

Sehingga  pohon di atas berderajat 3.

Gambar 3

7. Bobot minimum tree pada gambar diatas adalah …

Jawaban : 145

Pembahasan:

Spanning Tree :

Spanning tree tersebut memiliki bobot : 5 + 10 + 15 + 20 + 25 + 30 + 40 = 145

8. Bobot minimum tree dibawah ini adalah …

Gambar 4

Jawab : 105

Pembahasan :

Spanning Tree :

Spanning tersebut memiliki bobot = 10 + 25 + 15 + 20 + 35 = 105

Gambar 5

9. PreOrder dari gambar diatas adalah ..

Jawaban : * + a / b c - d * e f

Pembahasan :

Traversal Pre-order, dilakukan berturut-turut :

·         Simpul / Node nya

·         Subtree sebelah kiri (Left)

·         Subtree sebelah kana (Right) 

Sehingga preorder nya adalah * + a / b c - d * e f

10. PostOrder dari gambar diatas (gambar 5) adalah …

Jawaban : a b c / + d e f * - *

Pembahasan :

Traversal Post-order, dilakukan berturut-turut :

·         Subtree sebelah kiri (Left)

·         Subtree sebelah kana (Right)

·         Simpul /Node nya 

Sehingga Post-order nya adalah a b c / + d e f * - *