MST:The abstract problem Input:A connected weighted graph 4 1 口G=(V,E),w:E→R. Output:A spanning tree 4 6 3 with min total weight. 2 2 ▣A spanning tree whose weight is the minimum of 2 3 that of all spanning trees. Any algorithm? 6MST: The abstract problem ◼ Input: A connected weighted graph ❑ 𝐺 = (𝑉, 𝐸), 𝑤: 𝐸 → ℝ. ◼ Output: A spanning tree with min total weight. ❑ A spanning tree whose weight is the minimum of that of all spanning trees. ◼ Any algorithm? 4 1 4 3 5 4 2 2 2 3 3 2 6 6