Answer Happy

PROBLEM 5 30 POINTS Consider the following 4 operations for a graph data structure: insert edge, find edge, delete edge, and enumerate all neighbors of a vertex. a) An adjacency dictionary achieves the optimal average-case big O time complexity for all 4 operations, regardless of how many edges are in the graph. Is it possible for an adjacency list or adjacency matrix to also achieve the optimal average-case big O time complexity for all 4 operations? If so, then state under what conditions this is achieved. If not, then state why it is not possible. (15 points) b) An adjacency tree is a graph data structure similar to an adjacency list, except the inner list is replaced with a binary search tree. Assume that the outer list is implemented using a dynamic array. and the inner tree is implemented using a red-black tree. Compute the worst-case and average-case big O time complexities of the 4 operations as a function of the number of vertices V and the number of edges E in the graph. (15 points)