Let A be the adjacency matrix of a graph G.
Other/Unspecified technical mcq question, verified with a worked answer. Free to practise - no sign-up.
Let $A$ be the adjacency matrix of a graph $G$. What is represented by the entry $A^k[i][j]$ in the matrix $A^k$?
Show answer & explanation
Answer: A. The number of paths/walks of length k from vertex i to vertex j
By algebraic graph theory, the (i, j)-th entry of the k-th power of an adjacency matrix A^k counts the exact number of walks of length k from vertex i to vertex j.
Step-by-step Derivation:
Step 1: For k = 1, A[i][j] indicates an edge (walk of length 1).
Step 2: By matrix multiplication, A^k[i][j] = sum over intermediate vertices of A^(k-1)[i][m] * A[m][j].
Step 3: By induction, this counts the number of distinct walks of length k between i and j.