Question

4. Let (G, w) be a connected graph with weights on edges so that all weights are distinct positive real numbers. Suppose we find a MST (minimum spanning trees ) in G by using Prim's algorithm. Prove that no matter what vertex we begin with in Prim algorithm, the set of all weights on edges in the found MST is the same

This problem is dealing with Discrete Math. Please answer fully and clearly, and show/explain all steps or proofs that you state in the answer.

Answer 1

Since Prims Algorithm always give Spanning trees., Every vertex of G must be in the output MST of Prims Algorithm.

Hence no matter what vertex we begin with, each step connect it to its nearest neighbor.

To prove that Prims algorithm gives MST, let P be a connected, weighted graph. At every iteration of Prim's algorithm, an edge must be found that connects a vertex in a subgraph to a vertex outside the subgraph. Since P is connected, there will always be a path to every vertex. The output Y of Prim's algorithm is a tree, because the edge and vertex added to tree Y are connected. Let Y₁be a minimum spanning tree of graph P. If Y₁=Y then Y is a minimum spanning tree. Otherwise, let e be the first edge added during the construction of tree Y that is not in tree Y₁, and V be the set of vertices connected by the edges added before edge e. Then one endpoint of edge e is in set V and the other is not. Since tree Y₁ is a spanning tree of graph P, there is a path in tree Y₁ joining the two endpoints. As one travels along the path, one must encounter an edge f joining a vertex in set V to one that is not in set V. Now, at the iteration when edge e was added to tree Y, edge f could also have been added and it would be added instead of edge e if its weight was less than e, and since edge f was not added, we conclude that

w(f) greater than or equal to w(e).

Let tree Y₂ be the graph obtained by removing edge f from and adding edge e to tree Y₁. It is easy to show that tree Y₂ is connected, has the same number of edges as tree Y₁, and the total weights of its edges is not larger than that of tree Y₁, therefore it is also a minimum spanning tree of graph P and it contains edge e and all the edges added before it during the construction of set V. Repeat the steps above and we will eventually obtain a minimum spanning tree of graph P that is identical to tree Y. This shows Y is a minimum spanning tree. The minimum spanning tree allows for the first subset of the sub-region to be expanded into a smaller subset X, which we assume to be the minimum.