Let G = (V, E) be a directed graph in which each vertex u V is labeled with a unique integer L(u) from the set {1, 2, ..., |V |}. For each vertex u V , let R(u) be the set of vertices that are reachable from u. Define min(u) to be the vertex in R(u) whose label is minimum.

(a) (10 pts) Write pseudocode for algorithm that computes min(u) for all vertices in the graph. You will receive a 5 pt extra credit if your algorithm runs in O(|V | + |E|).

(b) (10 pts) Prove the worst-case running time of your algorithm.

(c) Extra credit (10 pts): Prove that your algorithm is correct (i.e., that it will always output the correct answer).

2. Let G = (V, E) be an undirected, fully-connected graph with real weights that are all distinct (i.e., no two edges have the same weight). Let T 0 be the minimum spanning tree of G and let T 00 be a secondbest spanning tree (i.e., it has the minimum weight among all spanning trees of G, excluding T 0 . For all the questions below, assume that G is not a tree (i.e., it has additional edges and thus contains at least one cycle).

(a) (10 pts) Show that the minimum spanning tree is unique.

(b) (10 pts) Show that T 00 is not necessarily unique. Hint: Come up with a simple counter-example.

(c) (15 pts) Prove that G contains edges (u, v) T 0 and (x, y) 6 T 0 , such that T{(u, v)}{(x, y)} is a second-best minimum spanning tree of G.

(d) Extra credit (10 pts): Prove that if you replace two or more edges of T 0 , you cannot form a second-best minimum spanning tree. 2