Note this homework is slightly shorter than the last two and has an earlier deadline.
1 Manually run the topological sort algorithm
Run the DFS-based topological sort algorithm taught in class (not the algorithm given in the text- book, which removes an in-degree zero node each time) using the example given in Figure 3.8 part (a) (page 103) of the textbook (for your convenience, also provided here; ignore the shades of the nodes). When performing DFS, when there are multiple choices, use the alphabetical order. For example, you should begin with v1 (the alphabetically smallest). From v1, you should first visit v4. Note: you should show the DFS timestamps and the order of the output nodes.
2 Semiconnected graph
A directed graph G = (V, E) is semiconnected if, for all pairs of vertices u, v ∈ V , there is a path from u to v or from v to u. That is, different from the strongly connected components where you can go from u to v and then back, here you only need to either go from u to v or from v to u but don’t have to get back. Give an efficient algorithm to determine whether or not G is semiconnected. Prove that your algorithm is correct and then analyze its running time. Note: to get full credit, your algorithm needs to run in O(|V | + |E|) time.
3 A distance problem
Do problem 3.9 on page 110. For your convenience, here is the problem description.
2
Suppose a n-node undirected (and unweighted) graph G = (V, E) contains two nodes s and t such that the distance between s and t is strictly greater than n . Show that there must exist some node v (different from s and t) such that deleting v (and all edges incident to v) from G will destroy all paths between s and t. In other words, the new graph by deleting v from G contains no path between s and t. Given an algorithm with running time O(m + n) to find such v (m is the number of edges).
Hint: since this problem concerns distance in a unweighted graph, this leads naturally to BFS...
10% extra credits: paths on a tree
This problem is for students who are looking for some challenge.
You are given T , a undirected tree (i.e. connected and acyclic graph). The objective is finding two nodes u, v of T s.t. the distance (i.e. the number of edges along the unique path between u and
v) is the maximum. Na¨ıvely, you can try all possible pairs of nodes but this is very slow. Here is a very simple algorithm for this problem that runs in linear time.
You start from any node s as the source and perform BFS. Let u be the node with the largest distance from s (i.e. at the largest level). Then you perform a second BFS: this time you use u as the source. Let v be the node with the largest distance from u.
Now, prove this claim: the distance between u and v is the largest possible distance between any two nodes on the tree.
