线性无关
对于 ${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)$
- 设 $S={e_1,e_1,\cdots,e_n}$ 是 $m$ 维向量的 $n$ 个向量集合，$I$ 是由 $S$ 线性无关向量所组成的集合
- 设 $S$ 是一个有限集，$I=I_k$ 是 $S$ 中至多 $k$ 个元素组成的子集 ，且 $k \le |S|$
- 设 $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)$
- 设 $A \in I, B \subseteq A$，则 $B$ 亦然线性无关，从而 $B \in I$
- 设 $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$ 个数，求从中选出尽可能多的数满足：
- 这些数之中任意多个的异或和不为 $0$
- 这些数的和最大
相当于模二剩余类整数域上的最大权极大线性无关组问题，可以贪心解决
最小生成树 $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|$ 产生矛盾，因此假设不成立，得证
