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

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