CSE 417 Assignment #5
Winter 2002

Due: Friday, February 22, 2002.

Reading:

Chapter 4.

Problems:

  1. For a directed graph G=(V,E), define its square H to be the directed graph H=(V,F), where F={ (u,w) | there exists a v in V such that both (u,v) and (v,w) are in E }. I.e., the edges in H correspond exactly to paths of length 2 in G.
    1. Give a fast algorithm to compute H given G, assuming both are represented by adjacency matrices. Analyze its run time.
    2. Give a fast algorithm to compute H given G, assuming both are represented by edge lists. Analyze its run time.
    3. Note, especially for the previous part, that the number of edges in H can be very different from the number in G. How different can they be? Make up some examples that are as extreme as you can make them. E.g., can there be an n-vertex graph G with O(n) edges whose square has Ω(n2) edges? Vice versa? [Note: to be really convincing, you should do this for general n, not some specific value like n=42. I.e., you need to describe a whole series of graphs Gn, n=1, 2, 3, ... that illustrate your point. Presumably, your graphs will follow some simple pattern so that you can describe them all on a finite number of pages...]

  2. Find the articulation points in the following graph by simulating the algorithm presented in class on 2/20. Redraw the graph showing tree edges, back edges, the DFS number and LOW value assigned to each vertex. For definiteness, start your DFS at vertex A and whenever the algorithm has a choice of which edge to follow next, pick the edge to the alphabetically first vertex among the choices.

  3. See Email Corrections. In a directed graph G, I will call a vertex v an 'origin' if every other vertex in G is reachable from v by a directed path. Some directed graphs will have no origin, some will have one, and some will have several. Give a linear time (O(n+m)) algorithm to tell whether a directed graph contains at least one origin or not, and if it does, identify one.

  4. (Extra Credit) Continuing the previous problem, extend your algorithm to also tell whether there is more than one origin or not, still in linear time. [Note: I think the first approach that would occur to me would be to identify all origins and see if there is more than one. However, I think this is noticeably trickier than just deciding whether there is more than one without actually finding them all. It's great if you can figure out how to find them all (extra extra credit), and of course "tricky" to one person may be "trivial" to another, but just remember that finding them all is not required to solve the problem.]