Description
1. Describe an algorithm to compute the reversal (also called transpose)
rev(G) of a directed graph in O(V + E) time. (10 points)
2. Given a directed graph G. Let v denote a vetex of G, and S(v) be the
strong component of G that contains v. For two arbitrary vertices u, v ∈
G, prove that u can reach v if and only if S(u) can reach S(v) in scc(G).
(10 points)
3. Given an undirected graph G with weighted edges and a minimum spanning tree T of G, describe an algorithm (use pseudocode) to update the
minimum spanning tree T when the weight of a single edge e is increased.
The input to your algorithm is the edge e and its new weight value. You
shold modify the spanning tree T so that it is still a minimum spanning
tree. (10 points)
Hint: Consider the cases e ∈ T and e 6∈ T separately.
4. Given a directed graph G with weighted edges, describe an algorithm to
find the shortest path from one vertex s to another vertex t. There is
exactly one edge in G that is with negative weight. (10 points)
Hint: Consider modifying Dijkstra’s algorithm. Of course other ideas
could also be great.
1
