拟阵

数学术语

在组合数学中，拟阵是一个对向量空间中线性独立概念的概括与归纳的数学结构。拟阵有许多等价的定义方式，最常见的定义方式是用独立集，基，圈，闭集合，闭平面，闭包算子或秩函数。

来源

“拟阵”这个词是由Hassler Whitney最早开始使用的。他曾研究矩阵拟阵，其中S是给定矩阵的各个行，如果这些行在通常意义下是线性无关的，则他们是独立的。

有限拟阵定义

有限拟阵有很多等价的定义方式。

独立集

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

1. 空集是独立的, 也就是说，。换个说法就是, 至少有一个E的子集是独立的, 即：。

2. 每个独立集的子集是独立的, 即：对于每个子集，如果则 . 有时我们称之为遗传特性。

3. 如果A和B是的两个独立集，A比B有更多的元素, 则在A中存在一个元素，当其加入B时得到一个比B更大独立集。有时我们称之为扩充特性或者叫独立集交换特性。

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

基与圈

Bases and circuits：E 对于一个基础集的子集，如果它不是独立的，那么我们称它为不独立集。对于拟阵M中的一个独立集A，如果加入基础集E中任何一个元素后，A都变为不独立集，那么我们称A是最大独立集，也叫做拟阵的基。对于拟阵M中的一个不独立集B，如果它的任何一个真子集都是独立的，那么我们称B是最小不独立集，也叫做拟阵的圈。之所以这里出现了圈，是因为拟阵中的圈正好与图论中图的环相对应。

独立集，基或圈都能完整地描述拟阵：一个集合是独立的当且仅当它不是不独立集，当且仅当它是基的一个子集，当且仅当它不包含任何圈。不独立集的集合，基的集合，圈的集合都拥有能作为拟阵公理的性质。例如，我们可以用元组(E， )定义拟阵M，其中E是一个有限集，是E的子集的集合，我们称之为“基集”，有以下性质：

1. 不是空集。

2. 如果A和B是中不同的元素，并且，那么存在一个元素，使得（这里的斜杠表示差集，该性质称为基交换性质）。

根据基交换性质我们可以得出结论，中没有一个元素是其它元素的真子集。

秩函数

Rank functions：两个拟阵的基具有相同数量的元素，它是拟阵理论的一个基础结论，这与线性代数中的基公理类似，基的元素的个数称为似阵的秩。如果M是一个E上的拟阵，并且A是E的一个子集，那么A上的拟阵可以通过把一个A的子集当作是独立集来定义当且仅当这个子集在M中是独立集。这个性质使得我们可以讨论子拟阵和E中任何子集的秩。子集A的秩通过秩函数来定义，它有以下几种性质：

1. 秩函数的值总是非负的。

2. 对于任意E的子集A，有。

3. 对于E的任意两个子集A 和B ，有。这意味着秩函数是一个子模函数。

4. 对于任意集合A和元素x，有。从第一个不等式我们可以得到更一般的结论，如果，那么。这意味着秩函数是一个单调函数。

这些属性可以被用来替换有限拟阵的定义：如果(E,r)满足这些属性，那么E上的拟阵独立集可以定义为E的子集A，且A满足。

子集A的元素个与其秩的差叫作A的零化度(nullity)或补秩(corank)。它是从A中移除元素使得A成为独立集的最小移除数量。E在拟阵M上的零化度叫做M的零化度或M的补秩。

闭包算子

Closure operators：设M是有限集E上的一个拟阵，其秩函数有上述定义。E的子集A的闭包cl(A)的定义如下：

闭包算子拥有如下性质，其中表示幂集。

1. 对于E的所有子集X，有。

2. 对于E的所有子集X，有。

3.对于E的所有子集X和Y，如果，那么。

4. 对于E的所有元素a和b，所有子集Y，如果那么。

前三个性质是闭包算子的定义，第四个性质叫做Mac Lane–Steinitz交换性质。这些性质也可以当作是拟阵的另一个定义，每个遵守这些性质的决定一个拟阵。

平面

Flats：我们称闭包等于自身的集合是封闭的，这样的集合也叫做拟阵的平面或子空间。如果一个集合的秩达到了最大，那么这个集合是封闭的，也就是说往该集合中加入任何元素都不会使它的秩变大。拟阵上的封闭的集合有以下性质：

1.E是封闭的。

2. 如果S和T都是平面，那么也是一个平面。

