拟阵

拟阵是组合数学中的一个结构，是对向量空间中线性独立这一概念的概括与归纳。拟阵有许多等价的定义，其中最主要的几个定义分别是基于独立集、基底、环路、闭集、平坦、闭包算子和秩函数。

拟阵理论从线性代数和图论中借用了大量术语，主要是因为它是对这些领域中很多重要的核心概念的概括。拟阵理论在几何、拓扑学、组合优化、网络理论和编码理论中都有应用。

定义

拟阵有很多等价的定义方式。

独立集

就独立集来说, 一个有限的拟阵 $M$ 是一个二元组 $(E,{\mathcal {I}})$, 其中 $E$ 是一个 有限集 (称之为 基础集) ，${\mathcal {I}}$ 是一个由$E$的子集构成的 集族 (称之为 独立集) 它需要满足下面的条件:

1. 空集 是独立的, 也就是说, $\emptyset \in {\mathcal {I}}$. 换个说法就是, 至少有一个 $E$的子集是独立的, 即：${\mathcal {I}}\neq \emptyset$.
2. 每个独立集的子集是独立的, 即： 对于每个子集 $A'\subset A\subset E$, 如果 $A\in {\mathcal {I}}$ 则 $A'\in {\mathcal {I}}$. 有时我们称之为 遗传特性.
3. 如果 $A$ 和 $B$ 是 ${\mathcal {I}}$ 的两个独立子集,$A$ 比$B$有更多的元素, 则在$A$中存在一个元素，当其加入 $B$时得到一个比$B$更大独立子集. 有时我们称之为 扩充特性 或者叫 独立集交换特性.

头两个特性定义了一个公认的组合结构，叫做独立系统。

基

对于有限拟阵 $M$，若其基础集$E$的子集$B$是一个极大的独立集（即添加任何一个新的元素得到的子集都不是独立集），则将$B$称为一个基底（英文：basis）。拟阵的一种等价定义为二元组$(E,{\mathcal {B}})$，其中$E$ 是一个有限集，${\mathcal {B}}$ 是一个由基底构成的$E$的子集族，称为$M$的基，满足以下条件:

1. ${\mathcal {B}}\neq \emptyset$;（即至少存在一个基底）
2. 对于${\mathcal {B}}$中不同的集合$A,B$以及任一元素$a\in A-B$，存在元素$b\in B-A$使得$A\cup \{b\}-\{a\}\in {\mathcal {B}}$。（该条件被称为交换公理）

可以证明，一个有限拟阵的所有基底的元素个数都相同，这个数被称为拟阵的秩。

环路

对于有限拟阵 $M$，若其基础集$E$的子集$C$是一个极小的非独立集（即去掉其中任一元素得到的子集都是独立集），则将$C$称为一个环路（英文：circuit）。拟阵的一种等价定义为二元组$(E,{\mathcal {C}})$，其中$E$ 是一个有限集，${\mathcal {C}}$ 是一个由环路构成的$E$的子集族，称为$M$的环路集，满足以下条件:

1. $\emptyset \notin {\mathcal {C}}$；
2. 如果$C_{1},C_{2}\in {\mathcal {C}}$且$C_{1}\subseteq C_{2}$，则$C_{1}=C_{2}$；
3. 对于${\mathcal {C}}$中不同的集合$C_{1},C_{2}$以及元素$a\in C_{1}\cap C_{2}$，存在$C_{3}\in {\mathcal {C}}$使得$C_{3}\subseteq C_{1}\cup C_{2}-\{a\}$。

可以证明，基础集的一个子集是独立集当且仅当它不包含任一环路作为子集。

秩函数

类似线性代数基底的性质，拟阵的基底具有类似的性质：$M$的任意两个基底具有相同的元素个数。这个数字被称为拟阵$M$的秩。