Assignment 3
due by the end of class Wednesday January 31 2001.
SCC stands for strongly connected component.
A sink SCC is an SCC whose vertex set
is a sink in the condensation dag of the digraph.
- The following algorithm
determines reachability in a digraph.
Assume that the results of the algorithm
are stored in an n-by-n boolean array R.
for each vertex v
for each vertex w not equal to v
determine by traversal whether w is reachable from v
endfor
endfor
- Design in detail the most efficient algorithm
you can which uses R to identify the
SCCs of the digraph.
- Using Theta notation, give the worst case
running time of your algorithm.
(In your analysis, do *not* include the time
of the code given above.)
-
Consider the recursive version of DFS
(e.g. on page 9 of the web notes)
performed on a digraph.
The dfs number for each vertex is the
order in which it is visited.
- Prove or disprove:
for each SCC,
the dfs numbers of these vertices
forms a consecutive subsequence of {1,...,n}.
- Prove or disprove:
for each sink SCC,
the dfs numbers of these vertices
form a consecutive subsequence of {1,...,n}.
- Give a counterexample, or give an *outline
of a proof* (you do not have to provide all details):
for any SCC,
the vertices of this SCC
form a subtree of the dfs forest of the digraph.