超平面

Hyperplanes：在一个秩为r的拟阵中，秩为r-1的平面称为超平面，它是平面的最大真子集，也就是说超平面的唯一父集是E，它拥有拟阵的所有元素。超平面也叫做补原子(coatom)，补原子是一个E的一个不能生成M子集，但往它加入任何元素都可以产生生成集。

拟阵的超平面系拥有以下属性，它也被认为是拟阵的另一个公理。

1.超平面系中不存在不同的使得的X和Y，也就是说超平面是一个Sperner系。

2.对于每个和不同的，如果，那么存在，并且有。

样例

均匀拟阵

Uniform matroids：设E是一个有限集，k是一个自然数。通过将E的每一个k-元素子集作为一个元素，我们可以定义一个关于E的拟阵。这被称为秩为k的均匀拟阵。秩为k的，有n个元素的均匀拟阵记为。秩大于等于2的所有均匀拟阵都是平凡的。n个点的秩为2的均匀拟阵被称作n点线。一个拟阵是均匀的，当且仅当它没有大小小于一加其秩的圈。均匀拟阵的直和称为分区拟阵(partition matroids)。

在均匀拟阵中，每一个元素都是一个循环(loop)，在均匀拟阵中，每一个元素都是一个联合循环(coloop)。这两种类型的拟阵的直和是一个分区拟阵，其中的每个元素都是循环或者联合循环，被称为离散拟阵(discrete matroids)。离散拟阵的一个等价定义是：E的每一个非空真子集都是一个分割。

拟阵与线性代数

拟阵理论主要来自于对向量空间中线性无关的维度的深层次属性的考量。对于这种方式定义的拟阵，有两种表示方法：

如果E是向量空间V的任意有限子集，通过将E中的线性无关子集作为M的元素，我们在E上定义拟阵M。这个拟阵的无关集合性质遵循斯坦尼茨交换定理。如果M是一个通过这种方式定义的拟阵，我们称E表示M。这种类型的拟阵被称作向量拟阵(vector matroids)。以这种方式定义的拟阵的一个重要的例子是法诺拟阵(Fano matroids)，是由法诺平面(Fano Plane)衍生而来的秩为3的拟阵。它是一个其元素可以表示为有限域GF(2)上的三维向量空间中的七个非零的点的线性拟阵。然而，在GF(2) 上用无法用实数近似表达法诺拟阵。

由某个域中的元素组成的矩阵A，由其列组成的集合可以形成一个拟阵M。拟阵中线性相关的列的集合，即是作为向量线性相关的向量。这个拟阵被称为A的列拟阵，也称为A表示M。例如，法诺拟阵可以表示为一个3*7的0-1矩阵。列拟阵是向量拟阵的另一种叫法，然而在进行矩阵表示时，这种表达方式更常用。

一个等价于向量拟阵的拟阵，尽管其表示可能不同，被称为可表示的或者线性的。如果在域F上，拟阵M等价于一个向量拟阵，我们称F上M是可表示的。特别地，M是可实数表示的如果它在实数域上是可表示的。例如，尽管一个图拟阵是以图的角度表示的，它也可以通过其他域上的向量来表示。拟阵理论的一个基本问题是在给定的域F刻画其可表示的拟阵的特征。Rota推论给出了有限域上的可能的刻画，迄今的主要成果是二项拟阵的特征。

一个常规拟阵(regular matroid)是在所有域上都可表示的拟阵。Vámos拟阵是在任何域上都不可表示的拟阵的一个简单例子。

拟阵与图理论

拟阵理论的另一个来源是图理论。

每一个有限图G都以以下方式给出一个拟阵M(G)：将图G中的所有边作为集合E，当且仅当一个边构成的集合是森林时，认为其是独立的；也就是说，当且仅当其不包含简单环路。那么M(G)被称作一个环拟阵。以这种方式构造的拟阵为图拟阵(graphic matroids)。并非每个拟阵都是图拟阵，但是所有三个元素组成的拟阵都是图拟阵。每个图拟阵都是常规拟阵。

后来人们在图结构中发现了很多拟阵：双环拟阵由独立性定义为至多包含一个环的连通子集构成。

在任何有向图或无向图G中，记E和F是两个不重合的顶点集。在集合E中，定义子集U是独立的，如果从F到U有|U|条顶点不相交路径。这种E上定义的拟阵称为gammoid：一个严格的gammoid是E为G的全部顶点的集合。

