目录

引子

拟阵的相关定义

M=(S,L)
S={1,2,3,5}
L={ {1},{3},{5},{1,3},{1,5},{3,5},{1,3,5} }

证明:

反证法。设 $A$与 $B$ 为拟阵的两个大小不同的极大独立集，不妨设$|A|<|B|$，那么根据拟阵的交换性，$A$ 是可拓展的，不满足最大独立集的定义，与假设矛盾，故命题成立。

拟阵上的最优化问题

简单的证明一下：

若独立集 $A$ 在拟阵 $M$ 中不是极大独立集，那么它一定是可拓展的，又因为权值一定为正，所以 $A$ 拓展后的集合的权值一定大于 $w(A)$ ，所以 $A$ 一定不是权值最大独立集。(要求权值为正的作用在这里便体现了)

 Set Solve(M,w)//给出拟阵M与权值函数w  (Set这里意为返回一个集合)
{
	清空A;
    将S按w(x)的大小降序排好；
    for(对每一个x∈S,按w(x)降序)
    {
    	if(A∪{x}∈L)
        	A=A∪{x}；
    }
    return A;//即权值最大独立集
}

证明：

反证法。由引理的定义,假设 $A'$ 不是任一权值最大独立集的子集。那么对于权值最大独立集 $T$ ，当$|A'|<|T|$，由拟阵的 交换性 可得知一定存在 $x$ 满足 $x∈T$ ，$x∉A$且 $A$ $∪$ { $x$ } $∈L$ ,那么我们不断令$A'=A'$ $∪$ { $x$ }直到 $|A'|=|T|$ , 由先前假设可知此时：

定义$K=A'$ $∩$ $T$ , 那么有{ $y$ } $=∁_TK$ , { $x$ } $=∁_{A'}K$，$w(y)≤w(x)$ 。

因此此时 $w(A')=w(K)+w(x)≥w(K)+w(y)=w(T)$

若$w(A')>w(T)$，那么 $T$ 不是权值最大独立集，与假设矛盾 ; 若$w(A')=w(T)$ ，那么现在的 $A'$ 为权值最大独立集，最开始的 $A'$ 是此权值最大独立集的子集，也与假设矛盾，故引理成立。

例子:最小生成树问题

遗传性：对任意$A∈L$， $B⊆A$ , 显然$B⊆E$。假设 $B$ 中有环，那么 $A$ 中也一定有环，与 $A∈L$ 矛盾，故 $B$ 中无环，因此$B∈L$ ， $M$具有遗传性。

交换性：对任意$A∈L$，$B∈L$，设$|A|<|B|$，显然 $G_A=(V,A)$ 中有$|V|-|A|$ 个连通分量 , $G_B=(V,B)$ 中有$|V|-|B|$ 个连通分量。

由$|A|<|B|$ 有 $|V|-|A|$ $>$ $|V|-|B|$ , 可知此时 $B$ 中一定存在一条边 $x$ 连接了 $G_A$ 中的两个不同的连通分量。显然，$G'=$( $V$ , $A$ $∪$ { $x$ }$)$中无环且$A$ $∪$ { $x$ } $∈L$ ，因此$M$具有交换性。

例子:任务调度问题

遗传性：对任意$A∈L$， $B⊆A$ , 显然$B⊆S$。因为 $A∈L$ ，所以减少了部分任务的 $B$ 也一定存在合理的调度使得总惩罚为 $0$ ， 故$M$具有遗传性。

交换性：对任意$A∈L$，$B∈L$，设$|A|<|B|$，显然 $A$ 中存在任务 $x$ 满足$x∈B$ ，$x∉A$ ，我们取其中完成期限最靠后的一个任务$x'$。

由于完成期限在 $x'$ 之后的任务集 $P$ 在 $A$ , $B$ 中均含有，我们便令$A'=∁_AP$ ,$B'=∁_BP$ ，显然$|A'|<|B'|$，由 $B∈L$ 我们知道在 $x'$ 完成期限之前至少可以合理调度$|B'|$个任务，又因为$|B'|>|A'|$，所以在 $A'$ 的合理调度中一定存在位于 $x'$ 完成期限前的空余时间，在此安排 $x'$ 一定不会增加新的惩罚。

因此$A$ $∪$ { $x'$ }$∈L$ , $M$ 具有交换性。