Matematika Diskrit

5.17          Graf dalam gambar 5P.5 menunjukkan saluran-saluran komunikasi dan tertahannya waktu komunikasi di dalam saluran di antara delapan pusat komunikasi. Pusat komunikasi dipresentasikan oleh verteks, saluran dipresentasikan oleh rusuk, dan tertahannya waktu komunikasi ( dalam menit ) dalam setiap saluran dipresentasikan oleh pembobot rusuk bersangkutan. Misalkan bahwa pada jam 15.00, pusat komunikasi a memancarkan ke semua salurannya berita bahwa seseorang telah menemukan cara untuk membuat perangkap tikus yang lebih baik. Pusat-pusat komunikasi lainnya segera menyebarluaskan berita ini ke semua salurannya begitu mereka menerimanya. Untuk pusat-pusat komunikasi b, c, d, e, f, g, dan h, tentukan kapan pertama kali mereka menerima berita ini ?

 

                                                Gambar 5P.5

Jawab :

 

Lintasannya adalah a ke b  = 3

Jadi : Pusat komunikasi b menerima berita pertama kali pada pukul 15.03

 

Lintasannya adalah a,b,c  = 3 + 1 = 4

Jadi : Pusat komunikasi c menerima berita pertama kali pada pukul 15.04

 

Lintasannya adalah a,b,f,d  = 3 + 1 + 1   = 5

Jadi : Pusat komunikasi d menerima berita pertama kali pada pukul 15.05

 

Lintasannya adalah a,b,f,e  = 3 + 1 +  2  = 6

Jadi : Pusat komunikasi e menerima berita pertama kali pada pukul 15.06

 

Lintasannya adalah a,b,f  = 3 + 1 = 4

Jadi : Pusat komunikasi f menerima berita pertama kali pada pukul 15.04

 

Lintasannya adalah a,b,f,d,g  = 3 + 1 + 1 + 2  = 7

Jadi : Pusat komunikasi g menerima berita pertama kali pada pukul 15.07   

 

Lintasannya adalah a,b,f,g ,h  = 3 + 1 + 4 + 1  = 9

Jadi : Pusat komunikasi h menerima berita pertama kali pada pukul 15.09

5.18         

10

Gunakan algoritma yang diberikan di dalam Pasal 5.5 untuk menentukan suatu lintasan terpendek antara a dan z pada graf dalam gambar 5P.6, jika bilangan pada setiap rusuk menyatakan jarak antara kedua verteks bersangkutan.

 

Jawab :

 

Panjang lintasan dari a sampai z adalah 1 + 10 + 5 = 16

 

Panjang lintasan dari a sampai z adalah 10 + 4 + 2 = 16

		10

 

Panjang lintasan dari a sampai z adalah 6 + 3 + 8 = 17

 

Panjang lintasan dari a sampai z adalah 3 + 8 + 5 = 16

 

Panjang lintasan dari a sampai z adalah 1 + 10 + 1 + 2 + 2  = 16

 

5.19          G

5.20          G

5.21          G

5.22          G

5.23          G