Question

Problem 3 (15 points). Let G (V,E) be the following directed graph. a. 1. Draw the reverse graph G of G. 2. Run DFS on G to obtain a post number for each vertex. Assume that in the adjacency list representation of G, vertices are stored alphabetically, and in the list for each vertex, its adjacent vertices are also sorted alphabetically. In other words, the DFS algorithm needs to examine all vertices alphabetically, and when it traverses the adjacent vertices of a vertex, it also needs to examine them alphabetically. (NOTE: you only need to give the post number for each vertex; you do not need to illustrate the internal steps of running DFS on G) 3. Run DFS on G by examining all vertices in the reverse order of their above post numbers to obtain all connected components of G. (NOTE: you only need to give the cc aray, which gives the index of the connected components the coresponding vertex belongs to; you do not need to illustrate the internal steps of running DFS on G.) 4. Draw the meta graph GM for G and give a linearization for GM.

Answer 1

3.

The reverse of the graph G is pre: 3 post4 pre: 2 1)G 2) re 0 postl pre: 6 d post7 pre: 5 post8 pre: 10 post11 Running DFS on GR The order of post numbers a c d e bf 147 8 9 11 3) Now running DFS on G in reverse order of above order b,de) 4) Now the meta graph for G is the graph of strongly connected components. let Si and Sj be two SCCs of G.then they would be two vertices of GM and there would be an edge between them if some u in Si and vin Sj has an edge between them in G So GM