(MST) MINIMUM SPANNING TREE Instance: Graph G=(V,E), for each e in E a weight W(e)>=0; Solution: A spanning tree for G, i.e. a subset T of E s.t. (V,E) is a tree Measure : W(T) (i.e. Sum {W(e): e in C}) +----------------------------------------------------+ | The "Local-Ratio Theorem" (oriented for MST) | +----------------------------------------------------+ | If T is MST w.r.t the weight function W1 | | and T is MST w.r.t the weight function W2 | | then T is MST w.r.t the weight function W1+W2 | +----------------------------------------------------+ Let epsilon = min {W(e): e in E} define W1(e) = epsilon for all e in E Q1: All spanning trees have same W1's weight. Why? The algorithm: iteratively subtract W1 as above. Induction hyp. implies that recusive call with W2=W-W1 would return a tree T which is MST w.r.t. W2. T (and any spanning tree) is MST w.r.t. W1 (see Q1). By the "Local-Ratio Theorem" T is MST w.r.t. W=W1+W2. Q2: What to do with zero weight edges? Q3: The above algorithm is equivalent to Kruskal's. Why?