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).
Rahmadya Trias Handayanto 