Solution
1. Analysis of Statement (A):
In a directed graph, each edge (u,v) is represented exactly once in the adjacency list (in the list of vertex u). Therefore, the sum of lengths of all adjacency lists is equal to the number of edges ∣E∣.
Statement (A) is Correct.
2. Analysis of Statement (B):
An adjacency matrix is a V×V matrix where V is the number of vertices. This requires V×V storage space, which is O(V2).
Statement (B) is Correct.
3. Analysis of Statement (C):
In an undirected graph, an edge between u and v is stored twice: once in the list for u and once in the list for v. Thus, the sum of the lengths of all adjacency lists is 2∣E∣, not ∣E∣.
Statement (C) is Incorrect.
4. Analysis of Statement (D):
The memory requirement for an adjacency list is O(V+E) for directed graphs and O(V+2E) for undirected graphs. In both cases, the storage significantly depends on the number of edges ∣E∣.
Statement (D) is Correct.
Conclusion:
Statements (A), (B), and (D) are correct.
Correct Option: (c)
