Homework Assignment #12

Objectives

To solve problems using the strongly connected components algorithm.

Exercises

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

Question 1

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).

Question 2

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.)

Question 3

3.15 in the textbook

cs-312/hw12.txt · Last modified: 2014/12/31 23:00 by ringger
Back to top
CC Attribution-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0