在一个二分图G=(U, V, E)中，我们可以定义拟阵：元素为U中的顶点，独立子集为图中顶点匹配的集合。这种拟阵被称为transversal matroid，是gammoid的一个特例。

拉曼图形成了二维的坚固拟阵，这种拟阵是结构稳定的。

设G是一个连通图，E是它的边集。记I是E的满足以下条件的子集F的集合：G-F是连通图。那么是一个拟阵，称为G的bond matroid。注意秩函数r(F)是边集F产生的子图中的最小环的个数。

拟阵与域扩张

拟阵理论的第三个来源是域理论。

域的一个扩张可以给出一个拟阵。假设F和K是K包含F的两个域。设E是K的任意有限子集。定义E的子集S是代数独立的如果域扩张F(S)的超越次数等于|S|。

与这种定义下的拟阵等价的拟阵被称作代数拟阵(algebraic matroid)。刻画代数拟阵的问题非常困难，相关知识很少。Vámos拟阵是一个非代数拟阵的例子。

基本构造

有很多种标准的方式能够从已有的拟阵中构造新的拟阵。

对偶

Duality：如果M是一个有限拟阵，我们可以定义其正交拟阵或者对偶拟阵，通过使用相同的原始集合，而一个集合在中当且仅当其补集在M中。不难验证是一个拟阵，而且的对偶拟阵是M。

对偶拟阵也可以通过其他定义拟阵的方式来很好的描述，比如：

中的一个集合是独立的，当且仅当它的补集在M中是非独立的

中的一个集合是环，当且仅当他的补集在M中是联合原子性的

对偶矩阵的秩函数是

根据库拉托夫斯基定理的拟阵版本，图拟阵的对偶拟阵也是图拟阵，当且仅当M是平面图的图拟阵。这种情况下，M的对偶拟阵是G的对偶图的拟阵。特定域F上可表示的向量拟阵的对偶拟阵在F上也是可表示的。中的顶点，独立子集为图中顶点匹配的集合。这种拟阵被称为transversal拟阵的对偶拟阵也是严格的gammoid，反之亦然。

极小元

限定的对偶操作是缩减。如果T是E的子集，M的T缩减，记做M/T，是原始集合E-T的拟阵，其秩函数是。在线性代数中，这对应着由T中的向量与E-T的向量的像形成的商空间。

由经过一些列的限制和缩减操作得到的拟阵N称为M的一个极小元。我们称M包含一个极小元N。很多重要的拟阵系都可以用不属于此系的极小元-最小值拟阵来刻画，这些拟阵称为禁止拟阵或排除拟阵。

和与并

Sums and unions：设M是原始集合为E的拟阵，设N是原始集合为F的拟阵。M和N的直和是原始集合为E和F的不相交并集的拟阵，其独立集合是M和N的独立集合的不相交并集。

M和N的并，是原始集合为E和F的并集的拟阵，它的独立集合是M和N的独立集合的并集。通常“并”在E=F时使用，但这个假设不是必要的。如果E和F是不相交的，M和N的并即是其直和。

相关术语

设M是由元素集合E构成的拟阵。

E可能被称作M的基础集。它的元素可能被称作M的点。

一个E的子集涵盖了M，如果M的闭包是F。一个集合被叫做涵盖了一个封闭集合K，当它的闭包是K，拟阵的周长（girth）是它最小的圈或者独立子集的大小。

一个组成了M的单个元素圈的元素称之为环。同等的，一个元素是一个环，当它不属于任何基（basis）。

一个不属于任何圈的元素被成为一个联合环或者峡（isthmus）。同等的，一个元素是个联合环，当它属于每一个基（basis）。环和联合环是互相对偶。

如果两个元素集合{f,g}是M的一个圈，那么f和g在M中是平行的。

一个拟阵被称作是简单的，当它没有包含1或2个元素的圈。也就是说，这个拟阵没有任何环或者没有平行元素。这个意义也被组合集合学使用。一个简单拟阵的获得方法是从另外一个拟阵M中删除所有的环和从每个二元圈中删除一个元素直到没有留下二元圈为止，这个过程被成为M的简化。一个拟阵是联合简单的，当它的对偶拟阵也是简单的。

一个圈的并操作有时候也被称作M的环。一个环因此是一个对偶拟阵的平面（flat）的补（此处的使用跟在图理论中通常的圈定义是冲突的）。

