拟阵

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

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

定义

拟阵有很多等价的定义方式^[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), Section 1.2, "Axiom Systems for a Matroid", pp. 7–9.