This is the end of the preview.
Sign up
to
access the rest of the document.

Unformatted text preview: 15-750 — Graduate Algorithms — Spring 2009Miller and Dinitz and TangwongsanAssignment 4 Solutions1Minimum Spanning Trees(25 pts.)While we did not have time to cover them in class, minimum spanning trees are a crucial buildingblock for many more complicated algorithm. We assume that you have seen MSTs before in anundergraduate algorithms class such as 15-451 at CMU. For completeness, we now define themformally. Given an undirected graphG= (V,E) and a weight functionw:e→R≥, aspanningtreeis a connected subgraphTofGcontaining no cycles such that every vertex has degree at least1 inT. The weight of a treeT= (V,E) is the sum of the weights of its edges, i.e.∑e∈Ew(e).Our goal is to find a spanning tree of minimum weight. For the purposes of this problem we willassume that all of the edge weights are distinct, so no two edges have exactly the same weight (thisdoesn’t actually matter, but makes some of the proofs easier)There are many algorithms for computing MSTs, but two are particularly well known: Kruskal’salgorithm and Prim’s algorithm. In this problem we will ask you to analyze a different algorithm,thereverse-delete algorithm. In this algorithm we begin with the full graphG, and then startdeleting edges in order of decreasing weight. For each edgee, when we get to it in the decreasingorder we delete it as long as doing so would not disconnect the graph that we currently have.(a) Prove that the reverse-delete algorithm returns a spanning tree(b) LetCbe any cycle inG, and letebe the edge onCof largest weight. Prove thatedoes not belong to any minimum spanning tree ofG.(c) Prove that no spanning tree ofGhas weight less than the weight of the tree returnedby the reverse-delete algorithm.Solution:a) Assuming thatGis connected, since the algorithm does not throw out any edge that woulddisconnect the graph we know that it returns a spanning connected graph. To see that it is acyclic(i.e. a tree), suppose for contradiction that there is some cycleCin the graph it returns, and letebe the edge inCof maximum weight. Then wheneis considered by the algorithm all of the otheredges inCare still present, since they have not been considered yet. Thus removingewould notdisconnect the graph, so the algorithm would remove it, giving us our contradiction.b) LetMbe a minimum spanning tree, and suppose thateis inM. We will derive a contradiction.RemovingefromMdisconnects the tree into two components, saySandT. SinceCis acycle containinge, it must cross the(S,T)cut at least twice, once witheand once with someother edgee. By construction we know thatw(e)< w(e)Note thateis not inM, or elseMwould have some cycle involvingeande. But sinceecrosses the(S,T)cut we know thatM=M∪{e}\{e}is connected and has no cycles, i.e. is a spanning tree. But sincew(e)< w(e)we have that the weight ofMis less than the weight ofM, contradicting our assumption that...
View
Full Document