TUGAS MATEMATIKA DISKRIT TENTANG ALOGARITMA PIRM DAN KRUSKAL

1. Perhatikan gambar pohon (tree) di bawah ini!
Gambarlah 3 pohon (tree) yang masing-masing akarnya d,e,k!
2. Pada gambar soal no.1 di atas, apabila g sebagai akar pohonnya, tentukan:
a. Anak (child) dari b
b. Saudara kandung (sibling) dari k
c. Panjang lintasan (path) dari k ke j apabila k sebagai akar.
3. Gunakan alogaritma kruskal untuk mencari MST dari:

Adakah lintasan (sisi yang menghubungkan dua vektor) yang DITOLAK? Sebutkan! Mengapa DITOLAK?
4. Gunakan alogaritma pirm untuk menentukan MST dari:

5. A. Tentukan koefisien x^r pada: (1+x+x²+….)^r
    B. Tentukan koefisien x¹⁶ pada: (x²+x³+x⁴+…)⁵
Penyelesaian:
1.

2.

· G sebagai akar
a. Anak dari b adalah e dan f
b. Saudara kandung (sibling) dari k tidak ada
c. Panjang lintasan (path) dari k ke j jika k sebagai akar adalah 6
1.

Langkah	Sisi	Bobot	Hutan Merentang
0
1	(A,B)	9
2	(D,F)	14
3	(B,D)	16
4	(D,C)	18
5	(F,G)	20
6	(G,E)	23
7	(E,F)	26
8	(A,C)	27
9	(D,E)	28
10	(D,A)	29
11	(D,G)	31
12	(C,F)	32
13	(E,B)	37

v Lintasan yang ditolak

1.(B,D)	5.(D,A)
2.(E,F)	6.(D,G)
3.(A,C)	7.(C,F)
4.(D,E)	8.(E,B)

Karena Lintasannya menghubungkan dua vektor

2.

Langkah	Sisi	Bobot	Pohon Merentang
1	(E,F)	11
2	(F,D)	15
3	(D,C)	12
4	(D,B)	12
5	(C,A)	16
6	(A,H)	14
7	(H,G)	18

MST = 11 + 15 + 12 + 12 + 16 + 14 + 18 = 98
3. –

Bila ada kekeliruan jawaban mohon koreksinya, terima kasih
SEMOGA BERMANFAAT…!!!