拟阵

维基百科,自由的百科全书
跳转至: 导航搜索

拟阵是一个数学结构,是对(线性)独立的概括与归纳。常用于排列组合图论等方面。

定义[编辑]

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

独立集[编辑]

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

  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. 如果 AB\mathcal{I} 的两个独立子集,AB有更多的元素, 则在A中存在一个元素,当其加入 B时得到一个比B更大独立子集. 有时我们称之为 扩充特性 或者叫 独立集交换特性.

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


一个关于有限集合 E 的拟阵是一个 (E,U) 对,U 是一个系统E的子集,满足下列条件:

  1. \empty \in U
  2. A \subseteq B , B \in U \Rightarrow A \in U
  3. A ,B \in U \mid A \mid < \mid B \mid \Rightarrow  \exists x \in B \setminus A A \cup {x} \in U
\mid A \mid集合A的基数。例如 A=\{a,b,c\}\mid A \mid = 3

参考资料[编辑]

  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.