(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?