Consider the following algorithm to obtain minimum spanning tree of a weighted connected graph. Let G...

 

Transcribed Image Text:

Consider the following algorithm to obtain minimum spanning tree of a weighted connected graph. Let G be a weighted connected graph of order n whose edges have distinct weights. Step 1: Initialize H as the empty graph On with vertex set V(G). Step 2: For each connected component H' of H, among all edges joining V(H) and V(G) \ V(H), find the edge with minimum weight and add it to H. Step 3: If |E(H)| < n − 1, then repeat Step 2. If |E(H)| = n − 1, then stop and denote the resulting graph by T. 1. Prove that this algorithm produces the minimum spanning tree of G. 2. Show how this algorithm can be applied to connected weighted graph to find the minimum spanning tree even if some edges have the same weight. Justify your answer. Consider the following algorithm to obtain minimum spanning tree of a weighted connected graph. Let G be a weighted connected graph of order n whose edges have distinct weights. Step 1: Initialize H as the empty graph On with vertex set V(G). Step 2: For each connected component H' of H, among all edges joining V(H) and V(G) \ V(H), find the edge with minimum weight and add it to H. Step 3: If |E(H)| < n − 1, then repeat Step 2. If |E(H)| = n − 1, then stop and denote the resulting graph by T. 1. Prove that this algorithm produces the minimum spanning tree of G. 2. Show how this algorithm can be applied to connected weighted graph to find the minimum spanning tree even if some edges have the same weight. Justify your answer.

Answer rating: 100% (QA)

1 To prove that this algorithm produces the minimum spanning tree of G we need to show two things a the resulting graph T is a spanning tree of G and ... View the full answer