Problem2D: Here is a variation on the above greedy algorithm. Let { x_{1}} be any vertex of a weighted connected graph {G} with {n} vertices and let {T_{1}} be the subgraph with the one vertex {x_{1}} and no edges. After a tree (subgraph) { T_{k}}, {k<n}, has been defined, let {e_{k}} be a cheapest edge among all edges with one end in {V(T_{k})} and the other end not in {V(T_{k})}, and let {T_{k+1}} be the tree obtained by adding that edge and its other end to {T_{k}}. Prove that {T_{n}} is a cheapest spanning tree in {G}.

Solution: This algorithm is called Prim’s algorithm. The proof can be found in Wikipedia. We state the proof here again. Suppose {T^{\prime }} is a cheapest spanning tree. If {T_{n}=T^{\prime }}, the proof finished. Otherwise, let {e_{k}} be the first edge not in {T^{\prime }} when we generate {T.} Denote by {V} all the edges before we add {e_{k}}. Since { T^{\prime }} is a spanning tree, there is a unique cycle in {T^{\prime }} containing two ends of {e_{k}}. We claim that there is at least one edge {w} having one end in {V}, and the other end not in {V}. Otherwise, if all the vertices of the cycle are in {V}, {T_{n}} will contain a cycle, a contradiction. On the other hand, not all the vertices are outside of {V} since one end of {e_{k}} is in {V}. So there must exists at least one edge {w } having one end in {V} and the other not in {V}. By Prim’s algorithm, { c(w)\geq c(e_{k})}, otherwise {w} would be chosen rather than {e_{k}}. Add { e_{k}} to {T^{\prime }} and delete {w}, we obtain a new spanning tree { T^{\prime \prime }} which is still a cheapest spanning tree. Keep doing this until we obtain a cheapest spanning tree identical to {T},

Note: The hint in the book says that {T_{n}} has the property that for every edge {e} in {T_{n}}, the ends of {e} are in different components of {G:\left\{ w:c(w)<c(e)\right\} }. And any spanning having this property will be a cheapest spanning tree. I still do not know how to show the second part. I shall be happy if anyone can suggest the solution.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: