Soal

1. Buatlah graf dari peta kelompok, disertai label simpul pada kota/kabupaten secara terurut!

(label simpul dimulai , jika simpul melebihi maka ditambahkan mulai dan seterusnya, kemudian disertai keterangan label simpul setiap kota/kabupaten dan sisi terbentuk pada lintasan darat)

2. Berilah nilai bobot pada setiap sisi dengan range (21 s/d 100) dengan satuan KM!(nilai bobot antar kota/kabupaten tidak boleh sama)

3. Tentukan bilangan kromatik dari graf tersebut, disertai pewarnaan pada graf dan peta!

4. Tentukan shortest path menggunakan algoritma Dijkstra dari kota/kabupaten (pangkal pulau) ke kota/kabupaten (ujung pulau)!

Petunjuk :

a. Baca soal dan petunjuk dengan sebaik-baiknya

b. Setiap kelompok diberikan peta

c. Dikerjakan di office word dan setiap jawaban berbeda lembar kertas

d. Pengumpulan print out dan soft file (cover, soal dan jawaban)

e. Pengumpulan Senin 8 Januari 2018, pukul 09.40 s/d 10.20 di Lab Matematika dan sekaligus tanda tangan presensi.

1. Graf

2. Nilai Bobot

3. Bilangan Kromatik graf dan pewarnaan pada graf dan peta

Jumlah warna minimum yang dapat digunakan untuk mewarnai simpul (bilangan kromatik) adalah 4. Karena jika bilangan kromatiknya 3, maka akan terdapat warna simpul yang sama pada simpul bertetangga.

· Pewarnaan pada graf

· Pewarnaan pada peta

4. Shortest path menggunakan algoritma Dijkstra

Start simpul = E1

Stop simpul = L2

Simpul yang dipilih

Lintasan 1

Panjang Lintasan 1 (km)

Lintasan 2

Panjang Lintasan 2

Total Lintasan (km)

F1

E1

0

F1

26

26

G1

E1, F1

26

G1

27

53

H1

E1, F1, G1

53

H1

56

109

M1

E1, F1, G1, H1

109

M1

53

162

N1

E1, F1, G1, H1, M1

162

N1

49

211

O1

E1, F1, G1, H1, M1, N1

211

O1

48

259

Q1

E1, F1, G1, H1, M1, N1, O1

259

Q1

45

304

R1

E1, F1, G1, H1, M1, N1, O, Q1

304

R1

43

347

T1

E1, F1, G1, H1, M1, N1, O, Q1, R1

347

T1

40

387

W1

E1, F1, G1, H1, M1, N1, O, Q1, R1, T1

387

W1

61

448

V1

E1, F1, G1, H1, M1, N1, O, Q1, R1, T1, W1

448

V1

60

508

Z1

E1, F1, G1, H1, M1, N1, O, Q1, R1, T1, W1

448

Z1

62

510

A2

E1, F1, G1, H1, M1, N1, O, Q1, R1, T1, Z1

510

A2

78

588

C2

E1, F1, G1, H1, M1, N1, O, Q1, R1, T1, Z1,A2

588

C2

85

674

D2

E1, F1, G1, H1, M1, N1, O, Q1, R1, T1, Z1,A2, C2

674

D2

86

760

E2

E1, F1, G1, H1, M1, N1, O, Q1, R1, T1, Z1,A2, C2, D2

760

E2

75

845

F2

E1, F1, G1, H1, M1, N1, O, Q1, R1, T1, Z1,A2, C2, D2

760

F2

76

921

H2

E1, F1, G1, H1, M1, N1, O, Q1, R1, T1, Z1,A2, C2, D2, F2

921

H2

74

995

G2

E1, F1, G1, H1, M1, N1, O, Q1, R1, T1, Z1,A2, C2, D2, E2

845

G2

73

1068

H2

E1, F1, G1, H1, M1, N1, O, Q1, R1, T1, Z1,A2, C2, D2, E2, G2

1068

H2

72

1140

I2

E1, F1, G1, H1, M1, N1, O, Q1, R1, T1, Z1,A2, C2, D2, E2, G2

1068

I2

71

1139

I2

E1, F1, G1, H1, M1, N1, O, Q1, R1, T1, Z1,A2, C2, D2, E2, G2, H2

1140

I2

70

1210

J2

E1, F1, G1, H1, M1, N1, O, Q1, R1, T1, Z1,A2, C2, D2, E2, G2, I2,

1139

J2

67

1206

K2

E1, F1, G1, H1, M1, N1, O, Q1, R1, T1, Z1,A2, C2, D2, E2, G2, I2, J2,

1206

K2

66

1272

K2

E1, F1, G1, H1, M1, N1, O, Q1, R1, T1, Z1,A2, C2, D2, E2, G2, I2,

1139

K2

68

1207

N1

E1, F1, G1, H1

109

N1

55

164

O1

E1, F1, G1, H1, N1

164

O1

48

212

R1

E1, F1, G1, H1, N1, O1

212

R1

46

258

S1

E1, F1, G1, H1, N1, O1, R1

258

S1

43

301

Y1

E1, F1, G1, H1, N1, O1, R1, S1

301

Y1

77

378

C2

E1, F1, G1, H1, N1, O1, R1, S1, Y1

378

C2

83

461

D2

E1, F1, G1, H1, N1, O1, R1, S1, Y1, C2

461

D2

86

547

F2

E1, F1, G1, H1, N1, O1, R1, S1, Y1, C2, D2

547

F2

76

623

H2

E1, F1, G1, H1, N1, O1, R1, S1, Y1, C2, D2, F2

623

H2

74

697

K2

E1, F1, G1, H1, N1, O1, R1, S1, Y1, C2, D2, F2, H2

697

K2

69

766

L2

E1, F1, G1, H1, N1, O1, R1, S1, Y1, C2, D2, F2, H2, K2

766

L2

64

830

Jadi, lintasan terpendek dari E1 ke L2 adalah E1, F1, G1, H1, N1, O1, R1, S1, Y1, C2, D2, F2, H2, K2, dan L2 yaitu 830.