今天看到topcode上的一个题目，题解直接说是拟阵，然后就是一大通的证明。好奇的我今天就看了看拟阵的知识。
拟阵可以用来研究贪心算法，他是贪心算法的数学基础，可以这么说，一个问题如果他可以转换为拟阵，那么一定可以用贪心算法进行求解；但是并不是所有的可用贪心算法求解的问题都能转换为拟阵。——主要是用来求解最优问题。
相关资料：2007年国家集训队论文 浙江省杭州第二中学 刘雨辰的《对拟阵的初步研究》，论文讲的非常详细易懂。中学生能看懂的东西，我相信我一个大学生也应该能看懂，更何况，他都写成了论文，我就更可以看懂了。
拟阵中文又称矩阵胚，英文名matroid。1935年美国数学家Whitney首先提出了拟阵的概念。拟阵是他在研究线性无关时发现的。拟阵是组合优化与图论的重要内容，在近几十年得到了空前的发展，成为了一门博大精深的学科 ：。
定义：
一个拟阵是满足下列条件的一个序对 M=(S,L)：
（1）S是一个有穷集合(S is a finite set)；
（2）L是S的一个非空子集簇，即L是由S的子集作为元素构成的集合，且非空；
（3）如果B∈L，并且A包含于B，则有A属于L，称为遗传性；
（4）如果A∈L，B∈L并且|B|>|A|，则有一定存在一个x∈B-A，使得集合A并上{x}之后形成的集合仍属于L，该性质称为交换性。
我们来同步地看我们的两个实例：
对于部分背包问题，我们首先进行一步转化：将体积为V，单位价值为W的物品变成V个体积为1，价值为W的物品。这样物品就全是单位体积的了。我们可以定义这样一个M=(S,L) ：
1、 S是所有物品的集合
2、 
这个M显然满足子集系统的前两条件。根据L的定义，对任意x∈L，任意y∈x，满足|y|≤|x|≤MAX，有y∈L,因此M满足遗传性,是一个子集系统。对任意A∈L，B∈L，随意选取一个x∈B-A,令C=A∪x,显然有|C|=|A|+1≤|B|，所以M满足交换性。因此M也是一个拟阵。我们称M为背包问题的拟阵。
最小生成树问题是在无向图上进行的。因此考虑对于无向图，我们可以定义这样一个：
1、 S是边集E
2、 
公式输入太麻烦了，证明看开头给的那篇论文。
适宜用贪心方法获得最优解的许多问题，都可以归结为在加权矩阵中找出一个具有最大权值的独立子集问题。因为任意元素的权值都是正的，故找出的最优子集同时也是最大子集。下面是求带权拟阵最优子集的贪心算法。
GREEDY( M , W )
A<-空集
将S中的元素按照权值W大优先组织成一个优先队列。
While ( S不为空 )
x = GetMax( S ) ;
if ( A ∪ {x} ∈ I）
A = A ∪ {x} ;
return A
这个算法排序的时间为O(NlogN)，共判断N次，设判断复杂度为f(N)，则整个算法运行时间为O(NlogN+Nf(N))
GREEDY的后续操作就会找出M'中的一个具有最大权值的独立子集。而GREEDY的全部操作就可找出M的一个具有最大权值的独立子集。
很经典的东西，虽然acm不大考这个东西，但是还是好奇的了解一下吧，对贪心有了更深的理解，说不定哪天就用到了