C134 Suppose G is a graph with n vertices and m edges Descri

C-13.4: Suppose G is a graph with n vertices and m edges. Describe a way to represent G using O(n +m) space so as to support in O(log n) time an operation that can test, for any two vertices v and w, whether v and w are adjacent. Additionally, the representation of G should support deletion of an edge in O(log n) time.

Solution

Input: Graph G with the two vertices v and w.

Algorithm: Check the adjacency.

Step 1: Start finding the connected component in the graph.

Step2: Provide the numbering to each vertex like start time and end time of each vertex.

Step 3: when both the vertices v, and w get covered by the parser stop the parsing.

Step 4: till the step 3 the compiler will take log n time. Where n is the number of vertices in the graph.

Step 5: After the step 4, when compiler reached at the second vertices, it checks the previous vertex. If the previous vertex is v of the w vertex. It means the both the vertices are adjacent.

Step 6: In step 5, the compiler will take only O (1) time.

Thus, the total time taken by the compile is = log(n) + O (1)

                                                                     = log(n) time.

Time to delete an edge:

To delete an edge from the graph using same procedure will take log (n) time.

Space complexity:

To store the n vertices and m edges will take O (n + m) time.