Homework Assignment #12

To solve problems using the strongly connected components algorithm.

Show all work. i.e., justify your answers.

Problem 3.4 graph (i) in the textbook. Just apply the SCC-finding algorithm to identify the SCCs. Start at A, and be sure to show your process and to give your answer clearly as sets of vertices. You do not need to do parts (a)-(d).

Problem 3.4 graph (ii), parts (a)-(d). Re-run the SCC-finding algorithm on this graph, but this time start step 1 of the SCC algorithm at vertex G in order to compute the post-order numbers.

• (Note: we already ran the algorithm on this graph in class, but that time we started at vertex A. For this problem, we're trying a different starting point, to find out whether the starting point actually matters.)

3.15 in the textbook