Question: Problem 4. Consider the strongly connected components algorithm. Assume that the depth-first- search algorithm, given the choice, will visit smaller numbered vertices first. (a) Give
Problem 4. Consider the strongly connected components algorithm. Assume that the depth-first- search algorithm, given the choice, will visit smaller numbered vertices first. (a) Give an example of a directed graph with around 10 to 15 vertices, numbered 1 to n, satisfying the following conditions: (1) The depth-first-search forest has exactly two trees. (2) At least one tree in the depth-first-search forest contains more than one strongly connected component, where at least two of those strongly connected components have at least three vertices. (3) There is at least one forward edge between two vertices in the same strongly connected component. (4) There is at least one forward edge between two vertices in different strongly connected components. (5) There is at least one cross edge between two vertices in the same tree. (6) There is at least one cross edge between two vertices in different trees. Draw the graph. Label the node mumbers. Circle the strongly connected components. (b) Draw the graph. Label the nodes with their finish numbers (not their node numbers). Label the back edges, forward edges, and cross edges. Circle the strongly connected components. (c) Reverse the edges. Draw the graph. Label the nodes with their finish numbers. Circle the strongly connected components
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
