Graph Theory 2

Mat Diskrit, 29.10.2012, T. Komputer D3

Jika pada pertemuan yang lalu kita menggunakan graph berarah, sekarang kita coba graph yang tidak berarah. Dalam Matlab tidak jauh berbeda teknik memasukkan datanya. Tetap gunakan arah panah sebagai patokan.

Setelah memasukan matriks graphnya:

>> W=[.5 .4 .3 .4 .2 .1];

>> DG=sparse([2 1 4 4 3 5],[1 3 3 2 5 4],W)

>>view(biograph(DG,[],’ShowWeights’,’on’))

Tekan tombol Accept. Akan dihasilkan gambar graph sebagai berikut:

Sekarang mencari Matriks graph untuk mengetahui jalur terpendek:

>> graphallshortestpaths(DG)

 

ans =

 

0 1.1000 0.4000 0.7000 0.6000

0.5000 0 0.9000 1.2000 1.1000

1.2000 0.7000 0 0.3000 0.2000

0.9000 0.4000 0.3000 0 0.5000

1.0000 0.5000 0.4000 0.1000 0

Untuk yang tidak berarah:

>> UG = tril(DG + DG’)

Matriks jalur terpendeknya:

>> graphallshortestpaths(UG)

 

ans =

 

0 Inf Inf Inf Inf

0.5000 0 Inf Inf Inf

0.4000 Inf 0 Inf Inf

0.7000 0.4000 0.3000 0 Inf

0.6000 0.5000 0.2000 0.1000 0

Iklan

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout /  Ubah )

Foto Google+

You are commenting using your Google+ account. Logout /  Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout /  Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout /  Ubah )

Connecting to %s