拟阵

维基百科,自由的百科全书
跳到导航 跳到搜索

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

定义[编辑]

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

独立集[编辑]

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

  1. 空集 是独立的, 也就是说, . 换个说法就是, 至少有一个 的子集是独立的, 即:.
  2. 每个独立集的子集是独立的, 即: 对于每个子集 , 如果 . 有时我们称之为 遗传特性.
  3. 如果 的两个独立子集,有更多的元素, 则在中存在一个元素,当其加入 时得到一个比更大独立子集. 有时我们称之为 扩充特性 或者叫 独立集交换特性.

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

[编辑]

对于有限拟阵 ,其基础集的子集称为一个基底(英文:basis),如果它是一个极大的独立集(即添加任何一个新的元素得到的子集都不是独立集)。拟阵的一种等价定义为二元组,其中 是一个有限集, 是一个由基底构成的的子集族,称为,满足以下条件:[1]

  1. ;(即至少存在一个基底)
  2. 对于中不同的集合以及任一元素,存在元素使得。(该条件被称为交换公理)

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

环路[编辑]

对于有限拟阵 ,其基础集的子集称为一个环路(英文:circuit),如果它是一个极小的非独立集(即去掉其中任一元素得到的子集都是独立集)。拟阵的一种等价定义为二元组,其中 是一个有限集, 是一个由环路构成的的子集族,称为的环路集,满足以下条件:[1]

  1. 如果,则
  2. 对于中不同的集合以及元素,存在使得

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

秩函数[编辑]

闭包[编辑]

参考资料[编辑]

  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.
  2. ^ Welsh (1976), Section 1.2, "Axiom Systems for a Matroid", pp. 7–9.