Given an adjacency matrix A = [ [0, 1, 1], [1, 0, 1], [1, 1, 0] ], The total no. of ways in which every vertex can walk to itself using 2 edges is ________

Category: QuestionsGiven an adjacency matrix A = [ [0, 1, 1], [1, 0, 1], [1, 1, 0] ], The total no. of ways in which every vertex can walk to itself using 2 edges is ________
Editor">Editor Staff asked 4 weeks ago

Given an adjacency matrix A = [ [0, 1, 1], [1, 0, 1], [1, 1, 0] ], The total no. of ways in which every vertex can walk to itself using 2 edges is ________
 
(a) 2
 
(b) 4
 
(c) 6
 
(d) 8
 
I need to ask this question from Adjacency Matrix topic in division Graph of Data Structures & Algorithms I
 
This question was addressed to me in an international level competition.

1 Answers
Editor">Editor Staff answered 4 weeks ago

Right choice is (c) 6
 
Easy explanation – A^2 = [ [2, 1, 1], [1, 2, 1], [1, 1, 2] ], all the 3 vertices can reach to themselves in 2 ways, hence a total of 3*2, 6 ways.