[learning notes] matroid

For this kind of question , There is a unified solution , namely According to the weight from big to small greed , Until you can't choose .

Common matroid models ：

• The items are $(v_i,w_i)$ Two attributes , Pick a collection $S$ , seek $\max ({\sum }_{i\in S}{v}_i)$ , among $S$ Any nonempty subset attribute XOR and $\ne 0$ .

M(E,I) in E Express n A collection of items , I Indicates that any non empty subset attribute and $\ne 0$ Collection of items .

• MST .

M(E,I) in E Represents a collection of edges , I Represents a set of edges that satisfy no ring .

Because we're going to MST , So consider $w(u,v)=w_0-w(u,v)$ , Note that what we are looking for must be a spanning tree , Therefore, it is necessary to avoid negative weight of edges .（ Otherwise, you can choose not to ）.

• Minimum base ring spanning tree .

Prove slightly . It is also greedy to sort by edge , Proof can disprove （ The proving process of matroids is rather troublesome ）.

• Yes $n$ Vector $(a_1,a_2,..,a_m)$ , Each vector has a weight $va{l}_i$ , Select a set of linearly independent vectors S , In the meet |S| Under the greatest premise $\min ({\sum }_{i\in S}va{l}_i)$ .

This problem can be translated into solving $\max ({\sum }_{i\in S}va{l}_i)$ , Because the weight is positive , therefore S It must be the basis of the original matroid , And because the basis size of matroids is the same （ Otherwise, it contradicts exchangeability ）, So directly $va{l}_i$ Sort from small to large greedy .