How would you generalize this idea ? Suppose you are given a graph G and a particular edge {u,v} in the graph. How would you alter Prim's algorithm to find the minimum spanning tree subject to the condition that {u,v} is in the tree?

PROBLEM 8 An undirected weighted graph G is given below: 2 5 Figure 16: An undirected weighted graph has 6 vertices, a through f, and 9 edges. Verter d is on the left. Vertex f is above and to the right of vertex d. Verter e is below and to the right of verter f, but above verter d. Verter c is below and to the right of verter e. Verter a is above vertex e and to the right of verter c. Verter b is below and to the right of vertex a, but above verter c. The edges between the vertices and their weight are as follows: d and f, 1; d and e, 4; f and e, 2; e and a, 2; f and a, 3; e and c, 5; c and a, 7; c and b, 5; and a and b, 6. (a) Use Prim's algorithm to compute the minimum spanning tree for the weighted graph. Start the algorithm at vertex a. Show the order in which the edges are added to the tree. ( age ) (e, f ) . ( f , d ) re, c ) ce, b (b) What is the minimum weight spanning tree for the weighted graph in the previous question subject to the condition that edge {d, e} is in the span- ning tree? (c) How would you generalize this idea? Suppose you are given a graph G and a particular edge {u, v} in the graph. How would you alter Prim's algorithm to find the minimum spanning tree subject to the condition that {u, v} is in the tree