Represent graphs (adjacency list/matrix) - Discrete Math

1. A programmer incorrectly implements an adjacency list by including each undirected edge only once (instead of twice) in the data structure. When this flawed adjacency list is converted back to an adjacency matrix, what property will the resulting matrix definitely have?
   Answer: The matrix will be asymmetric with some entries $a_{ij} \neq a_{ji}$ where edges exist When dealing with graph representations, understanding how adjacency lists and matrices correspond is crucial. In a correct undirected graph implementation, each edge appears twice in the adjacency list: if there's an edge between vertices i and j, then j appears in i's list AND i appears in j's list. The flawed implementation only stores each edge once, meaning some edges will be "one-way" in the adjacency list. When you convert this back to an adjacency matrix, you'll set $a_{ij} = 1$ if j appears in vertex i's list, but if the edge was only stored once (say, only j in i's list but not i in j's list), then $a_{ji} = 0$. This creates asymmetry where $a_{ij} \neq a_{ji}$ for existing edges, making answer D correct. Answer A is wrong because the number of 1s depends on exactly how edges were stored, not necessarily half. Answer B is incorrect since standard conversion algorithms don't automatically compensate for missing entries—they convert what's actually in the data structure. Answer C assumes a very specific storage pattern (upper triangular) that wasn't specified; the programmer could have stored edges inconsistently in any direction. Study tip: Remember that undirected graphs require symmetric adjacency matrices ($a_{ij} = a_{ji}$) and symmetric adjacency lists (mutual references). When you see questions about flawed graph implementations, check whether the fundamental symmetry property is violated—this is often the key insight being tested.
2. An undirected graph on 5 vertices has the adjacency list representation: $v_1: [v_2, v_4, v_5]$, $v_2: [v_1, v_3, v_5]$, $v_3: [v_2, v_4]$, $v_4: [v_1, v_3]$, $v_5: [v_1, v_2]$. How many 1's appear in the upper triangular portion (above the main diagonal) of its adjacency matrix?
   Answer: 5 The edges are: (v₁,v₂), (v₁,v₄), (v₁,v₅), (v₂,v₃), (v₂,v₅), (v₃,v₄). In the upper triangular portion, we count each edge once: positions (1,2), (1,4), (1,5), (2,3), (2,5) give 5 ones. Choice A misses one edge. Choice C counts the full symmetric matrix. Choice D counts each adjacency list entry.
3. An adjacency list representation uses arrays where each vertex $v$ maps to a sorted array of its neighbors. If vertex 1 maps to $[2, 4, 5]$, vertex 2 maps to $[1, 3]$, vertex 3 maps to $[2, 5]$, vertex 4 maps to $[1]$, and vertex 5 maps to $[1, 3]$, what is the value of entry $(2,4)$ in the corresponding adjacency matrix?
   Answer: 0 Entry $(2,4)$ is 1 if there's an edge from vertex 2 to vertex 4, and 0 otherwise. Vertex 2's adjacency list is $[1, 3]$, which doesn't contain vertex 4, so there's no edge from 2 to 4. Therefore $(2,4) = 0$. Choice B incorrectly assumes an edge exists. Choice C might confuse matrix arithmetic. Choice D incorrectly suggests the matrix entry doesn't exist.
4. A graph's adjacency matrix $A$ has the property that $A_{i,j} = 1$ if and only if vertices $i$ and $j$ are connected by an edge, and $A_{i,i} = 0$ for all $i$. If the sum of row 3 is 4 and the sum of column 3 is 2, what can be concluded about the graph?
   Answer: The graph is directed with vertex 3 having out-degree 4 and in-degree 2 Since row sums and column sums differ, the matrix is not symmetric, indicating a directed graph. Row sum gives out-degree (edges leaving vertex 3) and column sum gives in-degree (edges entering vertex 3). Choice A assumes undirected but row≠column sum contradicts this. Choice C uses wrong sum. Choice D incorrectly adds in-degree and out-degree.
5. Consider converting between representations of a graph with $n$ vertices and $m$ edges. The adjacency matrix requires $\Theta(n^2)$ space, while adjacency lists require $\Theta(n + m)$ space. For which type of graph do these space complexities become equal in order of magnitude?
   Answer: When the graph is dense with $m = \Theta(n^2)$ When analyzing graph representation space complexities, you need to determine when $\Theta(n^2)$ and $\Theta(n + m)$ represent the same order of magnitude. This happens when the dominant terms in both expressions are equal. For adjacency lists with $\Theta(n + m)$ space to equal adjacency matrix's $\Theta(n^2)$ space, the $m$ term must dominate the $n$ term in the first expression. This occurs when $m = \Theta(n^2)$, making the adjacency list space $\Theta(n + n^2) = \Theta(n^2)$. Answer D correctly identifies this scenario: when the graph is dense with $m = \Theta(n^2)$, both representations require $\Theta(n^2)$ space. Answer A is wrong because when $m = O(\log n)$, adjacency lists need only $\Theta(n + \log n) = \Theta(n)$ space, which is much less than $\Theta(n^2)$ for large $n$. Answer B is incorrect because trees have $m = n - 1$, so adjacency lists require $\Theta(n + (n-1)) = \Theta(n)$ space, again much smaller than $\Theta(n^2)$. Answer C fails because when $m = \Theta(n)$, adjacency lists need $\Theta(n + n) = \Theta(n)$ space, which remains significantly less than the matrix's $\Theta(n^2)$ requirement. Study tip: Remember that space complexities are equal only when both expressions have the same dominant term. For graph representations, this happens precisely when the number of edges reaches $\Theta(n^2)$ — the maximum possible for simple graphs.
