1. (9pts) The following is the proposition we used in EX2_22 and its proof Proposition: Let G=(V,E) be an edge-weighted graph, and T be any minimum spanning tree of G. The algorithm MST(G) can return T with some allowed choices of the next minimum edge e Proof: It suffices to show the following invariant for every given non-negative integer ms Vl 1. Invariant: There exists an edge set calc S T that can be constructed by MST(G) so that m= I calc I We show by induction on m. The base case m-0 is clearly true; T includes calc when calc is an empty set. Assume true for m and prove true for m+1. Let: o calc be a subset of T that is constructed MST(G) so that |calcl-m, o ECE be the set of edges, each of which grows a connected component in calc, and minweight = min w(e) where w: E Z+ is the weight function on G It further suffices to prove that: eea (A) there exists an edge e E E' in the tree T such that w(e) = minWeight The statement (A) is true otherwise(B) MSTIG) can choose such an edge e as the next choice. Therefore, calc U (e) can be constructed by MST(G), whose size is m+1. This completes the induction step The algorithm Answer the three questions. Explain why the invariant for all ms |V -1 is sufficient to prove the proposition. Write your answer in at least 3 and less than 15 lines. a. b. Explain why the statement (A) is sufficient to prove the induction step. Write your answer in at least 3 and less than 15 lines Fill in the blank (B) justifying the answer Answer for (B): (write your answer as a part of the proof, in one or two lines) Justification: (Explain why it's correct in at least 3 and less than 15 lines.) c. 1. (9pts) The following is the proposition we used in EX2_22 and its proof Proposition: Let G=(V,E) be an edge-weighted graph, and T be any minimum spanning tree of G. The algorithm MST(G) can return T with some allowed choices of the next minimum edge e Proof: It suffices to show the following invariant for every given non-negative integer ms Vl 1. Invariant: There exists an edge set calc S T that can be constructed by MST(G) so that m= I calc I We show by induction on m. The base case m-0 is clearly true; T includes calc when calc is an empty set. Assume true for m and prove true for m+1. Let: o calc be a subset of T that is constructed MST(G) so that |calcl-m, o ECE be the set of edges, each of which grows a connected component in calc, and minweight = min w(e) where w: E Z+ is the weight function on G It further suffices to prove that: eea (A) there exists an edge e E E' in the tree T such that w(e) = minWeight The statement (A) is true otherwise(B) MSTIG) can choose such an edge e as the next choice. Therefore, calc U (e) can be constructed by MST(G), whose size is m+1. This completes the induction step The algorithm Answer the three questions. Explain why the invariant for all ms |V -1 is sufficient to prove the proposition. Write your answer in at least 3 and less than 15 lines. a. b. Explain why the statement (A) is sufficient to prove the induction step. Write your answer in at least 3 and less than 15 lines Fill in the blank (B) justifying the answer Answer for (B): (write your answer as a part of the proof, in one or two lines) Justification: (Explain why it's correct in at least 3 and less than 15 lines.) c
