拟阵

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

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

定义

拟阵有很多等价的定义方式^[1]。

独立集

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

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

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

基

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

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

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

环路

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

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

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

秩函数

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

闭包

参考资料

1. A standard source for basic definitions and results about matroids is Oxley (1992). An older standard source is Welsh (1976). See Bryzlawski's appendix in White (1986) pp.298–302 for a list of equivalent axiom systems.
2. Welsh (1976) harvtxt模板错误: 无指向目标: CITEREFWelsh1976 (帮助), Section 1.2, "Axiom Systems for a Matroid", pp. 7–9.