拟阵
拟阵是组合数学中的一个结构，是对向量空间中线性独立这一概念的概括与归纳。拟阵有许多等价的定义，其中最主要的几个定义分别是基于独立集、基底、环路、闭集、平坦、闭包算子和秩函数。
拟阵理论从线性代数和图论中借用了大量术语，主要是因为它是对这些领域中很多重要的核心概念的概括。拟阵理论在几何、拓扑学、组合优化、网络理论和编码理论中都有应用。
定义[编辑]
拟阵有很多等价的定义方式[1]。
独立集[编辑]
就独立集来说, 一个有限的拟阵 <math>M</math> 是一个二元组 <math>(E,\mathcal{I})</math>, 其中 <math>E</math> 是一个 有限集 (称之为 基础集) ，<math>\mathcal{I}</math> 是一个由<math>E</math>的子集构成的 集族 (称之为 独立集) 它需要满足下面的条件:[2]
- 空集 是独立的, 也就是说, <math>\emptyset\in\mathcal{I}</math>. 换个说法就是, 至少有一个 <math>E</math>的子集是独立的, 即：<math>\mathcal{I}\neq\emptyset</math>.
- 每个独立集的子集是独立的, 即： 对于每个子集 <math>A'\subset A\subset E</math>, 如果 <math>A\in\mathcal{I}</math> 则 <math>A'\in\mathcal{I}</math>. 有时我们称之为 遗传特性.
- 如果 <math>A</math> 和 <math>B</math> 是 <math>\mathcal{I}</math> 的两个独立子集,<math>A</math> 比<math>B</math>有更多的元素, 则在<math>A</math>中存在一个元素，当其加入 <math>B</math>时得到一个比<math>B</math>更大独立子集. 有时我们称之为 扩充特性 或者叫 独立集交换特性.
头两个特性定义了一个公认的组合结构，叫做独立系统。
基[编辑]
对于有限拟阵 <math>M</math>，若其基础集<math>E</math>的子集<math>B</math>是一个极大的独立集（即添加任何一个新的元素得到的子集都不是独立集），则将<math>B</math>称为一个基底（英文：basis）。拟阵的一种等价定义为二元组<math>(E,\mathcal{B})</math>，其中<math>E</math> 是一个有限集，<math>\mathcal{B}</math> 是一个由基底构成的<math>E</math>的子集族，称为<math>M</math>的基，满足以下条件:[1]
- <math>\mathcal{B} \ne \emptyset </math>;（即至少存在一个基底）
- 对于<math>\mathcal{B}</math>中不同的集合<math>A,B</math>以及任一元素<math>a\in A-B</math>，存在元素<math>b\in B-A</math>使得<math>A\cup \{b\}-
\{a\}\in \mathcal{B}</math>。（该条件被称为交换公理）
可以证明，一个有限拟阵的所有基底的元素个数都相同，这个数被称为拟阵的秩。
环路[编辑]
对于有限拟阵 <math>M</math>，若其基础集<math>E</math>的子集<math>C</math>是一个极小的非独立集（即去掉其中任一元素得到的子集都是独立集），则将<math>C</math>称为一个环路（英文：circuit）。拟阵的一种等价定义为二元组<math>(E,\mathcal{C})</math>，其中<math>E</math> 是一个有限集，<math>\mathcal{C}</math> 是一个由环路构成的<math>E</math>的子集族，称为<math>M</math>的环路集，满足以下条件:[1]
- <math>\emptyset \notin \mathcal{C}</math>；
- 如果<math> C_{1},C_{2}\in \mathcal{C}</math>且<math> C_{1}\subseteq C_{2}</math>，则<math> C_{1} = C_{2}</math>；
- 对于<math>\mathcal{C}</math>中不同的集合<math>C_{1},C_{2}</math>以及元素<math>a\in C_{1}\cap C_{2}</math>，存在<math>C_{3}\in \mathcal{C}</math>使得<math>C_{3}\subseteq C_{1}\cup C_{2} - \{a\}</math>。
可以证明，基础集的一个子集是独立集当且仅当它不包含任一环路作为子集。
秩函数[编辑]
类似线性代数基底的性质，拟阵的基底具有类似的性质：<math>M</math>的任意两个基底具有相同的元素个数。这个数字被称为拟阵<math>M</math>的秩。
闭包[编辑]
参考资料[编辑]
- ^ 1.0 1.1 1.2 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.
- ^ Welsh (1976), Section 1.2, "Axiom Systems for a Matroid", pp. 7–9.