拟阵定义

一个拟阵是满足下列条件的一个序对 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，该性质称为交换性。

相关定理

1、如果G=（V,E）是一个无向图，那么M=（S,L）是个拟阵。其中S是图G的边集E，而L则是由这样的E的子集构成的：A是E的子集，并且A是无回路的，则A属于L。

2、某一拟阵中的所有最大的独立子集的大小都是相同的。拟阵M=（S,L）中L的每一个元素都是S的独立子集。

拟阵来源

“拟阵”这个词是由Hassler Whitney最早开始使用的。他曾研究矩阵拟阵，其中S是给定矩阵的各个行，如果这些行在通常意义下是线性无关的，则他们是独立的。

拟阵应用

拟阵可以用来研究贪心算法，他是贪心算法的数学基础，可以这么说，一个问题如果他可以转换为拟阵，那么一定可以用贪心算法进行求解；但是并不是所有的可用贪心算法求解的问题都能转换为拟阵。

主要是用来求解最优问题。

相关图书

《拟阵论》

相关研究