Questions: Graph Representation: Matrices and Lists

Question 1

A sparse graph has 1,000 vertices and 2,000 edges. Approximately how much memory does an adjacency matrix require compared to an adjacency list?

• A. About the same — both scale with edges
• B. The adjacency list uses more memory because it stores pointers
• C. The adjacency matrix uses about 333 times more memory
• D. The adjacency matrix is always preferred because it supports O(1) lookup

Answer: (C)

The adjacency matrix requires n² = 1,000,000 entries. The adjacency list requires O(|V| + |E|) = 1,000 + 2×2,000 ≈ 5,000 entries (each edge appears in two lists for an undirected graph). That is roughly 1,000,000 / 5,000 = 200× more memory for the matrix. For sparse graphs, adjacency lists are strongly preferred despite the O(1) lookup advantage of matrices.

Question 2

For an undirected graph, the adjacency matrix is always symmetric (A[i][j] = A[j][i] for all i, j).

• T. True
• F. False

Answer: True

In an undirected graph, an edge between vertices i and j means both A[i][j] = 1 and A[j][i] = 1 — the edge exists in both directions. Symmetry follows directly. For directed graphs this does not hold: an arc from i to j sets A[i][j] = 1 but A[j][i] remains 0 unless there is also an arc from j to i. Always check whether the graph is directed before assuming symmetry.

Question 3

You compute A², where A is the adjacency matrix of a graph. What does the entry (A²)[i][j] count, and why?

Model answer: It counts the number of distinct walks of length 2 from vertex i to vertex j — that is, the number of intermediate vertices k such that edges i→k and k→j both exist.

Matrix multiplication gives (A²)[i][j] = Σ_k A[i][k] · A[k][j]. The product A[i][k] · A[k][j] equals 1 only when both edges exist (i to k and k to j). Summing over all possible intermediate vertices k counts how many 2-step walks exist from i to j. More generally, (A^m)[i][j] counts walks of length m, making matrix powers a powerful tool for analyzing graph connectivity.