Question 2.

I. Let G = (V. E) be a directed graph in which each vertex u E V is labeled with a unique integer L(u) from th.2 V For each vertex u E V, let Ru be the set of vertices that are reachable from u Define min(u) to be the vertex in R(u) whose label is minim (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 OVE) (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 distinet ie., no two edges have the same weight). Let T" be the minimum spanning tree of G and let T be a second- best spanning tree (i.e., it has the minimum weight among all spanning trees of G, excluding T. For al 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 is not necessarily unique Hint: Come up with a simple counter-example (c) (15 pts) Prove that G contains edges (u, v) E T and (r, y) T such that T-[(u, v))Ut(,) tree of G. is a second-best minimum spanning (d) Extra cdt (10 pts): Prove that if you replace two or more edges of T, you cannot form a second-best minimum spanning tree