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

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.