查看“︁拟阵”︁的源代码

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

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

== 定义 ==
拟阵有很多等价的定义方式<ref name="oxley">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.</ref>。

===独立集===
就独立集来说, 一个有限的拟阵 <math>M</math> 是一个二元组 <math>(E,\mathcal{I})</math>, 其中 <math>E</math> 是一个 [[有限集]] (称之为 '''基础集''') ，<math>\mathcal{I}</math> 是一个由<math>E</math>的子集构成的 [[集族]] (称之为 '''独立集''') 它需要满足下面的条件:<ref name="w7-9">{{harvtxt|Welsh|1976}}, Section 1.2, "Axiom Systems for a Matroid", pp. 7–9.</ref>
# [[空集]] 是独立的, 也就是说, <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>的'''基'''，满足以下条件:<ref name="oxley"></ref>
# <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>的环路集，满足以下条件:<ref name="oxley"></ref>
# <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>的[[拟阵的秩|秩]]。

===闭包===


==参考资料==
{{Reflist}}

[[Category:闭包算子]]
[[Category:维度]]
[[Category:几何学]]
[[Category:对偶理论]]