一个M的分隔符是S的一个子集，满足。一个真或者非平凡的分隔符是既不是M又不是空集的分隔符。一个不可归约的分隔符是没有包含任何非空的分隔符的分隔符。不可归约的分隔符划分了基础集E。

一个不能被直接写成两个非空拟阵直接相加结果的拟阵，或者同等的，没有真分隔符，被称为相连，或者不可归约。一个拟阵被相连的，当且仅当它的对偶是相连的。

一个最大的不可归约的M的子拟阵被称为M的分量。一个分量是从M到一个不可归约的分隔符的约束，相反的，从M到一个不可归约的分隔符的约束是一个分量。一个分隔符就是所有分量的是并。

一个拟阵M被称作帧拟阵，当它或者一个包含有它的拟阵，有一个基（basis）因此所有的M的点在基（basis）元素对的交点的线上被包含。

一个拟阵被称为平铺矩阵，当它的所有圈有着至少等于它的秩的大小。

一个拟阵多胞形是基于M的指标向量的凸包。

应用

拟阵可以用来研究贪心算法，他是贪心算法的数学基础，可以这么说，一个问题如果他可以转换为拟阵，那么一定可以用贪心算法进行求解；但是并不是所有的可用贪心算法求解的问题都能转换为拟阵。

主要是用来求解最优问题，是组合优化问题的有力工具。

算法

贪心算法

一个带权拟阵是一种带有映射函数，将其元素映射到非负实数上的拟阵。一个元素的子集的权重被定义为在子集上的所有元素权重之和。贪心算法可以被用于找到一个拟阵的最大权重基，通过从空集开始，迭代地一次添加一个元素，在每一步中从所有能够保持增广集独立性的元素中选择一个最大权重的元素。这个算法不需要知道任何有关拟阵定义的细节，只要通过独立定义，即测试一个集合是否是独立的子例程来跟拟阵打交道。

一个优化算法可能被用来表示拟阵的特点：如果一个集合的簇F，在取子集的情况下，具有这样的性质，不管集合权重是多少，贪心算法从簇中找到最大权重的集合，那么F一定是一个拟阵的独立子集的簇。

拟阵的概念已经被推广在允许其他类型的集合上，通过贪心算法获得优化解决方案。

拟阵划分

拟阵划分问题是指，把一个拟阵当中的元素划分到尽可能少的独立子集当中，拟阵打包问题是找到尽可能多的不相交生成集。这两者都可以在多项式时间内解决，可以被推广到计算秩或者找到拟阵和中的一个最大独立子集问题中。

拟阵相交

两个或者更多的拟阵相交是在每个拟阵中的集合系都同时独立。找到在两个拟阵的交中最大集，或者最大带权集的问题是在多项式时间可得到结果，并提供了一个解决许多其他重要的组合优化问题的方法。比如，在二分图中的最大匹配问题可以被表述为两个划分拟阵的交的问题。然而，在三个或者更多拟阵的交中找到最大集的问题是NP完全的。

拟阵软件

两个用于做拟阵运算的单机系统是Kingan的Oid和Hlineny的Macek。他们两者都是开源包。Oid是一个交互式的，可扩展的软件系统，被用于拟阵实验。Macek是一个由许多工具和例程构成的软件系统，在可表示的拟阵上可以高效地进行组合计算。

SAGE是一个开源的数学软件系统，包括了拟阵的包。

无限拟阵

无限拟阵远远比有限拟阵复杂，在很长一段时间内，业界存在很多合理的有用的定义，但没有一个能概括有限拟阵的所有重要性质的理论。例如，在无限拟阵中，似乎没有基，圈和对偶等概念。

无限拟阵最简单的定义是需要有限的秩，也就是说E的秩是有限的。除了对偶性之外，这个理论与有限拟阵相似，因为有限秩的无限拟阵的对偶不存在有限的秩。有限秩的拟阵包括有限维度向量空间，域扩张和有限超越次数的每个子集。

一个具有限性质的拟阵有如下性质：

也就是说，每个非独立集包括一个有限的非独立集。

无限拟阵的独立性质有以下几个公理：

1. 空集是独立的。

2. 每个独立集的子集是独立的。

3. 对于每个非最大独立集和最大独立集，如果，那么是独立的。

4. 对于基空间的每个子集，每个的独立子集可以扩展成的最大独立子集。

在这些公理存在的前提下，每个拟阵都有一个对偶。