6. A graph's adjacency matrix has all zero entries on the main diagonal. After adding a self-loop to vertex 3, exactly one entry changes from 0 to 1. If the original matrix was symmetric, which property is preserved after adding the self-loop?
   Answer: The matrix remains symmetric and represents an undirected graph Adding a self-loop changes only the diagonal entry $(3,3)$ from 0 to 1. Since diagonal entries equal their own transposes, the matrix remains symmetric. A symmetric adjacency matrix with self-loops still represents an undirected graph (now with self-loops allowed). Choices B and C incorrectly claim the graph type changes. Choice D is true but not the most specific preserved property.
7. Consider the adjacency list representation where vertex $A$ maps to $[B, C, D]$, vertex $B$ maps to $[A, D]$, vertex $C$ maps to $[A]$, and vertex $D$ maps to $[A, B, E]$, but vertex $E$ is missing from the representation. What should vertex $E$'s adjacency list be to make this a valid undirected graph?
   Answer: $[D]$ When working with adjacency lists for undirected graphs, remember that adjacency must be symmetric: if vertex $X$ is adjacent to vertex $Y$, then $Y$ must also be adjacent to $X$. This bidirectional property is what makes the graph "undirected." To find $E$'s adjacency list, examine which vertices claim to be adjacent to $E$. Looking at the given adjacency lists, only vertex $D$ includes $E$ in its list: $[A, B, E]$. Since $D$ is adjacent to $E$, the symmetry property requires that $E$ must be adjacent to $D$. No other vertex mentions $E$, so $E$ is only connected to $D$. Therefore, $E$'s adjacency list should be $[D]$, making answer D correct. Let's see why the other options violate the symmetry requirement: A) $[A, B, C, D]$ would mean $E$ is adjacent to all other vertices, but none of $A$, $B$, or $C$ include $E$ in their lists. This creates asymmetric connections. B) $[]$ (empty list) would mean $E$ has no neighbors, but $D$ claims to be adjacent to $E$. This breaks the symmetry between $D$ and $E$. C) $[A, D]$ includes $A$, but $A$'s list $[B, C, D]$ doesn't include $E$, creating another asymmetric relationship. Study tip: When checking adjacency lists for undirected graphs, always verify that every connection appears in both directions. Scan each vertex's list and ensure the reverse connection exists.
8. Consider an undirected multigraph (allowing multiple edges between the same pair of vertices) with adjacency matrix $A$ where $A_{i,j}$ equals the number of edges between vertices $i$ and $j$. If converting to an adjacency list representation where each edge is listed separately, and vertex 3 has matrix row $[0, 2, 0, 1, 3]$, how many entries will appear in vertex 3's adjacency list?
   Answer: 6 entries: 2, 2, 4, 5, 5, 5 In a multigraph adjacency list, each edge is listed separately. Row $[0, 2, 0, 1, 3]$ means 0 edges to vertex 1, 2 edges to vertex 2, 0 edges to vertex 3, 1 edge to vertex 4, and 3 edges to vertex 5. The adjacency list contains: 2, 2, 4, 5, 5, 5 (total 6 entries). Choice A counts unique neighbors only. Choice B misinterprets the format. Choice D double-counts for undirected edges.
9. A complete bipartite graph $K_{3,4}$ has vertex sets $U = \{u_1, u_2, u_3\}$ and $V = \{v_1, v_2, v_3, v_4\}$ where every vertex in $U$ connects to every vertex in $V$. In the adjacency list representation, what is the total length of all adjacency lists combined?
   Answer: 24 Each vertex in $U$ connects to 4 vertices in $V$, and each vertex in $V$ connects to 3 vertices in $U$. Total list length = $3 \times 4 + 4 \times 3 = 12 + 12 = 24$. Choice A counts only edges once. Choice B adds vertices to edge count. Choice D incorrectly computes $7 \times 4$.
