JAWABAN TUGAS MATEMATIKA DISKRIT TGL29

Jawaban:

1. Permutasi adalah suatu susunan unsur-unsur berbeda dalam urutan tertentu. Pada permutasi urutan diperhatikan, sehingga AB ≠ BA.

2. Kombinasi adalah susunan unsur-unsur dengan tidak memperhatikan urutan. Pada kombinasi AB = BA.

3. Pohon adalah graf tak-berarah terhubung yang tidak mengandung sirkuit

4. A. P_(10,5) =

                   =

                   = 30240

   B. C_(15,12) = =

                      =

                      = 455

5. C_(24,19) x^24-19y¹⁹ =

                                     =

                                     =

                                     =

                                     = 42504

6. (x²+ x³+ x⁴+…)⁵ = x² + x³+ x⁴+ … + x¹⁶ + …

Maka koefisiennya x¹⁶ adalah x¹⁶ = x¹⁶

Koefisien x¹⁶ pada penjabaran (x²+ x³+ x⁴+…)⁵ adalah

7. Langkah-Langkah:

· Ambil sisi dari graf yang berbobot minimum, masukan ke dalam T.

· Pilih sisi e yang mempunyai bobot minimum dan bersisian dengan simpul di T, tetapi e tidak membentuk sirkuit di T. masukan e ke dalam T

· Ulangi 2 sebanyak n – 2 kali.

Yang lebih rincinya:

a) Kruskal + menjaga graf tetap terhubung

8. Langkah-Langkah:

· Langkah 0: sisi-sisi dari graf sudah diurut menaik berdasarkan bobotnya – dari bobot kecil ke bobot besar)

· Langkah 1: T masih kosong

· Langkah 2: pilih sisi (u, v) dengan bobot minimum yang tidak membentuk sirkuit di T. Tambahkan (u, v) ke dalam T.

· Langkah 3: ulangi langkah 2 sebanyak n – 1 kali.

Yang lebih rincinya:

a) Urutkan ruas dari G menurut bobotnya, dari kecil ke besar.

b) Lakukan penambahan ruas berdasarkan urutan yang sudah dilakukan, dengan ketentuan bahwa penambahan ruas tersebut tidak menyebabkan adanya sirkuit.

9.

Langkah	Sisi	Bobot	Pohon Merentang
1	(A,B)	9
2	(B,D)	16
3	(D,F)	14
4	(D,C)	18
5	(F,G)	20
6	(G,E)	23

Pohon Merentang Minimum : 9 + 16 + 14 + 18 + 20 + 23 = 100

10.

Sisi	(F,E)	(D,C)	(D,B)	(A,H)	(D,F)	(A,C)	(C,B)	(B,E)	(H,G)	(C,G)	(G,F)	(A,B)
Bobot	11	12	12	14	15	16	17	18	18	21	24	25

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

Pohon Merentang Minimum : 11 + 12 + 12 + 14 + 15 + 16 + 18 = 98