3.15 Adjacency matrices and walks Quiz

1. Which describes the adjacency matrix of a simple undirected graph?

• A. Symmetric, with zeros on the leading diagonal
• B. Symmetric, with ones on the leading diagonal
• C. Not symmetric, with zeros on the diagonal
• D. Each column sums to 1

2. The $(2,4)$ entry of $\mathbf{A}^3$ is 5. What does this mean?

• A. There are 5 edges between vertices 2 and 4.
• B. There are 5 vertices adjacent to vertex 2.
• C. There are 5 walks of length 3 from vertex 2 to vertex 4.
• D. There are 5 walks of any length from vertex 2 to vertex 4.

3. A directed graph has adjacency matrix $\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}$. How many walks of length 2 go from vertex 2 to vertex 2?

• A. $0$
• B. $1$
• C. $3$
• D. $2$

4. In a transition matrix with the probabilities in columns, what does each column add up to?

• A. $0$
• B. $1$
• C. $\frac1n$
• D. The number of links

5. Which matrix gives the number of walks of length at most 3 between two vertices?

• A. $\mathbf{A}^3$
• B. $3\mathbf{A}$
• C. $\mathbf{A}+\mathbf{A}^2+\mathbf{A}^3$
• D. $\mathbf{A}^3+\mathbf{I}$