Question
According to the following graph just answer this two questions :
1-Let G be a graph with n vertices and m edges.
a. True or false: All its DFS forests (for traversals starting at different vertices)
will have the same number of trees?
2-Explain how one can identify connected components of a graph by using
a. a depth-first search.
2 troduction to the Design and Analysis of Algorithms 3rd Edition.pdf-Adobe Acrobat Reader DC File Edit View Window Help Home Tools ntroduction to the Bookmarks Exercises 3.5 i. Consider the following graph. Problem A Exercises 3.3 3.4 Exhaustive Search a. Write down the adjacency matrix and adjacency lists specifying this graph. (Assume that the matrix rows and columns and vertices in the adjacency A Traveling salesman lists follow in the alphabetical order of the vertex labels.) Problem b. Starting at vertex a and resolving ties by the vertex alphabetical order, Knapsack Problem traverse the graph by depth-first search and construct the corresponding depth-first search tree. Give the order in which the vertices were reached -A Assignment for the first time (pushed onto the traversal stack) and the order in which Problem the vertices became dead ends (popped off the stack) A Exercises 3.4 2. If we define sparse graphs as graphs for which IEIE o IVD, which implemen tation of DFS will have a better time efficiency for such graphs, the one that 3.5 Depth-First Search uses the adjacency matrix or the one that uses the adjacency lists? and Breadth-First 3. Let G be a graph with n vertices and m edges. Search a. True or false: All its DFS forests (for traversals starting at different ver- Depth-First Search tices) will have the same number of trees? Breadth-First True or false: All its DFS forests will have the same number of tree edges and the same number of back edges? Search A Exercises 3.5 4. Traverse the graph of Problem 1 by breadth-first search and construct the corresponding breadth first search tree. Start the traversal at vertex a and A summary resolve es by the vertex alphabetical order. Decrease-and-Conquer Ask me anything A Sign In Export PD v Create PDF Adobe PDF Pack Convert files to PDF and easily combine them with other file types with a paid subsc Select File to Convert to pDF Select File GE Edit PDF Comment L Combine Files Store and share files in the Document Cloud More 38 AM 3/5/2017
Explanation / Answer
1.) False
Let the number of components in DFS forest be k. Let the number of nodes in ith component be ci. then the number of tree edges in the ith component is ci-1 (because it is a tree). So total number of tree edges is c1+c2...+ck . This sum will vary for each DFS forest because each DFS forest will have different number of component of different sizes.Which determines that a graph with n vertices and m edges will not have the same number of trees.
2.) A strongly-connected component of a directed graph G is a maximal subset V' of the vertices with the property that every node in V' is reachable from every other node in V'. Finding the strongly-connected components is closely related to finding cycles. We can detect cycles by looking for back edges in a DFS forest. So to find strongly-connected components, we will first compute a DFS forest and then look for chains of back edges that take us up higher in the tree. Each strongly-connected component we find will be identified with some highest reachable node, and will consist of all descendants of that node that can reach it by some path.
