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