Question

Which of the following statements are TRUE, where $|E|$ represents the number of edges?
(A). In case of a directed graph, the sum of lengths of all the adjacency list is |E|
(B). For an undirected graph, the sum of the lengths of all the adjacency list is 2|E|
(C). For a dense graph, adjacency matrix representation is preferable
(D). The memory requirement of the adjacency matrix of a graph is dependent on the number of edges

• A. (A), (B) and (D) only
• B. (A), (B) and (C) only
• C. (A), (B), (C) and (D)
• D. (A), (B) and (C) only

Hint:

In dense graphs, adjacency matrices are more efficient than adjacency lists. The memory for an adjacency matrix depends on the number of vertices, not edges.

Answer 1

The Correct Option is C

Step 1: Statement Analysis.
- (A) In a directed graph, the total number of entries across all adjacency lists equals $|E|$. This is accurate as each edge appears precisely once in its originating vertex's adjacency list.
- (B) In an undirected graph, the sum of the lengths of all adjacency lists is $2|E|$. This holds true because each edge is represented in the adjacency lists of both its connected vertices.
- (C) For dense graphs, an adjacency matrix is the preferred representation. This is correct; dense graphs with many edges benefit from an adjacency matrix, which efficiently stores edge presence between all vertex pairs, compared to an adjacency list.
- (D) The memory usage of a graph's adjacency matrix is determined by the number of edges. This statement is incorrect. The memory footprint of an adjacency matrix is solely dependent on the number of vertices, irrespective of the edge count.

Step 2: Final Determination.
Therefore, the accurate selections are (3) (A), (B), (C), and (D).