线性无关

对于 ${x_1,x_2, \cdots, x_n}$,若不存在一组不全为 $0$ 的 ${k_1,k_2, \cdots, k_n}$,满足 $\sum_{i=1}^{n}k_ix_i=0$,则称它们线性无关

线性相关

对于 ${x_1,x_2, \cdots, x_n}$,若存在一组不全为 $0$ 的 ${k_1,k_2, \cdots, k_n}$,满足 $\sum_{i=1}^{n}k_ix_i=0$,则称它们线性相关

有限拟阵

一个有限拟阵是一个满足下列条件的二元组 $M=(S,I)$:

有限性(独立集公理)

$S$ 是一个有限集

可遗传性

$I$ 是由满足 $s \subseteq S$ 的一些 $s$ 组成的有限非空集合,这些 $s$ 称为 $S$ 的独立子集

若 $B \in I$ 且 $A \subseteq B$,则应有 $A \in I$,这种性质称为遗传性

交换性(独立扩充公理)

若 $A \in I, B \in I$,且 $|A| < |B|$,那么 $\exists x \in B-A$,使得 $A \cup {x} \in I$,这种性质称为交换性

拓展

给定一个拟阵 $M=(S,I)$,如果对一个集合 $A \in T$ 和一个元素 $x \not\in A$,将 $x$ 加入 $A$ 会保持独立性质,则称 $x$ 是 $A$ 的一个拓展

对于拟阵中的一个独立子集,如果它不存在拓展,则称它是最大的

几个拟阵的例子 $M=(S,I)$

  1. 设 $S={e_1,e_1,\cdots,e_n}$ 是 $m$ 维向量的 $n$ 个向量集合,$I$ 是由 $S$ 线性无关向量所组成的集合
  2. 设 $S$ 是一个有限集,$I=I_k$ 是 $S$ 中至多 $k$ 个元素组成的子集 ,且 $k \le |S|$
  3. 设 $S$ 是一个有限集,$S_1,S_2,\cdots,S_k$ 是 $S$ 的划分,令 $I={A | |A \cap S_i| \le 1, 1 \le i \le k}$

独立子集

对于拟阵 $M=(S,I)$,若 $S$ 的子集 $X$ 满足 $X \in I$,则称 $X$ 是 $S$ 的一个独立子集

极大独立子集

若对于所有 $S$ 的独立子集 $Y$ ,均有 $|X| \ge |Y|$,则称 $X$ 是 $S$ 的一个极大独立子集

或者说,若拟阵中的一个独立子集 $A$ 不存在扩展,那么称它是极大的

拟阵中所有的极大独立子集都具有相同的大小

拟阵的权函数

设 $M=(S,I)$ 是一个拟阵,$\mathbb{R}^S$ 表示定义在 $S$ 上的全体实函数,则每个映射 $w \in \mathbb{R}^S$ 称为拟阵 $M$ 的一个权函数

对于子集 $X \subseteq S$,记 $w(X)=\sum_{e \in X}w(e)$

约定 $w(\emptyset)=0$

加权拟阵

对于拟阵 $M=(S,I)$,可以关联一个权重函数 $w$,对于所有 $x \in S$,赋予一个严格大于 $0$ 的权重 $w(x)$,则称 $M$ 是加权的

同时权重函数 $w$ 可以扩展到 $A \subseteq S$:
$$
w(A)=\sum_{x \in A}w(x)
$$

加权拟阵的最大权独立集

对于拟阵 $M=(S,I)$,要求确定 $X \subseteq S, X \in I$,使得 $c(X)=\max{c(Y) | Y \in I}$

首先将所有的 $x \in S$,按照从大到小的顺序排序,维护一个一开始 $A=\emptyset$ 的集合

然后依次考虑所有的 $x$,若 $A \cup {x} \in I$,则将 $x$ 加入到 $A$

最后得到的 $A$ 即是最大权独立集

引理 1(拟阵具有贪心选择性质)

设 $M=(S, I)$ 是一个加权拟阵,加权函数为 $w$,且 $S$ 已按照权重单调递减顺序排序

