【理论学习】拟阵

发表于 分类于

为什么要有拟阵？

我们先不说拟阵是什么，而说一下为什么拟阵这个东西会出现。

在线性代数里，我们有“线性无关”这个概念。但它是用于矩阵中的向量组的。

数学家（比如1935年的Hassler Whitney）想把“线性无关”这个概念以一种特别一般的形态抽象出来，就有了跟“矩阵”名字很像的拟阵结构。

什么是拟阵？

因此，矩阵中线性无关的向量组就给出了第一个拟阵的实例。

矩阵中有三个向量，已知与，与分别线性无关，则可以导出一个线性无关集族

拟阵是这样一个二元结构：

其中是一个有限集，是由的子集构成的一个非空集族，且

  1. ;（遗传性）

  2. 若且，那么存在某个元素，使得。（交换性）

集族内的集合被称为的独立子集。

继续用向量线性无关的例子来理解上面两个性质：

  1. 如果一堆向量线性无关，那么从里面取出任意几个向量，它们也肯定线性无关。

  2. 如果第二组向量的秩比第一组向量的秩大，那么第二组向量中一定能拿出第一组向量没法线性表示的一个向量，把这个向量和第一组向量合并起来就可以生成一个更大的线性无关组。

另外，如果存在独立子集和元素使得，则称是的一个扩展。

如果一个独立子集不存在扩展，那就称它是最大的（事实上一般这种性质会被叫做极大的，但下面的定理会告诉我们为什么它们在拟阵中是一样的）。

容易发现，一个拟阵的所有最大独立子集的大小都是相等的，这是因为，如果有某个最大集比另一个最大集更大，那么根据交换性，我们可以扩充那个较小的最大集，这与最大的定义矛盾。

图拟阵

拟阵的一个重要例子就是图拟阵，它定义在一个给定的无向图上：

  • 定义为，即的边集。

  • 如果是的子集，则当且仅当是无圈的。也就是说，一组边是独立的当且仅当子图形成一个森林。

此处省略是拟阵的证明，从线性无关的角度看还是比较直观的，成圈了就相当于线性相关。

拟阵与贪心算法

拟阵有很多用处，最常见的用处就是证明贪心算法的正确性。也就是说，只要一个问题对象的结构可以被构造为一个拟阵，那么这个问题就可以直接用贪心算法正确求解。具体来说：

如果一个拟阵关联一个权重函数，为每个元素赋予一个严格大于的权重，则称是加权的。通过求和，可将权重函数的定义域扩展到的任意子集：

给定一个加权拟阵，我们希望寻找独立集使得最大，这样的独立集被称为最优子集。因此，最优子集一定是一个最大集，因为添加元素总有助于增大集合的权重。

最小生成树问题就是一个最优子集问题，只要令边的权重函数为即可，其中是的原始边权（一般来讲是长度），是一个大于的数。

所有最优子集问题都有一个统一的贪心算法：

GREEDY(,)

1

2 把 按递减排序

3 for 每个

4 if

5

6 return

该算法的正确性由拟阵的性质保证，不作证明。