拟阵的定义
拟阵(Matroid)一词最早于1935年被数学家Whitney使用，其是从矩阵的线性无关概念中提炼而来的，拟阵多种不同的等价定义，其基于子集系统的定义如下，第1～4定义了子集系统，拟阵是满足交换性质的子集系统：
1) 拟阵\(M\)是为二元组\((S,L)\)；
2) \(S\)是有限集合；
3) \(L\)是由\(S\)的符合下述性质的子集组成的有限非空集；
4) 遗传性质：对任意\(B\in L\)与\(A\subseteq B\)，都满足\(A\in L\)；
5) 交换性质：对任意\(A\in L\)与\(B\in L\)。若\(|A|<|B|\)，则存在\(x \in B-A\)，使\(A\bigcup\{x\} \in L\)；
在无向图\((V,E)\)上可定义图拟阵(Graphic Matroid)，图拟阵与拟阵等价，故图拟阵也可定义拟阵：
1) 图拟阵\(M_G\)为二元组\((S_G,L_G)\)；
2) \(S_G=E\)，即无向图的边集；
3) \(L_G=\{ A | A\subseteq E ~~且~~A是无环的 \}\)；
先证明关于森林的性质：“任意无根树森林\(F=(V_F,E_F)\)有\(|V_F|-|E_F|\)个树”。设\(F\)含\(t\)个无根树，且第\(i\)个树的顶点数与边数为\(v_i\)与\(e_i\)。由无根树性质\(\sum_i e_i =\sum_i (v_i-1)\)。故\(|E_F|=\sum_i e_i =\sum_i (v_i-1)= |V_F|-t \)，证毕。
接下来证明图拟阵与拟阵等价，因为无环子图删边仍是无环子图，故\(M_G\)满足遗传性。然后证明其满足交换性，设\(G_A=(V,A),G_B=(V,B) \)为\(G\)的森林，且\(|A|<|B|\)。那么\(G_A\)含\(|V|-|A|\)个树，\(G_B\)含\(|V|-|B|\)个树，\(G_B\)的树的数目更少，故\(G_B\)中存在树\(T\)，其包含能连通\(G_A\)不同两个树的边，把该边加入\(G_A\)不会形成环，交换性得证。
拟阵的相关定义
拟阵\(M=(S,L)\)上的独立集的性质：
1) 独立集：集合\(L\)中的元素，空集是独立集；
2) 独立集的扩展：对于独立集\(A\)，若存在\(x \notin A\)，使得\(A\bigcup \{x\} \in L\)，那么称\(x\)为\(A\)的“扩展”；
3) 最大独立集：若独立集\(A\)不存在“扩展”，那么\(A\)为一个最大独立集，拟阵的所有最大独立集元素数相等；
加权拟阵的定义：
1) 加权拟阵：将拟阵\(M=(S,L)\)关联到权重函数\(w\)，其定义域为\(S\)，值域为正实数。那么称拟阵\(M\)是加权的。通过求和可以把权重函数推广到任意独立集\(A\)，其中\(w(A)=\sum_{x \in A} w(x)\)。例如对于图拟阵，很多时候需要把加权函数设定为边或独立集的权重函数；
2) 最优子集：加权拟阵中使得权重最大的独立集；
拟阵与贪心策略
拟阵可用于解决贪心策略问题。虽然其不能解决活动选择问题、哈夫曼编码等问题。但其给出相当数量的贪心问题的一般解决方法，这些问题可形式化为求加权拟阵的最优子集。下面论证拟阵与贪心算法策略的关系：
a) 拟阵的贪心选择性质：设\((S,L)\)是权重函数为\(w\)的加权拟阵，\(S\)为按权重排序的降序序列。若存在\(x\)为\(S\)中排最前面的满足\(\{x\}\)为独立集的元素，那么\(S\)存在包含\(x\)的最优子集；
证明：假设存在符合要求的\(x\)。设\(B\)为不包含\(x\)的最优子集，\(A\)为独立集\(\{x\}\)。然后反复从\(B-A\)寻找元素加入\(A\)，直到\(|A|=|B|\)，根据交换性质最终\(A\)仍是独立集，且\(A=(B-\{y\})\bigcup \{x\}\)，即\(A\)与\(B\)仅有一个元素互异(\(x\)与\(y\))。然后考虑权重函数，由于\(w(x)>=w(y)\)所以\(w(A)>=w(B)\)，由于\(B\)为最优子集故\(A\)为最优子集。
b) 设\((S,L)\)为拟阵，对于\(x\in S\)，若其不是空集的“扩展”，那么其不是任何独立集的“扩展”；
证明：上述命题是“设\((S,L)\)为拟阵，对于\(x\in S\)，若\(x\)是某个独立集的扩展，那么其为空集的扩展”的逆否命题。然后证明该命题，设\(x\)是\(A\)的扩展，则\(A\bigcup \{x\}\)为独立集，根据遗传性\(\{x\}\)为独立集，所以\(x\)为空集的扩展。
c) 拟阵的最优子结构性质：设\(M=(S,L)\)是权重函数为\(w\)的加权拟阵，\(S\)为按权重排序的降序序列。设\(x\)为上述通用贪心算法选出的第一个元素，那么寻找一个含\(x\)的最优子集等价于从拟阵\(M’=(S’,L’)\)寻找任意一个最优子集(\(M’\)称为\(M\)在\(x\)上的收缩)，其中\(S’=\{ y ~| \{x,y\} \in L \}~,~L’=\{ B ~| B\subseteq (S-\{x\}) 且 B\bigcup \{x\} \in L \}\)；
证明：容易证明\(M’=(S’,L’)\)是拟阵，因为假设\(M’\)不满足遗传性与交换性可以比较容易得出\(M\)不是拟阵的矛盾。设\(A\)为\(M\)的最优子集，且\(x\in A\)。\(A’=A-\{x\}\)显然为\(M’\)的独立集。反之任何\(M’\)的独立集\(B’\)都使得\(B’\bigcup \{x\}\)为\(M\)的独立集，这使得\(M\)与\(M’\)的最优子集权重差为\(w(x)\)。故\(M’\)的任意最优子集加上\(x\)后为\(M\)的最优子集。
拟阵的通用贪心算法
定义拟阵\(M=(S,L)\)上的通用贪心算法(求出一个\(M\)的最优子集)的流程：
1) 把集合\(S\)按权重排为降序序列；
2) 初始化\(A\)为空集；
3) 遍历\(S\)序列元素(计为\(x\))，若\(A\bigcup x \in L\)，则\(A = A\bigcup x\)；
下面论证该流程将选出其中一个最优子集。首先明确循环最先选出的元素\(x\)与(a)选出的元素相同，再根据(b)可知循环最开始跳过的元素不存在于任何最优子集。当循环选出\(x\)后，问题化为关于拟阵\(M’\)(\(M\)在\(x\)上的收缩)的子问题。排在\(x\)前的元素\(x’\)不可能存在于\(M’\)的某个最优子集\(A’\)中，否则将导致\(A’\bigcup \{x’\}\)可作为\(M\)的最优子集，这与最先选择\(x\)矛盾。于是对于\(M’\)接下来的循环选出的元素与(a)选出的相同。如此循环下去将得到一个最优子集。