UAS Sem. Ganjil 2014/2015 MUG2A3 (Matematika Diskrit) Senin, 16 Desember 2014 (120 menit) RPS, RTA, EFS, HIF, EFY, IAR, DWJ, NIB, SUI, LDN 1. [nilai 25] Berikut ini merupakan sebuah graf yang menunjukkan peta rencana penggelaran kabel optik di pulau Jawa. Terdapat 8 buah simpul yang menunjukkan kota-kota yang akan dijadikan server utama yaitu A sampai dengan H, sedangkan sisi menunjukkan panjang kabel optik yang akan digelar dalam satuan km (kilometer). Tentukan lintasan terpendek dari kota A ke semua kota yang lainnya agar setidaknya dari A bisa terhubung ke kota-kota lainnya. 5
B 10
20
11
32
10 8
C 10
E
22
F
13 8
40
H 7
12
6
17
10
D
11
G
Jawab: Menggunakan algoritma Djikstra, tanda centang (√) adalah lintasan yang dipilih. A-B : direct = 10 √ A-C : direct = 20 √ A-B-C = 10+11 = 21 x A-D-C = 17+10 = 27 x A-D : direct = 17 √ A-E : A-B-E = 10+5 = 15 √ A-C-E = 20+8 = 28 x
A-F : A-B-F = 10+22 = 32 x A-C-F = 20+13 = 33 x A-D-F = 17+12 = 29 √ A-G : A-C-G = 20+8 = 28 √ A-D-G = 17+11 = 28 √ A-H = A-B-H = 10+40 = 50 x A-E-H = 15+32 = 47 x A-F-H = 29+7 = 36 √ A-G-H = 28+10 = 38 x
2. Dalam suatu kepanitiaan dibentuk 7 kelompok yang setiap seminggu sekali selalu mengadakan rapat. 7 kelompok tersebut dimana • Tidak ada anggota kelompok 1 yang menjadi anggota kelompok 5 dan 7 • Tidak ada anggota kelompok 2 yang menjadi anggota kelompok 4 dan 7 • Tidak ada anggota kelompok 3 yang menjadi anggota kelompok 5 • Tidak ada anggota kelompok 4 yang menjadi anggota kelompok 2 dan 6 • Tidak ada anggota kelompok 5 yang menjadi anggota kelompok 1 dan 3 • Tidak ada anggota kelompok 6 yang menjadi anggota kelompok 4 • Tidak ada anggota kelompok 7 yang menjadi anggota kelompok 1 dan 2 • Selain ketujuh kondisi di atas, ada anggota suatu kelompok yang menjadi anggota di kelompok lain. a) [nilai 5] Sajikan persoalan tersebut dalam graf dan jelaskan sisi menyatakan apa, simpul menyatakan apa! b) [nilai 10] Gunakan algoritma WELCH-POWELL untuk mewarnai graf yang terbentuk. c) [nilai 10] Buatlah jadwal rapat organisasi tersebut agar tidak ada 2 orang yang mempunyai jadwal pada waktu yang sama (Hari kerja Senin s/d Jum'at) Jawab: Jawaban ada dua pendekatan a. simpul/vertex menyatakan kelompok, sisi/edge a. simpul/vertex menyatakan kelompok, sisi/edge menyatakan adanya irisan anggota. menyatakan tidak adanya irisan anggota.
2
3
7
2
1
7
4
6
3
1
4
6
5
5
b. d1=4 d2=4 d3=5 d4=4 d5=4 d6=5 d7=4
b. d1=2 d2=2 d3=1 d4=2 d5=2 d6=1 d7=2
Algoritma Welch-Powell, diurutkan secara desc menurut derajatnya. Dua vertex dapat mempunyai warna yang sama jika tidak ada irisan anggota (tidak terhubung).
Algoritma Welch-Powell, diurutkan secara desc menurut derajatnya. Dua vertex dapat mempunyai warna yang sama jika tidak ada irisan anggota (terhubung).
Vertex v
3
6
1
2
4
5
7
Vertex v
1
2
4
5
7
3
6
Derajat d
5
5
4
4
4
4
4
Derajat d
2
2
2
2
2
1
1
Colour
a
b
c
d
b
a
c
Colour
a
b
b
a
c
d
e
c. Senin: Selasa: Rabu: Kamis:
Kelompok 3 dan 5 Kelompok 6 dan 4 Kelompok 1 dan 7 Kelompok 2
c. Senin: Kelompok 1 dan 5 Selasa: Kelompok 2 dan 4 Rabu: Kelompok 7 Kamis: Kelompok 3 Jum'at: Kelompok 6
3. Perusahaan pengembang perumahan ingin membuat jaringan kabel fiber optik untuk memberikan layanan internet bagi para penghuninya. Jika data jarak (dalam puluhan meter) tiap gedung digambarkan pada matriks adjacency sebagai berikut: a
b
c
d
e
f
g
h
i
j
k
a
0
2
0
3
2
3
0
0
0
0
0
b
2
0
4
0
0
1
3
0
0
0
0
c
0
4
0
0
0
0
0
3
0
0
0
d
3
0
0
0
6
0
0
0
3
0
0
e
2
0
0
6
0
2
0
0
2
0
0
f
3
1
0
0
2
0
0
0
1
1
0
g
0
3
0
0
0
0
0
4
0
3
0
h
0
0
3
0
0
0
4
0
0
0
5
i
0
0
0
3
2
1
0
0
0
5
0
j
0
0
0
0
0
1
3
0
5
0
4
k
0
0
0
0
0
0
0
5
0
4
0
a) [nilai 10] Sajikan persoalan tersebut dalam graf! b) [nilai 10] Rencanakan (gambarkan) jaringan yang akan dibuat agar kabel yang diperlukan sependek mungkin dan semua gedung terhubung! (Gunakan algoritma Kruskal). c) [nilai 5] Jika harga kabel adalah Rp. 5000,-/m berapa biaya yang diperlukan untuk membangun jaringan tersebut. Jawab: a. 50
k
40
j 50
10 20
i
20
g
f
10
e 30
20 60
30
40
30 10
h
30
b 20
a 30
d
c
30 40
b. Algoritma Kruskal: Semua sisi diurutkan secara ascending, dipilih dari sisi terkecil yang tidak membentuk sirkuit. Tanda centang (√) menunjukkan sisi tersebut dipilih, tanda silang (x) menunjukkan sisi tersebut tidak dipilih. b-f = 10 √ f-i = 10 √ f-j = 10 √ a-b = 20 √ a-e =20 √ e-f = 20 x (sirkuit abfea) e-i = 20 x (sirkuit abfiea)
a-d = 30 √ a-f = 30 x (sirkuit abfa) b-g = 30 √ c-h = 30 √ d-i = 30 x (sirkuit abfida) g-j = 30 x (sirkuit bfjgb)
h
k
40
30
j
g
10
f 10
10
i
b-c = 40 √ g-h = 40 x (sirkuit bchgb) j-k = 40 √ h-k = 50 x (sirkuit bchkjfb) i-j = 50 x (sirkuit fijf) d-e = 60 x (sirkuit adea)
e
b 20
c
30 40
20
a 30
d c. Jumlah kabel yang dibutuhkan = 10+10+10+20+20+30+30+30+40+40 = 240m Biaya yang dibutuhkan = 240xRp5000 = Rp 1.200.000,-
4. BPS (Badan Pusat Statistik) mencatatkan data umur penduduk pada sensus nasional 2014 pada database komputer mereka dengan urutan sebagai berikut: 50,13,12,9,23,72,14,19,17,67,5,54,76 Untuk memudahkan pencarian data dibentuklah suatu metode pohon pencarian biner (binary search tree) pada database komputer tersebut. a) [nilai 10] Buatlah gambar pohon pencarian (search tree) yang terbentuk. b) [nilai 10] Tentukan hasil penelusuran preorder, inorder, dan postorder dari pohon jawaban a) tersebut. a. 50 13 23
12 9
72
14
67
54 19
5 17
b. pre-order = R-T1-T2 → 50-13-72
13 dipecah secara pre-order = R-T1-T2 → 50-13-12-23-72 12 dipecah secara pre-order = R-T1-T2 → 50-13-12-9-23-72 9 dipecah secara pre-order = R-T1-T2 → 50-13-12-9-5-23-72 23 dipecah secara pre-order = R-T1-T2 → 50-13-12-9-5-23-14-72 14 dipecah secara pre-order = R-T1-T2 → 50-13-12-9-5-23-14-19-72 19 dipecah secara pre-order = R-T1-T2 → 50-13-12-9-5-23-14-19-17-72 72 dipecah secara pre-order = R-T1-T2 → 50-13-12-9-5-23-14-19-17-72-67-76 67 dipecah secara pre-order = R-T1-T2 → 50-13-12-9-5-23-14-19-17-72-67-54-76 in-order = T1-R-T2 → 13-50-72 13 dipecah secara in-order = T1-R-T2 → 12-13-23-50-72 12 dipecah secara in-order = T1-R-T2 → 9-12-13-23-50-72 9 dipecah secara in-order = T1-R-T2 → 5-9-12-13-23-50-72 23 dipecah secara in-order = T1-R-T2 → 5-9-12-13-14-23-50-72 14 dipecah secara in-order = T1-R-T2 → 5-9-12-13-14-19-23-50-72 19 dipecah secara in-order = T1-R-T2 → 5-9-12-13-14-17-19-23-50-72 72 dipecah secara in-order = T1-R-T2 → 5-9-12-13-14-17-19-23-50-67-72-76 67 dipecah secara in-order = T1-R-T2 → 5-9-12-13-14-17-19-23-50-54-67-72-76 post-order = T1-T2-R → 13-72-50 13 dipecah secara post-order = T1-T2-R → 12-23-13-72-50 12 dipecah secara post-order = T1-T2-R → 9-12-23-13-72-50 9 dipecah secara pot-order = T1-T2-R → 5-9-12-23-13-72-50 23 dipecah secara post-order = T1-T2-R → 5-9-12-14-23-13-72-50 14 dipecah secara post-order = T1-T2-R → 5-9-12-19-14-23-13-72-50 19 dipecah secara post-order = T1-T2-R → 5-9-12-17-19-14-23-13-72-50 72 dipecah secara post-order = T1-T2-R → 5-9-12-17-19-14-23-13-67-76-72-50 67 dipecah secara post-order = T1-T2-R → 5-9-12-17-19-14-23-13-54-67-76-72-50
76
