3 a a. [2] Does Prim's algorithm always work correctly on graphs with negative edge weights?...

 

Transcribed Image Text:

3 a a. [2] Does Prim's algorithm always work correctly on graphs with negative edge weights? b. [2] Apply Prim's algorithm on the following graph. Show the construction of the minimum spanning tree at each step. Start at vertex a. What is the total weight of the spanning tree? b 4 5 9 1 2. f 5 8 C c. [3] Let T be a minimum spanning tree of graph G obtained by Prim's algorithm. Let Gnew be a graph obtained by adding to G a new vertex and some edges with weights, connecting the new vertex to some vertices in G. Can we construct a minimum spanning tree of Gnew by adding one of the new edges to T? If you answer yes, explain how; if you answer no, explain why not. d. [5] Prove that any weighted connected graph with distinct weights has exactly one minimum spanning tree. [Note: Prove by contradiction.] 3 a a. [2] Does Prim's algorithm always work correctly on graphs with negative edge weights? b. [2] Apply Prim's algorithm on the following graph. Show the construction of the minimum spanning tree at each step. Start at vertex a. What is the total weight of the spanning tree? b 4 5 9 1 2. f 5 8 C c. [3] Let T be a minimum spanning tree of graph G obtained by Prim's algorithm. Let Gnew be a graph obtained by adding to G a new vertex and some edges with weights, connecting the new vertex to some vertices in G. Can we construct a minimum spanning tree of Gnew by adding one of the new edges to T? If you answer yes, explain how; if you answer no, explain why not. d. [5] Prove that any weighted connected graph with distinct weights has exactly one minimum spanning tree. [Note: Prove by contradiction.]

Answer rating: 100% (QA)

Answer No Prims algorithm does not always work correctly on graphs with negative edge weights Prims ... View the full answer