10. An undirected graph has adjacency lists: vertex A: [B, C, D], vertex B: [A, D], vertex C: [A], vertex D: [A, B, E], vertex E: [D]. If we construct the adjacency matrix with vertices ordered alphabetically, what is the sum of all entries in the matrix?
    Answer: 10 For an undirected graph, each edge contributes 2 to the sum of the adjacency matrix (once for each direction). From the adjacency lists, the edges are: A-B, A-C, A-D, B-D, D-E. That's 5 edges total. Since each edge appears twice in an undirected graph's adjacency matrix (as $a_{ij} = a_{ji} = 1$), the sum is $5 \times 2 = 10$.
11. Consider the adjacency list representation: vertex 1: [2, 3], vertex 2: [1, 4], vertex 3: [1, 4], vertex 4: [2, 3, 5], vertex 5: [4]. In the corresponding adjacency matrix, how many entries are equal to 1?
    Answer: 10 entries equal to 1 Each entry in an adjacency list corresponds to a 1 in the adjacency matrix. Counting all list entries: vertex 1 has 2 entries, vertex 2 has 2 entries, vertex 3 has 2 entries, vertex 4 has 3 entries, vertex 5 has 1 entry. Total: $2+2+2+3+1 = 10$ entries, so exactly 10 matrix entries equal 1.
12. A bipartite graph with vertex sets $X = \{x_1, x_2, x_3\}$ and $Y = \{y_1, y_2\}$ has edges from each $x_i$ to every vertex in $Y$. If the vertices are ordered as $x_1, x_2, x_3, y_1, y_2$ in the adjacency matrix, which pattern appears?
    Answer: A $5 \times 5$ matrix with 1s in the upper-right $3 \times 2$ and lower-left $2 \times 3$ blocks In a bipartite graph, edges only exist between vertices in different partitions. With ordering $x_1, x_2, x_3, y_1, y_2$, edges from $X$ to $Y$ create 1s in the upper-right $3 \times 2$ block (rows 1-3, columns 4-5). Since the graph is undirected, edges from $Y$ to $X$ create 1s in the lower-left $2 \times 3$ block (rows 4-5, columns 1-3). All other entries are 0.
13. When converting from an adjacency list to an adjacency matrix for a graph with $n$ vertices, which statement about space complexity is most accurate?
    Answer: Adjacency matrix always uses $O(n^2)$ space while adjacency list uses $O(n + m)$ where $m$ is edges An adjacency matrix for $n$ vertices always requires $O(n^2)$ space regardless of edge count, since it must store an $n \times n$ matrix. An adjacency list uses $O(n + m)$ space: $O(n)$ for the vertex array and $O(m)$ for storing all edges. For dense graphs ($m \approx n^2$), matrices become more efficient, and for sparse graphs, lists are better.
14. In converting a weighted directed graph to its representations, the adjacency matrix has entry $a_{2,4} = 7$ and $a_{4,2} = 0$. What would appear in the adjacency list representation?
    Answer: Vertex 2's list contains 4 with weight 7, and vertex 4's list does not contain 2 In an adjacency matrix, $a_{i,j}$ represents the weight of the edge from vertex $i$ to vertex $j$. So $a_{2,4} = 7$ means there's an edge from vertex 2 to vertex 4 with weight 7, which appears in vertex 2's adjacency list. Since $a_{4,2} = 0$, there's no edge from vertex 4 to vertex 2, so vertex 4's list does not contain 2.
15. Two different adjacency list representations of the same undirected graph are given: List A has vertex 3: [1, 2, 4] and List B has vertex 3: [4, 1, 2]. When converted to adjacency matrices using identical vertex orderings, how do the resulting matrices compare?
    Answer: The matrices will be identical since adjacency lists order is irrelevant for undirected graphs When you encounter questions about graph representations, remember that different representations of the same graph must capture identical structural information, regardless of how that information is organized or ordered. An adjacency list for an undirected graph simply records which vertices are connected to each vertex. For vertex 3, both List A [1, 2, 4] and List B [4, 1, 2] tell you the exact same thing: vertex 3 is connected to vertices 1, 2, and 4. The order in which these neighbors are listed is completely arbitrary and doesn't affect the underlying graph structure. When you convert either list to an adjacency matrix using the same vertex ordering, you're creating a matrix where entry (i,j) equals 1 if vertices i and j are connected, and 0 otherwise. Since both lists contain identical connection information for vertex 3, row 3 of both matrices will be identical. The same logic applies to all other vertices, making the complete matrices identical. Option A is wrong because the connection information for vertex 3 is complete in both representations. Option B incorrectly assumes that different list orderings create different matrix entries, but matrix entries depend only on whether connections exist, not on list order. Option C misunderstands how adjacency matrices work—the order within adjacency lists doesn't affect matrix structure, and undirected graphs always produce symmetric (not just transposed) matrices anyway. Remember: adjacency lists are like shopping lists—whether you write "milk, eggs, bread" or "bread, milk, eggs," you're buying the same items. The order doesn't change the underlying relationships.
