Redirected
2,368 views
1 votes
1 votes

5 Answers

Best answer
6 votes
6 votes

Adjacency matrix of given graph is

$A= \begin{bmatrix}
 0 & 0 & 1 & 1 \\
 0 & 0 & 1 & 1 \\
 1 & 1 & 0 & 0\\                                                                                                                                                                      1 & 1 & 0 & 0
\end{bmatrix}
$

This matrix above represents "1" if there is any DIRECT path from $x$ to $y$, i.e path of length 1.

If I multiply above matrix with itself i.e. raising power with 2, then entries $A^2$ represents Number of paths of length 2.

$
A^2 = \begin{bmatrix}
2 & 2 & 0 & 0 \\
2 & 2 & 0 & 0 \\
0 & 0 & 2 & 2\\
0 & 0 & 2 & 2
\end{bmatrix}
$

here $A^2(1,2)$ is 2, this means there are 2 paths of length 2 from vertex 1 to vertex 2.

$A^2(1,1)$ is 2, this means there are 2 paths of length 2 from vertex 1 to vertex 1. (that is 1 to 3 and 3 to 1, And 1 to 4 and 4 to 1)

 $
\\
A^3= \begin{bmatrix}
0 & 0 & 4 & 4 \\
0 & 0 & 4 & 4 \\
4 & 4 & 0 & 0\\
4 & 4 & 0 & 0
\end{bmatrix}
$

entry (1,4 ) in $A^3$ is 4, therefore Total number of paths (of length 3 ) from 1 to 4 is = 4.

Path 1: 1-3-2-4
Path 2: 1-3-1-4
Path 3: 1-4-2-4
Path 4: 1-4-1-4

Entry (i,j) in $A^n$ represents, number of paths of length n from i to j.

This is standard method given in kenneth rosen page 567, 7th Edition.

One more reference-

https://www.cs.sfu.ca/~ggbaker/zju/math/paths.html

How to do Matrix Multiplication https://www.mathsisfun.com/algebra/matrix-multiplying.html

For matrix multiplication , we use Dot products ,  it is like 1st Matrix first Row have ( 1,2,3)  and 2nd Matrix 1st column have ( 7,9,11) then Dot Product is : 

(1, 2, 3) • (7, 9, 11) = 1×7 + 2×9 + 3×11 = 58 [ 58 will go in 1st Row, 1 st column in Result Matrix  ] . Now , second result will come 1st row and 2nd column in Result Matrix .

edited by
5 votes
5 votes
The total number of path is 4.

Path 1: 1-3-2-4
Path 2: 1-3-1-4
Path 3: 1-4-2-4
Path 4: 1-4-1-4
2 votes
2 votes

For the path to be the length of 3, there should be 4 vertices.

And from vertex 1 to vertex 4 there is only one path of length 3 that is 1-3-2-4 

So C should be the answer.

1 votes
1 votes
"A path is a trail in which all vertices (except possibly the first and last) are distinct."
souce : wiki
so only possible path is 1-3-2-4
Answer:

Related questions

0 votes
0 votes
2 answers
1
Gate Ranker18 asked Apr 2, 2017
540 views
0 votes
0 votes
1 answer
2
Gate Ranker18 asked Apr 2, 2017
474 views
0 votes
0 votes
1 answer
3
Gate Ranker18 asked Apr 2, 2017
311 views
In general , root is at level 0 like if we have level 2 then no of leaf nodes in a binary tree is at most 22
0 votes
0 votes
1 answer
4
Gate Ranker18 asked Apr 2, 2017
546 views