Graph Theory

Discrete Mathematic, Lab of Software, 23.10.2012, Comp. Engineering D3

Graph theory is an old theory about connection between vertex and edge. It was found in eighteen century by Euler. The first case was about bridge called konisberg. So, as a exercise we try to solve the smallest path to problem below.

Open your Matlab application and try to input that problem into Matlab. In command window, firstly, we create Matrix of vertexes and edges.

  • W=[.5 .4 .3 .4 .2 .1];
  • >> DG=sparse([2 1 4 4 3 5],[1 3 3 2 5 4],W)
  • DG =
  • (2,1) 0.5000
  • (5,4) 0.1000
  • (4,2) 0.4000
  • (1,3) 0.4000
  • (4,3) 0.3000
  • (3,5) 0.2000
  • view(biograph(DG,[],’ShowWeights’,’on’))

Finaly, we get the shortest path for every node using function ‘graphallshortestpaths

>> 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

What is that matrix mean? The rows are represent nodes and the columns are another nodes. For example, the shortest path from node 2 to node 5 can be seen at that matrix are the number of row 2 column 5 is 1.1. You can count by your self that the node 2 to node 5 are across node 1 and 3 with 0.5, 0.4 and 0.2 = 1.1 which the same as element (2,5).

Tentang rahmadya

I'm a simple man .. Lahir di Sleman Yogyakarta, 7 Juni 1976 PENDIDIKAN: TK : - (tidak ada TK di tj Priok waktu itu) SDN : Papanggo, Jakarta 83 - 89 SMPN : 129, Jakarta 89 - 92 SMAN : 8, Yogyakarta 92 - 95 Univ. : Fak. Teknik UGM, Yogyakarta 95 - 2001 Pasca. : Tek. Informatika STMIK Nusa Mandiri, Jakarta 2008 - 2010 Doctoral : Information Management Asian Institute of Technology, Thailand 2013 - 2018 PEKERJAAN: Tek. Komputer AMIK BSI Jakarta : 2002 - 2005 IT Danamon Jakarta : 2005 - 2008 Tek. Informatika STMIK Nusa Mandiri Jakarta : 2005 - 2008 Univ. Darma Persada Jakarta: 2008 - 2013 Fakultas Teknik Universitas Islam "45" Bekasi : 2008 - Skrg ( Homebase) Univ. Bhayangkara Jakarta Raya: 2018 - Skrg Univ. Nusa Putra Sukabumi: 2018 - Skrg
Pos ini dipublikasikan di Matematika Diskrit, Matlab. Tandai permalink.

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.