16. A directed graph has vertices $\{v_1, v_2, v_3, v_4\}$ and edges $\{(v_1, v_2), (v_1, v_3), (v_2, v_4), (v_3, v_1), (v_3, v_4), (v_4, v_3)\}$. What is the sum of all entries in the adjacency matrix representation of this graph?
    Answer: 6 The adjacency matrix has a 1 for each directed edge and 0 elsewhere. Since there are exactly 6 directed edges listed, the sum of all entries equals 6. Choice B incorrectly counts vertices plus edges. Choice C might result from double-counting bidirectional connections. Choice D incorrectly counts each edge twice.
17. A graph's adjacency matrix has exactly 3 ones in row 2 and exactly 2 ones in column 2. What can be definitively concluded about the graph?
    Answer: The graph must be directed since the in-degree and out-degree of vertex 2 differ In an undirected graph, the adjacency matrix must be symmetric, so entry $a_{ij} = a_{ji}$. This means row 2 and column 2 would have the same sum. Since row 2 has sum 3 and column 2 has sum 2, the matrix cannot be symmetric, so the graph must be directed. The out-degree of vertex 2 is 3 and the in-degree is 2.
18. A graph $G$ has the adjacency matrix $A = \begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 2 & 0 \\ 0 & 2 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix}$. If this matrix is converted to an adjacency list representation, what is the total number of entries across all adjacency lists?
    Answer: 10 entries total In the adjacency matrix, we count all non-zero entries: positions (0,1)=1, (0,3)=1, (1,0)=1, (1,2)=2, (2,1)=2, (2,3)=1, (3,0)=1, (3,2)=1. For adjacency lists, each non-zero entry $a_{ij}$ with value $k$ contributes $k$ entries to vertex $i$'s list. So vertex 0 has 2 entries, vertex 1 has 3 entries (1+2), vertex 2 has 3 entries (2+1), and vertex 3 has 2 entries, totaling 10 entries.
19. An adjacency matrix $A$ for an undirected graph satisfies $A^2_{i,j} = \text{number of paths of length 2 from vertex } i \text{ to vertex } j$. If $A$ has 1's at positions $(1,2)$, $(1,3)$, $(2,1)$, $(2,4)$, $(3,1)$, $(4,2)$ and 0's elsewhere, what is $A^2_{1,4}$?
    Answer: 1 $A^2_{1,4} = \sum_{k} A_{1,k} \cdot A_{k,4}$. From the given entries: $A_{1,2} = A_{1,3} = 1$, others in row 1 are 0. Only $A_{2,4} = 1$ in column 4, others are 0. So $A^2_{1,4} = A_{1,2} \cdot A_{2,4} = 1 \cdot 1 = 1$. There's exactly one path of length 2 from vertex 1 to vertex 4: $1 \to 2 \to 4$. Other choices miscount the matrix multiplication.
20. A weighted directed graph uses an adjacency matrix where $A_{i,j}$ stores the weight of edge $(i,j)$ if the edge exists, and $\infty$ if no edge exists. The matrix has finite entries at positions $(1,2):5$, $(1,3):2$, $(2,3):1$, $(3,1):4$, and $\infty$ elsewhere. How would vertex 2's adjacency list be represented using (neighbor, weight) pairs?
    Answer: $[(3, 1)]$ When working with graph representations, you need to understand the fundamental difference between adjacency matrices and adjacency lists. An adjacency matrix uses rows to represent source vertices and columns to represent destination vertices, while an adjacency list for a vertex contains only the vertices that can be directly reached from that vertex. To find vertex 2's adjacency list, you need to examine row 2 of the adjacency matrix, which tells you all edges originating from vertex 2. Looking at row 2: $A_{2,1} = \infty$, $A_{2,2} = \infty$, and $A_{2,3} = 1$. Since only $A_{2,3}$ has a finite value, vertex 2 has exactly one outgoing edge: to vertex 3 with weight 1. Therefore, vertex 2's adjacency list is $[(3, 1)]$, making D correct. Choice A is wrong because it includes $(1, \infty)$, suggesting an edge from vertex 2 to vertex 1 that doesn't exist. Choice B incorrectly includes $(1, 4)$, which represents the edge from vertex 3 to vertex 1 (found at position $(3,1)$ in the matrix), not an edge from vertex 2. Choice C includes $(1, 5)$, which corresponds to the edge from vertex 1 to vertex 2 (position $(1,2)$), but adjacency lists only show outgoing edges from the specified vertex. Remember: when converting from an adjacency matrix to adjacency lists, always focus on the row corresponding to your vertex of interest. The row index represents the source vertex, and finite entries in that row indicate the destinations and weights of outgoing edges.

Start this quiz