Consider the minimum spanning tree (MST) problem. Namely, lets say given a connected graph G - (V, E) with weights w ER, find a spanning tree T E minimizing ETw(e). The generalization to a weighted matroid M (U,w) with w : U R is to find a basis B-U so as to minimize Xe) (a) Why is the MST (or its generaliztion to a minimum weight ba- sis) problem equivalent to the maximium weight spanning tree problem (resp. to maximize EBw(e))? imum weight basis in a matroid M-(U, w) Let m = r(M) where r(M) is the rank of M While |S|m (b) Consider the following reverse greedy algorithm for finding a max remove from S a minimum weight element r such that End While Claim: The resulting S will be a maximum weight basis Restate the reverse greedy algorithm for the minimum (or maxi- r(S \ {z)) = m mum) spanning tree problem c) Prove that the reverse greedy algorithm will always produce a maximum weight basis in a matroid