设 $x$ 是 $S$ 中第一个满足 ${x}$ 独立的元素(如果存在)

若存在这样的 $x$,那么存在 $S$ 的一个最优子集 $A$ 包含 $x$

证明

假设 $B$ 是任意非空的最优子集,且 $x \not\in B$

对于任意 $y \in B$,有 $w(y) \le w(x)$(因为 $S$ 已排序)

构造集合 $A={x}$,则可以反复的在 $B$ 中找出新元素加入 $A$ 直到 $|A|=|B|$,且保持 $A$ 的独立性(独立扩充定理)

因此存在某个 $y \in B$,使得 $A=(B-{y}) \cup {x}$

由于 $w(A)=w(B)-w(y)+w(x) \ge w(B)$,于是得证

引理 2

设 $M=(S, I)$ 是一个拟阵,如果 $x \in S$ 且 $x$ 是 $S$ 的某个独立子集 $A$ 的一个扩展,则 $x$ 也是 $\emptyset$ 的一个扩展

证明

由于 $x$ 是 $A$ 的一个扩展,说明 $A \cup {x}$ 是独立的,由于 $I$ 是遗传的,所以 ${x}$ 必然是独立的,所以是 $\emptyset$ 的一个扩展

推论

设 $M=(S, I)$ 是一个拟阵,如果 $x \in S$ 且 $x$ 不是 $\emptyset$ 的一个扩展,则 $x$ 也不是 $S$ 的任何独立集 $A$ 的扩展

证明

假设 $x$ 是 $A$ 的一个扩展,说明 $A \cup {x}$ 是独立的,由于 $I$ 是遗传的,所以 ${x}$ 必然是独立的,所以是 $\emptyset$ 的一个扩展,然而其实并不是 $\emptyset$ 的一个扩展,产生矛盾,因此 $x$ 不是 $S$ 的任何独立集 $A$ 的扩展

所以我们可以得知,如果一个元素首次不能用于构造独立集,之后永远也不可能用到了

因此寻找起始元素时,贪心地直接跳过 $S$ 中那些不是 $\emptyset$ 的扩展的元素不会导致错误的结果,因为这些元素永远都不会被用到

引理 3 (拟阵具有最优子结构的性质)

设 $M=(S, I)$ 是一个加权拟阵,$x$ 是 $S$ 中第一个被贪心算法选出的元素,则接下来寻找一个包含 $x$ 的最大权重独立子集的问题归结为寻找加权拟阵 $M’=(S’,I’)$ 的一个最大权重独立子集的问题,其中:

$$
\begin{aligned}
& S’={y | y \in S, {x,y} \in I} \
& I’={B | B \subseteq (S-{x}),B \cup {x} \in I}
\end{aligned}
$$

$M’$ 的权重函数就是 $M$ 的权重函数,但只局限于 $S’$ 的元素,称 $M’$ 为 $M$ 在元素 $x$ 上的收缩

证明

首先证明在 $M’=(S’,I’)$ 中求得任意最优解 $X$ 均满足 $X \cup {x} \in I$

其次证明在 $M=(S,I)$ 中包含 $x$ 的最优解 $X$ 一定可以表示为 ${x} \cup X$,其中 $X$ 是 $M’$ 的最优解

设 $A$ 是 $M$ 的任意一个包含 $x$ 的最大权独立集,则 $A’=A-{x}$ 是 $M’$ 的一个独立子集

相反,任何 $M’$ 的独立子集 $A’$ 可生成 $M$ 的独立子集 $A=A’ \cup {x}$

由于对两种情况均有 $w(A)=w(A’)+w(x)$,因此 $M$ 的包含 $x$ 的最大权重独立子集必然是生成 $M’$ 的最大权重独立子集,反之亦然

定理(拟阵上贪心算法的正确性)

设 $M=(S, I)$ 是一个加权拟阵,权重函数为 $w$,那么 $GREEDY(M, w)$ 返回一个最优子集

证明

