
Greedy Algorithm Proofs
1) Let M be a matroid and w: E(M)>R. When the greedy algorithm is applied to the pair (I(M),w) each application of the step involves a potential choice. Thus in general, there are a number o different sets that the algorithm can produce as solutions to the optimization problem (I(M),w). Let Bg be the set o such sets and Bmax be the set of maximumweight bases of M. Prove Bg=Bmax
2) Let M be a matroid and w: E(M) > R be a onetoone. function. Prove that M has a unique basis of maximum weight.
Thanks for any help !