Matematika Diskrit: Juli 2020

Multiple Choice

Graf tak berarah terhubung yang tidak mengandung sirkuit disebut...
a. Pohon
b. Binary
c. Akar
d. Level
e. Anak
Sisi pada pohon rentang disebut dengan...
a. Tali hubung
b. Cabang
c. akar
d. Rank
e. Upapohon
Metode yang digunakan untuk menyelesaikan pohon rentang minimum adalah...
a. Algoritma Prim
b. Algoritma Kruskal
c. Traveling Salesman
d. a dan c benar
e. a dan b benar
Di bawah ini yang bukan terminologi pohon adalah...
a. Anak
b. Lintasan
c. Sirkuit
d. Derajat
e. Daun
Pohon biner dengan daun berupa operand dan simpul dalam berupa operator disebut dengan pohon...
a. Keputusan
b. Huffman
c. Prefiks
d. Ekspresi
e. Pencarian biner

Essay

Cari Bobot Pohon rentang minimum dari graf dibawah ini dengan :
a. Algoritma Prim
b. Algoritma Kruskal

Jawab :

a. Algoritma Prim

Maka Bobotnya = 5 + 10 + 15 + 20 + 25 + 30 + 35 = 140

b. Algoritma Kruskal

Sisi-sisi diurut menaik :

Sisi (1,2) (2,3) (2,6) (3,5) (5,7) (4,7) (4,8) (5,8) (3,4) (4,5) (6,7) (1,4) (2,5) (5,6) (7,8 (1,7)
Bobot 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80

Maka Bobotnya = 5 + 10 + 15 + 20 + 25 + 30 + 35 = 140
Terminologi Pohon
Graf :

a. Anak dan Orang tua
Contoh :
- Simpul B,C,dan D merupakan anak dari simpul A
- Simpul E merupakan anak dari simpul B
- Simpul F dan G merupakan anak dari simpul C
- Simpul H,I,dan J merupakan anak dari simpul D
- Simpul E merupakan orang tua dari simpul K dan L
- Simpul Q merupakan orang tua dari simpul R dan S

b. Lintasan (Path)
Contoh :
- Lintasan dari simpul A ke K adalah A,B,E,K dengan panjang lintasan ada 3
- Lintasan dari simpul A ke S adalah A,D,J,Q,S dengan panjang lintasan ada 4

c. Keturunan (Descendant) dan Leluhur (Ancestor)
Contoh :
- Simpul B adalah leluhur dari simpul K
- Simpul K adalah keturunan dari simpul B
- Simpul J adalah leluhur dari simpul S
- Simpul S adalah keturunan dari simpul J

d. Saudara kandung (Sibling)
Contoh :
- Simpul B,C,dan D adalah saudara kandung dengan orang tua yang sama yaitu simpul A
- Simpul H,I,dan J adalah saudara kandung dengan orang tua yang sama yaitu simpul D
- Simpul M dan N adalah saudara kandung dengan orang tua yang sama yaitu simpul F
- Simpul R dan S adalah saudara kandung dengan orang tua yang sama yaitu simpul Q

e. Upapohon (Subtree)
Contoh :
- V' = {J,P,Q,R,S}
E' = {(J,P),(J,Q),(Q,R),(Q,S)}
dengan J adalah simpul akar

f. Derajat (Degree)
Contoh :
- Derajat simpul A : 3
- Derajat simpul B : 1
- Derajat simpul D : 3
- Derajat simpul F : 2

g. Daun (Leaf)
Contoh :
- Simpul K,L,M,N,O,P,R,S merupakan daun (leaf)

h. Simpul Dalam (Internal nodes)
Contoh :
- Simpul A,B,C,D,E,F,G,J,Q merupakan simpul dalam (internal nodes)

i. Aras (Level) atau tingkat

j. Tinggi (Height) atau Kedalaman (Depth)
Contoh :
- Tinggi atau kedalaman pada pohon di atas adalah 4

h. Pohon Ekspresi (expression tree)
Contoh :
- Ekspresi dari ((a + b) * (c - d)) / (e * (f + g)) adalah

- Mencari nilai evaluasi dari pohon ekspresi

i. Pohon keputusan (decision tree)
Contoh :

j. Kode Huffman (Huffman code)
Contoh :
- Buat Kode Huffman dari "DISKRIT"
memori yang dipakai sebesar 7 x 8 = 56 bit (7 byte)

Huruf Frekuensi
D 1
S 1
K 1
R 1
T 1
I 2

Tabel dari kode Huffman :

Huruf Kode Huffman
D 110
S 111
K 00
R 010
T 011
I 10

Sehingga kode Huffman untuk "DISKRIT" adalah 110101110001010011
Dengan kode Huffman , memori yang dipakai sebesar 18 bit

i. Kode Prefiks (Prefix code)
Contoh :
-

Kode Prefiks : / * + a b - c d * e + f g