由推论,$GREEDY$ 跳过的任何不适 $\empty$ 的扩展的起始元素可以永久丢掉,因为这些元素永远不会被用到

一旦 $GREEDY$ 算法选出了第一个元素 $x$,引理 1 表明算法将 $x$ 加入 $A$ 不会导致错误的结果,因为必然存在包含 $x$ 的子集

最终 引理 3 说明剩下的问题就是如何寻找拟阵 $M’$ 的最优子集了,$M’$ 是 $M$ 在 $x$ 上的收缩

在 $GREEDY$ 将 $A$ 设置为 ${x}$ 后,我们可以将之后它的所有步骤解释为拟阵 $M’=(S’,I’)$ 上的操作,因为对所有集合 $B \in I’$,$B$ 在 $M’$ 中独立当且仅当 $B \cup {x}$ 在 $M$ 中独立

因此 $GREEDY$ 随后的操作将会找到 $M’$ 的一个最大权重独立子集,而且所有操作的总体效果就是找到 $M$ 的一个最大权重独立子集

例题

最大权极大线性无关组

设 $S={e_1,e_2,\cdots,e_n}$ 是 $m$ 维向量的 $n$ 个向量集合

设 $I$ 是由 $S$ 线性无关向量所组成的集合

设 $w$ 为权函数,且对于 $X \subseteq S$,有 $w(X)=\sum_{e \in X} w(e)$

求 $X \subseteq S$,使得 $X \in I$ 且 $w(X)=\max{w(Y) | Y \subseteq S}$

构造二元组 $M=(S, I)$

  1. 设 $A \in I, B \subseteq A$,则 $B$ 亦然线性无关,从而 $B \in I$
  2. 设 $A,B \in I$ 且 $|A| < |B|$,由于 $B$ 线性无关,所以 $\exists e \in B$,满足 $A$ 不能表示出 $e$,从而 $A \cup {e} \in I$

因此 $M=(S,I)$ 是拟阵,$w$ 是拟阵 $M$ 的权函数,可以贪心解决

对于第二步的证明:

假设 $\forall e \in B-A$,都有 $A \cup {e} \not\in I$,则 $B-A$ 的元素均可以由 $A$ 的某个子集来表示,这与 $|A| < |B|$ 产生矛盾,因此假设不成立,得证

异或和最大问题

给出 $n$ 个数,求从中选出尽可能多的数满足:

  1. 这些数之中任意多个的异或和不为 $0$
  2. 这些数的和最大

相当于模二剩余类整数域上的最大权极大线性无关组问题,可以贪心解决

最小生成树 $kruskal$

已知 $N=(V,E,M)$,构造二元组 $M=(S, I)$

其中 $S=E,I \subseteq 2^{S}$,且 $I={X \subseteq E | X无圈}$

只需要证明 $M=(S,I)$ 是一个拟阵

1. 设 $A \in I,B \subseteq A$,证明 $B \in I$

由于边集 $A$ 无圈,因此其子集 $B$ 依然无圈

2. 设 $A, B \in I$ 且 $|A| < |B|$,证明 $\exists e \in B - A$,使得 $A \cup {e} \in I$

对于 $M=(S,I)$ 的任意一极大独立子集 $A$ 都有 $|A|=|V|-1$

设 $A,B$ 分别导出图 $N_1,N_2$,且 $|A| < |B| \le n-1$,从而 $N_1$ 不连通

用 $p(N)$ 表示图 $N$ 的连通分量个数,由于 $N_1,N_2$ 均没有回路,故 $p(N_1) < p(N_2)$

因此 $\exists e \in B-A$,使得 $e$ 所关联的两个顶点在 $N_1$ 的不同连通分量中

从而 $A \cup {e} \in I$

综上,$M=(S,I)$ 是拟阵,从而 $kruskal$ 的贪心是对的

对于第二步的证明:

假设 $\forall e \in B-A$,都有 $A \cup {e} \not\in I$,那么有 $|A| \ge |B|$,但这与 $|A| < |B|$ 产生矛盾,因此假设不成立,得证