3. Given a directed graph G , we define its transpose GT to be the graph such that E-:? E. In other words, GT has the same number of edges as in G, but the directions of the edges are reversed. Consider the following graph: Draw its transpose. 9 Perform DFS on the original graph G, and write down the start and finish times for each vertex in the graph. Assume that the nodes are in alphabetical order and the adjacency list for each node is also in alphabetical order (the algorithm does not rely on the ordering, this is only for the convenience of checking your answer). Now, perform DFS on the transpose GT, but in the upper-case DFS routine, consider the ver tices in order of decreasing order the finish times computed earlier. For convenience, we again assume that the adjacency list for each node is also in alphabetical order. Draw all depth-first tres constructed in this DFS of G Consider all vertices from a depth-first tree, what can you say about the connectivity of these vertices in G? If you pick a vertex from a depth-first tree and another vertex from a different depth-first tree, you should not observe the same property