拟阵的定义：
拟阵是一个序对(S,I),其满足以下条件：
- S是一个有限非空集合
- I是某些非空的S子集的集合（由于其中元素为集合，也可以称为集族），I中的元素称为S的独立子集。故而，可以定义I的子集为S的独立子集族，
- 遗传性，如果A是I中的元素，B是A的子集，则B是I的元素
- 变换性，如果A，B是I的元素，|A| < |B|，那么一定存在x∈B-A，使得AU{x} 是I中的元素
在理解上说，遗传性，使得I中的某个元素集合A，A的子集合都是I的元素。
拟阵的相关定义
- 扩张：设M=(S, I)是一个拟阵 , A是I的元素. 如果AU{x}是I的元素 , 且x!∈A, x称为A的一个扩张。
- 最大独立子集合：设M=(S, I)是拟阵, A是I的元素. 若A没有扩张, 则称A为最大独立子集合。
- 加权拟阵：设M=(S, I)是拟阵，如果存在一个权函数W，使得对于在S中的任意的元素x，W(x)是一个正数，则称M是加权拟阵，W可以扩展到S的任意子集合A，W(A) = ∑(x∈A)W(x)。
- 优化子集：拟阵M=(S,I)中具有最大权值W(A)的独立子集A，A∈I。
拟阵的有关性质
定理1：一个拟阵的所有最大独立子集合都具有相同大小。
证明：使用反证法以及定义中的变换性。
假设一个拟阵的所有最大独立子集合不具有相同大小，则，存在A，B是拟阵M的最大独立子集合， |A| < |B|. 根据M的交换性, 存在x∈B-A，使AU{x}是I的元素, A可以进行扩张这与A是M的最大独立子集合矛盾.
拟阵的实例：图拟阵
图拟阵的定义：
设 G=(V,E) 是一个无向图，由 G 确定的MG =(SG,IG)，其中各符号定义如下:
- SG是G的边集合 E
- IG={A|A是E的子集, (V, A)是森林}.
证明：MG =(SG,IG)是拟阵。
- 边集合E是一个非空有限集合
- 显然A是E的子集合，IG是E的子集合族，而对于E中的任意一个元素e，{e}是IG的元素，IG非空。
- MG满足遗传性，一个森林的边集的子集合仍然是一个森林，满足遗传性。
- MG满足变换性，设对于任意的IG的元素A,B， |A|<|B|. 如果B的任意一条边都包含在A的同一棵树中， 则B的边数不大于A的边数，与|A|<|B|矛盾. 于是，B必包含一条边(u,v)，(u,v)不在A的同一棵树中，则(u,v)必连接A的两棵不同树。 (V, AU{(u,v)})是森林，AU{(u,v)}是 IG的元素 . 于是, MG满足交换性。
参考连接