Step by Step

贪心算法、独立系统、拟阵

独立系统与独立集

• 独立系统： 对于集合系统 (E,F)(E, \mathscr{F})(E,F) ，其中 EEE 是有限基本元素集合，F∈2E\mathscr{F} \in 2^EF∈2E，若满足：

  • (M1) ∅∈F\empty \in \mathscr{F}∅∈F
  • (M2) 若 Y⊆X∈FY \subseteq X \in \mathscr{F}Y⊆X∈F，则 Y∈FY \in \mathscr{F}Y∈F。（包含的封闭性）

  则 (E,F)(E, \mathscr{F})(E,F) 是一个独立系统。

• 独立集：F\mathscr{F}F 中的元素称为独立集。

F\mathscr{F}F 可以看作某种规则，F\mathscr{F}F 中的元素就是满足规则的集合。比如定义规则 F={T⊆E,∣T∣≤K}\mathscr{F} = \{T\subseteq E, |T| \le K\}F={T⊆E,∣T∣≤K}，(E,F)(E, \mathscr{F})(E,F) 就是一个符合定义的独立系统，独立集就是模不大于 KKK 的子集。

基、相关集与圈

• 基： 对于 F⊆EF \subseteq EF⊆E，若 T⊆FT \subseteq FT⊆F 是 FFF 上的独立集，且 ∀e∈F,e∉T\forall\ e \in F,\ e \notin T∀ e∈F, e∈/T，都有 T∪eT \cup eT∪e 就不是独立集，则 TTT 是 FFF 上的极大独立集，又称 TTT 是 FFF 的一个基。
• 相关集：2E\F2^E\backslash\mathscr{F}2E\F 中的元素称为相关集。
• 圈： 对于相关集 TTT，若 TTT 去掉任意一个元素都变成独立集，则 TTT 是极小相关集，又称 TTT 是一个圈。

在上面的例子中，基就是模等于 KKK 的子集，相关集就是模大于 KKK 的子集，圈就是模等于 K+1K+1K+1 的子集。

秩、下秩与秩商

对于 EEE 的子集 F⊆EF\subseteq EF⊆E，有：

• 秩（上秩）：γ(F)=max⁡{∣Y∣:Y⊆F,Y∈F}\gamma(F) = \max\{\ |Y|: Y\subseteq F,\ Y\in \mathscr{F}\ \}γ(F)=max{ ∣Y∣:Y⊆F, Y∈F }。即模最大的独立集的元素个数。
• 下秩：ρ(F)=min⁡{∣Y∣:Y\rho(F) = \min\{\ |Y|: Yρ(F)=min{ ∣Y∣:Y 是 FFF 的基 }\}}。即模最小的极大独立集的元素个数。
• 秩商：q(E,F)=min⁡F⊆Eρ(F)γ(F)\displaystyle\mathscr{q}(E,\mathscr{F}) = \min_{F\subseteq E} \frac{\rho(F)}{\gamma(F)}q(E,F)=F⊆Emin​γ(F)ρ(F)​。即找到集合 EEE 的一个子集 FFF, 使得下秩和上秩的比值最小（感性理解就是下秩上秩差别最大），秩商表示这个比值。

容易想到，模最大的独立集也是极大独立集，所以其实上秩下秩分别是模最大和最小的基的元素个数；秩商小于等于1。

我们前面提到过的很多组合优化问题都可以归结为独立集系统的问题。

记问题为 (E,F,C)(E,\mathscr{F},C)(E,F,C) ，其中 C:E→R+C:E\rightarrow R^+C:E→R+ 表示每个元素的权重。对 F∈EF \in EF∈E，记 C(F)C(F)C(F) 为 FFF 的权重，一般而言， C(F)=Σe∈FC(e)C(F) = \Sigma_{e \in F} C(e)C(F)=Σe∈F​C(e)。我们有两种基本优化问题：

• 极大化问题 (E,F,C)(E,\mathscr{F},C)(E,F,C) ：寻找权重最大的独立集（结果也是极大独立集）
• 极小化问题 (E,F,C)(E,\mathscr{F},C)(E,F,C) ：寻找权重最小的极大独立集

组合优化问题的例子

最小生成树问题：

对于连通无向图 G=(V,E)G=(V,E)G=(V,E)，边权 C:E→R+C:E\rightarrow R^+C:E→R+，求权重最小的生成树。

EEE 表示边集，F={F⊆E∣F\mathscr{F} = \{F\subseteq E\ |\ FF={F⊆E ∣ F 是无圈子图 }\}}，最小生成树问题是求权重最小的极大独立集。（极大独立集就是生成树）

最短路问题：

对于图 G=(V,E)G=(V,E)G=(V,E)，边权 C:E→R+C:E\rightarrow R^+C:E→R+，求 s-t​ 的最短路。

EEE 表示边集，F={F⊆E∣F\mathscr{F} = \{F\subseteq E\ |\ FF={F⊆E ∣ F 是一条 s-t 路径的边子集 }\}}，最短路问题是求权重最小的极大独立集。（极大独立集就是一条 s-t 路径）

顶点覆盖问题：

对于无向图 G=(V,E)G=(V,E)G=(V,E)，点权 C:V→R+C:V\rightarrow R^+C:V→R+，求权重最小的顶点覆盖（EEE 中任意一条边的两个顶点至少有一个在）。

EEE 表示点集，F={F⊆E∣F\mathscr{F} = \{F\subseteq E\ |\ FF={F⊆E ∣ F 是某个极小顶点覆盖的子集 }\}}，求权重最大的独立集。

最大权匹配问题：

对于无向图 G=(V,E)G=(V,E)G=(V,E)，边权 C:E→R+C:E\rightarrow R^+C:E→R+，求权重最大的边集，其任意两边无公共顶点。

EEE 表示边集，F={F⊆E∣F\mathscr{F} = \{F\subseteq E\ |\ FF={F⊆E ∣ F 中的边无公共顶点 }\}}，求权重最大的独立集。

装箱问题：

对于物品集合，每个物品有相应体积，若干单位容量的箱子，求箱子用量最小的装箱方式。

设单个箱子的可行装填方案有 MMM 个，用 tit_iti​ 表示一个单箱装填方案，则任一个装箱的可行解都是若干单箱方案的集合，使得每个物品一定出现在某个方案中。

则 E={t1,...,tM}E=\{t_1, ...,t_M\}E={t1​,...,tM​}，每个方案的权重 C(ti)=1C(t_i) = 1C(ti​)=1，F={F⊆E∣F\mathscr{F} = \{F\subseteq E\ |\ FF={F⊆E ∣ F 是某个装箱可行解的子集 }\}}，求权重最小的极大独立集。（极大独立集就是一个装箱可行解）

背包问题：

对于物品集合 EEE，每个物品的体积 C:E→R+C:E\rightarrow R^+C:E→R+，背包体积给定为 KKK，求权重最大的装包方案。

EEE 表示物品集合，F={F⊆E∣C(F)≤K\mathscr{F} = \{F\subseteq E\ |\ C(F) \le KF={F⊆E ∣ C(F)≤K }\}}，求权重最大的独立集。

旅行商问题：

对于无向图 G=(V,E)G=(V,E)G=(V,E)，边权 C:E→R+C:E\rightarrow R^+C:E→R+，求权重最小的哈密尔顿圈。

EEE 表示边集，F={F⊆E∣F\mathscr{F} = \{F\subseteq E\ |\ FF={F⊆E ∣ F 是某个哈密尔顿圈的子集 }\}}，求权重最小的极大独立集。（极大独立集就是哈密尔顿圈）

对于 (E,F,C)(E,\mathscr{F},C)(E,F,C) 上极大化问题的贪心算法，有 Best in 和 Worst out 两种

Best in：

对权重进行排序： c1≥c2≥...≥cnc_1 \ge c_2\ge ... \ge c_nc1​≥c2​≥...≥cn​

F=ϕF = \phiF=ϕ
for iii = 1 to n
if F∪ei∈FF\cup e_{i} \in \mathscr{F}F∪ei​∈F
F:=F∪eiF := F\cup e_{i}F:=F∪ei​

Worst out:

对权重进行排序：c1≥c2≥...≥cnc_1 \ge c_2\ge ... \ge c_nc1​≥c2​≥...≥cn​

F=EF=EF=E
for iii = 1 to n
if F\eiF\backslash{e_i}F\ei​ 含基
F:=F\eiF := F\backslash{e_i}F:=F\ei​

• 证明使用Best-in求解极大化问题满足q(E,F)≤G(E,F,c)OPT(E,F,C)≤1q(E,F) \leq \frac{G(E,F,c)}{OPT(E,F,C)} \leq 1q(E,F)≤OPT(E,F,C)G(E,F,c)​≤1，注意下界是与权ccc无关的。

  Ej={e1,e2,...,ej}E_j = \{e_1, e_2, ..., e_ j\}Ej​={e1​,e2​,...,ej​} C: E→R+,c1≥c2≥...≥cnE\rightarrow R^+ ,\quad c_1 \ge c_2\ge ...\ge c_nE→R+,c1​≥c2​≥...≥cn​
  贪心算法解：Gn,Gj=Gn∩Ej,j=1,2,...,nG_n,\quad G_j = G_n\cap E_j,\ j = 1,2,...,nGn​,Gj​=Gn​∩Ej​, j=1,2,...,n
  最优解：On,Oj=On∩Ej,j=1,2,...,nO_n,\quad O_j = O_n\cap E_j,\ j = 1,2,...,nOn​,Oj​=On​∩Ej​, j=1,2,...,n
  C(Gn)=∑j=1n(∣Gj∣−∣Gj−1∣)cj=∑j=1n∣Gj∣(cj−cj+1)≥∑j=1nρ(Ej)(cj−cj+1)[Gj是Ej的⼀个极大独立集]≥q∑j=1nr(Ej)(cj−cj+1)[q(E,F)=min⁡F⊆Eρ(F)γ(F)]≥q∑j=1n∣Oj∣(cj−cj+1)[γ(F)=max⁡{∣Y∣,Y⊆F,Y∈F}]=qC(On)​ \begin{aligned} C(G_n) &= \sum^n_{j=1} (|G_j|-|G_{j-1}|)c_j \\ &= \sum^n_{j=1} |G_j|(c_j-c_{j+1})\\ &\ge \sum^n_{j=1} \rho(E_j)(c_j-c_{j+1}) \quad[G_j是E_j的⼀个极大独立集]\\ &\ge q \sum^n_{j=1} r(E_j) (c_j-c_{j+1}) \quad[ q(E,\mathscr{F}) = \min_{F\subseteq E}\frac{\rho(F)}{\gamma(F)}]\\ &\ge q \sum^n_{j=1} |O_j| (c_j-c_{j+1}) \quad[ \gamma(F) = \max\{|Y|, Y\subseteq F, Y\in \mathscr{F}\} ]\\ &= q\ C(O_n)​ \end{aligned} C(Gn​)​=j=1∑n​(∣Gj​∣−∣Gj−1​∣)cj​=j=1∑n​∣Gj​∣(cj​−cj+1​)≥j=1∑n​ρ(Ej​)(cj​−cj+1​)[Gj​是Ej​的⼀个极大独立集]≥qj=1∑n​r(Ej​)(cj​−cj+1​)[q(E,F)=F⊆Emin​γ(F)ρ(F)​]≥qj=1∑n​∣Oj​∣(cj​−cj+1​)[γ(F)=max{∣Y∣,Y⊆F,Y∈F}]=q C(On​)​​

  证下界是紧的：

  由秩商的定义， ∃F,ρ(F)γ(F)=q(E,F)\exists F, \frac{\rho(F)}{\gamma(F)} = q(E,\mathscr{F})∃F,γ(F)ρ(F)​=q(E,F)，即 ∃F\exists F∃F , FFF 的基 B1,B2B_1, B_2B1​,B2​ 满足 ∣B1∣∣B2∣=q(E,F)\frac{\vert B_1\vert}{\vert B_2\vert} = q(E, \mathscr{F})∣B2​∣∣B1​∣​=q(E,F)

  定义权重：c(e)=1,e∈F;c(e)=0,e∉Fc(e) = 1, e\in F;\ c(e) = 0, e\notin Fc(e)=1,e∈F; c(e)=0,e∈/F 。把 B1B_1B1​ 的元素排在前面 e1,e2,...,e∣B1∣,...e_1, e_2, ..., e_{\vert B_1\vert},...e1​,e2​,...,e∣B1​∣​,... 。使用Best in，会选择前 ∣B1∣\vert B_1\vert∣B1​∣ 个元素，而最优解可以选 ∣B2∣\vert B_2\vert∣B2​∣ 个元素。

  因此贪心算法的近似比

  q(E,F)≤G(E,F,C)OPT(E,F,C)≤1 q(E,\mathscr{F}) \le \frac{G(E,\mathscr{F},C)}{OPT(E,\mathscr{F},C)} \le 1 q(E,F)≤OPT(E,F,C)G(E,F,C)​≤1

• Worst out类似：Worst-out求解极小化问题，将元素按照权重从大到小排序，依次尝试去掉一个元素，如果还有一个基剩余那么就去掉该元素，满足1≤G(E,F,c)OPT(E,F,c)≤max⁡X⊆E∣X∣−ρ∗(X)∣X∣−r∗(X)1 \leq \frac{G(E,F,c)}{OPT(E,F,c)} \leq \max_{X \subseteq E}\frac{|X|-\rho*(X)}{|X|-r*(X)}1≤OPT(E,F,c)G(E,F,c)​≤maxX⊆E​∣X∣−r∗(X)∣X∣−ρ∗(X)​，其中XXX是EEE的一个任意非独立子集，证明在对偶系统部分。

考虑下面两个问题：极小覆盖集的最大权问题，极大独立集的最小权问题，可以发现只有在best-in用在极大化问题，worst-out用在极小化问题时才可以保证上述两个约束，当然特例是拟阵，两个算法相同

对偶独立系统

定义：
(E,F)→(E,F∗)F∗={X⊆E∣∃F的一个基B，满足X∩B=∅} (E,\mathscr{F}) \rightarrow (E,\mathscr{F}^*)\\\mathscr{F}^* = \{X\subseteq E\ \vert\ \exists\mathscr{F}的一个基B，满足 X\cap B = \emptyset \} (E,F)→(E,F∗)F∗={X⊆E ∣ ∃F的一个基B，满足X∩B=∅}

• (E,F∗)(E,\mathscr{F}^*)(E,F∗) 是一个独立集系统：证明满足独立集系统的定义即可

• BBB 是 (E,F)(E,\mathscr{F})(E,F) 的基， 当且仅当， E\BE\backslash BE\B 是 (E,F∗)(E,\mathscr{F}^*)(E,F∗) 的基：
  若 AAA 是 (E,F∗)(E,\mathscr{F}^*)(E,F∗) 的一个基，则 ∃B∈F,A∩B=∅\exists B\in \mathscr{F},A\cap B = \emptyset∃B∈F,A∩B=∅并且B是基
  由于 AAA 是极大独立集， 再加任何一个就不是独立集，A=E\BA = E\backslash BA=E\B

• (E,F∗∗)=(E,F)(E,\mathscr{F}^{**}) = (E,\mathscr{F})(E,F∗∗)=(E,F)

  ∀X∈F∗∗⇔∃(E,F∗)的一个基B∗,X∩B∗=∅⇔∃(E,F)的一个基B,X∩(E\B)=∅⇔∃(E,F)的一个基B,X⊆B,X⊆F \begin{aligned} \forall X\in \mathscr{F}^{**} &\Leftrightarrow \exists (E,\mathscr{F}^*)的一个基 B^*, X\cap B^* = \emptyset\\ &\Leftrightarrow \exists (E,\mathscr{F})的一个基 B, X\cap (E\backslash B) = \emptyset\\ &\Leftrightarrow \exists (E,\mathscr{F})的一个基 B, X\subseteq B, X\subseteq\mathscr{F} \end{aligned} ∀X∈F∗∗​⇔∃(E,F∗)的一个基B∗,X∩B∗=∅⇔∃(E,F)的一个基B,X∩(E\B)=∅⇔∃(E,F)的一个基B,X⊆B,X⊆F​

独立集系统的对偶主要用于分析Worst out极小化问题，可以证明：

1≤G(E,F,C)OPT(E,F,C)≤max⁡F≠∅∣F∣−ρ∗(F)∣F∣−γ∗(F) 1\le \frac{G(E,\mathscr{F},C)}{OPT(E,\mathscr{F},C)} \le \max_{F\neq \emptyset }\frac{\vert F\vert-\rho^*(F)}{\vert F\vert-\gamma^*(F)} 1≤OPT(E,F,C)G(E,F,C)​≤maxF=∅​∣F∣−γ∗(F)∣F∣−ρ∗(F)​

证明与极大化问题类似.

Gj∪(E∖Ej)G_{j} \cup (E \setminus E_{j})Gj​∪(E∖Ej​)含有EEE的基，并且任取e∈Gje \in G_{j}e∈Gj​，Gj∪(E∖Ej)∖{e}G_{j} \cup (E \setminus E_{j}) \setminus \{e\}Gj​∪(E∖Ej​)∖{e}就不再是EEE的基。

E∖(GJ∪(E∖Ej))=Ej∖GjE \setminus (G_{J} \cup (E \setminus E_{j}))=E_{j} \setminus G_{j}E∖(GJ​∪(E∖Ej​))=Ej​∖Gj​是F∗F^{*}F∗在EjE_{j}Ej​上的基，因此∣Ej∣−∣Gj∣≥ρ∗(Ej)|E_{j}|-|G_{j}| \geq \rho^{*}(E_{j})∣Ej​∣−∣Gj​∣≥ρ∗(Ej​)。

考虑On⊆E∖(Ej∖Oj)O_{n} \subseteq E \setminus (E_{j} \setminus O_{j})On​⊆E∖(Ej​∖Oj​)且是一个基，所以Ej∖Oj∈F∗E_{j} \setminus O_{j} \in F^{*}Ej​∖Oj​∈F∗，因此∣Ej∣−∣Oj∣≤r∗(Ej)|E_{j}|-|O_{j}| \leq r^{*}(E_{j})∣Ej​∣−∣Oj​∣≤r∗(Ej​) 。

因此我们得到了∣Gj∣≤∣Ej∣−ρ∗(Ej)∣Oj∣≥∣Ej∣−r∗(Ej)\begin{aligned} |G_{j}| \leq |E_{j}|-\rho^{*}(E_{j}) \\ |O_{j}| \geq |E_{j}|-r^{*}(E_{j}) \end{aligned}∣Gj​∣≤∣Ej​∣−ρ∗(Ej​)∣Oj​∣≥∣Ej​∣−r∗(Ej​)​，那么令λ=maxX⊆E∣X∣−ρ∗(X)∣X∣−r∗(X)\lambda = max_{X \subseteq E}\frac{|X|-\rho^{*}(X)}{|X|-r^{*}(X)}λ=maxX⊆E​∣X∣−r∗(X)∣X∣−ρ∗(X)​，则有∣Gj∣≤λ∣Oj∣|G_{j}| \leq \lambda |O_{j}|∣Gj​∣≤λ∣Oj​∣，带入best-in证明即可。

秩商的估计式

如果对任意A∈F,e∈EA \in \mathscr{F}, \ e \in EA∈F, e∈E，A+eA + eA+e最多PPP个圈，则q(E,F)≥1/pq(E, \mathscr{F}) \ge 1/pq(E,F)≥1/p。

拟阵是一类特殊的独立集系统: (E,F)(E,\mathscr{F})(E,F) 满足:

• (M1): ∅∈F\emptyset \in \mathscr{F}∅∈F
• (M2): 若 X∈F,∀Y⊆X,Y∈FX\in \mathscr{F},\ \forall Y\subseteq X,Y\in\mathscr{F}X∈F, ∀Y⊆X,Y∈F
• (M3): 若X,Y∈F,∣X∣>∣Y∣,则∃e∈X\Y,Y∪{e}∈F若X, Y\in\mathscr{F},\vert X \vert >\vert Y\vert ,则 \exists e\in X\backslash Y, Y\cup \{e\}\in\mathscr{F}若X,Y∈F,∣X∣>∣Y∣,则∃e∈X\Y,Y∪{e}∈F , 也就是说 YYY 可从XXX扩充
  (M3’): 若X,Y∈F,∣X∣=∣Y∣+1,则∃e∈X\Y,Y∪{e}∈F若X, Y\in\mathscr{F},\vert X \vert = \vert Y\vert +1,则 \exists e\in X\backslash Y, Y\cup \{e\}\in\mathscr{F}若X,Y∈F,∣X∣=∣Y∣+1,则∃e∈X\Y,Y∪{e}∈F, 也就是说 YYY 可从XXX扩充
  (M3"): ∀F⊆E\forall F \subseteq E∀F⊆E, FFF 上的任何基有相同的元素个数 (要注意这里不只是 EEE 上的基，而是 EEE 的任意子集上的基)
  M3, M3’, M3" 是相互等价的，只要满足其中之一的独立集系统就是拟阵。

例子:

1. 向量
   E={v1,v2,...,vm},F={Z⊆E∣Z是线性无关组} E = \{v_1,v_2,...,v_m\},\ \mathscr{F} = \{Z\subseteq E\vert Z 是线性无关组\} E={v1​,v2​,...,vm​}, F={Z⊆E∣Z是线性无关组}

2. 相同的模
   E 是有限集合，K 是一个给定的正整数, F={X⊆E∣∣X∣≤K}\mathscr{F} = \{X\subseteq E\vert\ \vert X\vert\le K\}F={X⊆E∣ ∣X∣≤K}

3. 图拟阵
   EEE 是无向图 GGG 中的边集, F={X⊆E,X构成一个森林}\mathscr{F} = \{X\subseteq E, X 构成一个森林\}F={X⊆E,X构成一个森林}

可以看到很多常见的体系都是一个拟阵，如矩阵与线性无关的概念，森林与树。又或者说，拟阵是这些体系的一个抽象，从而分析它们的共性。

拟阵与贪心算法

可以简单得到，拟阵的秩商是 1，根据前面独立集系统的分析，贪心算法的近似比为1。因此，在拟阵中使用贪心算法可以得到最优解。[ 所以最小生成树问题贪心就可以得到最优解。]

用秩商分析得到这个结论是显然的，下面用另一种方法证明拟阵上贪心算法可以得到最优解（来自算法导论）

引理1： (拟阵具有贪心选择性质) 假定 M=(S,I)M= ( S , I )M=(S,I) 是一个加权拟阵，加权函数为 $ w$ , 且
SSS 已按权重单调递减顺序排序． 令 xxx 是S 中第一个满足 {x}\{x\}{x} 独立的元素（ 如果存在）。如果存在这样的 xxx ， 那么存在 SSS 的一个最优子集 AAA 包含xxx．

证明：

1. 如果不存在这样的 xxx ， 唯一的独立子集是空集，引理显然成立。否则，令B 为任意非
   空最优子集． 假定 x∉Bx\notin Bx∈/B。
2. BBB 中元素的权重都不大于 w(x)w( x )w(x): 我们观察到 y∈By\in By∈B 意味 ${y} 是独立的，是独立的，是独立的，x$ 是第一个形成独立集的元素，因此对任意 y∈By\in By∈B, 有 $w(x) \ge w(y) $。
3. 构造集合 AAA . 以 A={x}A = \{x\}A={x} 开始，集合 AAA 是独立的。根据 (M3): 若X,Y∈FX, Y\in\mathscr{F}X,Y∈F, ∣X∣>∣Y∣\vert X \vert >\vert Y\vert∣X∣>∣Y∣, 则∃e∈X\Y\exists e\in X\backslash Y∃e∈X\Y,Y∪{e}∈FY\cup \{e\}\in\mathscr{F}Y∪{e}∈F， 反复寻找 BBB 中一个可以加入 AAA 中的新元素, 同时保持 AAA 的独立性，直至 ∣A∣=∣B∣\vert A \vert =\vert B\vert∣A∣=∣B∣ . 此时， A 和B 的区别仅在 AAA 包含 xxx ，而 BBB 包含另一个元素 yyy . 由于 w(x)≥w(y)w(x)\ge w(y)w(x)≥w(y) ,所以 w(A)=w(B)−w(y)+w(x)≥w(B)w(A) = w(B) - w(y) +w(x) \ge w(B)w(A)=w(B)−w(y)+w(x)≥w(B) 。
4. 由于集合B 是最优的，因此集合A 必然也是最优的，且包含 xxx。

引理2: M=(S,I)M= (S , I )M=(S,I) 是一个拟阵． 如果 xxx 是 SSS 中一个元素， 且它不是 ∅\emptyset∅ 的一个扩展．
那么它也不是 SSS 的任何独立子集 AAA 的扩展．

证明：由独立集的定义，独立集中的任何元素 xxx 自身形成的集合 {x}\{x\}{x} 也是一个独立集。因此若 {x}\{x\}{x} 不是独立集，则 A∪{x}A\cup\{x\}A∪{x} 也不是独立集。

引理2表明， 任何元素如果首次不能用于构造独立集，则之后也不可能被用到。因此，贪心算法跳过 SSS 中那些不是 ∅\emptyset∅ 的扩展的起始元素，不会导致错误结果。

引理3: （拟阵具有最优子结构性质） M=(S,I)M= (S , I )M=(S,I) 是一个加权拟阵，xxx 是 SSS 中第一个被贪心算法选出的元素，则接下来寻找一个包含 xxx 的最大权重独立子集的问题归结为寻找加权拟阵 M′=(S′,I′)M'=(S',I')M′=(S′,I′) 的一个最大权重独立子集的问题， 其中

S′={y∈S:(x,y)∈I}I′={B⊆S−{x}:B∪{x}∈I} S' = \{y\in S:(x,y)\in I\}\\ I' = \{B\subseteq S-\{x\}:B\cup\{x\}\in I\}\\ S′={y∈S:(x,y)∈I}I′={B⊆S−{x}:B∪{x}∈I}

M′M'M′ 的权重函数就是 MMM 的权重函数，但只局限于S’ 中元素． 我们称 M′M'M′ 为 MMM 在元素 xxx 上的收缩 ( contraction)

证明: 若 AAA 是 MMM 的任意一个包含x 的最大权独立子集，则 A′=A−{x}A' = A -\{x\}A′=A−{x} 是 M′M'M′ 的一个独立子集。同时，任何 M′M'M′ 的独立子集 AAA 可生成 MMM 的独立子集 A=A′∪{x}A = A'\cup\{x\}A=A′∪{x} . 均有 w(A)=w(A′)+w(x)w(A)=w(A')+w(x)w(A)=w(A′)+w(x).因此 MMM 的包含 xxx 的最大权重独立子集必然生成 M′M'M′ 的最大权重独立子集．反之亦然．

定理: （拟阵上贪心算法的正确性） 若 M=(S,I)M= ( S , I )M=(S,I) 是一个加权拟阵，加权函数为 $ w$ ．那么贪心算法返回一个最优子集

证明：由引理2, 贪心算法跳过 SSS 中那些不是 ∅\emptyset∅ 的扩展的起始元素可永远丢弃． 因为这些元素不会被用到。一旦贪心算法选出第一个元素 xxx， 引理 1 表明算法将 xxx加入 AAA 不会导致错误结果， 因为必然存在包含 xxx 的最优子集。 引理 3 说明剩下的问题就是如何寻找拟阵 M′M'M′ 的最优子集， M′M'M′ 是 MMM 在 xxx 上的收缩。将 AAA 设为 {x}\{ x\}{x} 后．我们可以将之后的所有步骤解释为拟阵 M′=(S′,I′)M' =(S',I')M′=(S′,I′)上的操作,因为对所有集合 B∈I′B\in I'B∈I′ , BBB 在 M′M'M′ 中独立当且仅当 B∪{x}B\cup\{x\}B∪{x} 在 MMM 中独立。因此， 贪心算法随后的操作将会找到M’ 的一个最大权重独立子集。而其所有操作的总体效果就是找到 MMM 的一个最大权重独立子集。

拟阵与独立系统

独立集系统的交： (E,F1),(E,F2)(E,\mathscr{F}_1), (E,\mathscr{F}_2)(E,F1​),(E,F2​) 的交为 (E,F1∩F2)(E,\mathscr{F}_1\cap\mathscr{F}_2)(E,F1​∩F2​)

任何一个独立集系统⼀定是有限个拟阵的交。构造法证明：

记独立集系统为 (E,F)(E,\mathscr{F})(E,F) , 设独立集系统有 kkk 个圈： c1,c2,...,ckc_1,c_2,...,c_kc1​,c2​,...,ck​

令 Fi={X⊆E∣X⊉ci}\mathscr{F}_i = \{X\subseteq E\vert X\nsupseteq c_i\}Fi​={X⊆E∣X⊉ci​} , 可以证明 (E,Fi)(E,\mathscr{F}_i)(E,Fi​) 是一个独立集系统。

[ 这里很容易弄晕，解释一下。前面说过独立集系统表示了一个集合与一个规则，在这里不同的 Fi\mathscr{F}_iFi​ 表示了不同的规则，因此形成了不同的独立集系统，每个独立集系统都确定了哪些是独立集哪些不是。 (E,Fi)(E,\mathscr{F}_i)(E,Fi​) 这个独立集系统表示的是：如果一个集合不包含 cic_ici​ 中的所有元素，则它是一个独立集。对于第 iii 个独立集系统，独立集可以包含其他圈。圈的概念是极小相关集，但这里的相关集是独立集系统 (E,F)(E,\mathscr{F})(E,F) 中的相关集，在当前的独立集系统中，包含 ‘圈’ 的集合仍可以是独立集 ]

下证， (E,Fi)(E,\mathscr{F}_i)(E,Fi​) 是拟阵，用 M3": ∀F⊆E\forall F \subseteq E∀F⊆E, FFF 上的任何基有相同的元素个数。对于 ∀F⊆E\forall F \subseteq E∀F⊆E

1. F⊉ciF \nsupseteq c_iF⊉ci​ ，则整个集合 FFF 是一个独立集，因此它就是 FFF 上的极大独立集， FFF 上的基有相同的元素个数
2. F⊇ciF \supseteq c_iF⊇ci​ ，对 ∀e∈ci\forall e\in c_i∀e∈ci​ , F\eF\backslash {e}F\e 是极大独立集， FFF 上的基有相同的元素个数

现证 F=∩i=1kFi\mathscr{F} = \cap_{i = 1}^k \mathscr{F}_iF=∩i=1k​Fi​

• F⊆∩i=1kFi\mathscr{F} \subseteq \cap_{i = 1}^k \mathscr{F}_iF⊆∩i=1k​Fi​:
  ∀X∈F,X\forall X\in \mathscr{F},X∀X∈F,X 不包含任何圈, X∈Fi,i=1,...,k⇒X∈∩i=1kFiX\in\mathscr {F}_i,i=1,...,k \ \Rightarrow X\in \cap_{i = 1}^k \mathscr{F}_iX∈Fi​,i=1,...,k ⇒X∈∩i=1k​Fi​

• F⊇∩i=1kFi\mathscr{F} \supseteq \cap_{i = 1}^k \mathscr{F}_iF⊇∩i=1k​Fi​
  ∀X∈Fi,X\forall X\in \mathscr{F}_i,X∀X∈Fi​,X不包含圈 cic_ici​ 。∀X∈∩i=1kFi⇒X\forall X\in\cap_{i = 1}^k \mathscr{F}_i\Rightarrow X∀X∈∩i=1k​Fi​⇒X不包含任何圈 ⇒X∈F\Rightarrow X\in \mathscr{F}⇒X∈F

[ 需要指出的是，这里只是用构造法说明了任何⼀个独⽴集系统都可以表示为有限个拟阵的交，但用这种构造不一定能分解为最少的拟阵，在实际应用中不一定能得到紧的解 ]

少数的例子：

对于二部图 G=(A∪B,E)G=(A\cup B,E)G=(A∪B,E), (E,F)(E,\mathscr{F})(E,F) 表示图的匹配的独立集系统。

F1={X⊆E,∣δX(u)∣≤1,∀u∈A}F2={Y⊆E,∣δY(u)∣≤1,∀u∈B} \mathscr{F}_1 = \{X\subseteq E, \vert\delta _X(u)\vert\le 1,\forall u\in A\}\\ \mathscr{F}_2 = \{Y\subseteq E, \vert\delta _Y(u)\vert\le 1,\forall u\in B\}\\ F1​={X⊆E,∣δX​(u)∣≤1,∀u∈A}F2​={Y⊆E,∣δY​(u)∣≤1,∀u∈B}

其中 δX(u)\delta_X(u)δX​(u) 表示 uuu 的度数，只考虑 XXX 中的边。可以证明， (E,F1),(E,F2)(E,\mathscr{F}_1),(E,\mathscr{F}_2)(E,F1​),(E,F2​) 是拟阵且 F=F1∩F2\mathscr{F} = \mathscr{F}_1\cap \mathscr{F}_2F=F1​∩F2​ 。

若独立集系统是 kkk 个拟阵的交，则贪心解的近似比至少为 1/k1/k1/k

记独⽴集系统为 (E，F)(E，\mathscr{F})(E，F)，是 kkk 个拟阵 (E，Fi)(E，\mathscr{F}_i)(E，Fi​) 的交。

证：即证秩商 q(E,F)≥1/kq(E ,\mathscr{F}) \ge 1 /kq(E,F)≥1/k 。对 ∀F⊆E\forall F\subseteq E∀F⊆E, 考虑 (E,F)(E ,\mathscr{F})(E,F) 在 FFF 上任意两个不同的极⼤独⽴集 A,BA, BA,B ∣B∣≥∣A∣\vert B\vert \ge \vert A\vert∣B∣≥∣A∣ , 只需证 ∣B∣≤k∣A∣\vert B\vert \le k\vert A\vert∣B∣≤k∣A∣

AiA_iAi​ 是 (E,Fi)(E,\mathscr{F}_i)(E,Fi​) 在 A∪BA\cup BA∪B 上含 AAA 的极大独立集，容易得 A=⋂i=1kAiA = \bigcap_{i=1}^k A_iA=⋂i=1k​Ai​
BiB_iBi​ 是 (E,Fi)(E,\mathscr{F}_i)(E,Fi​) 在 A∪BA\cup BA∪B 上含 BBB 的极大独立集，B=⋂i=1kBiB = \bigcap_{i=1}^k B_iB=⋂i=1k​Bi​

∀e∈B\A\forall e \in B\backslash A∀e∈B\A, ，由于 e∉Ae\notin Ae∈/A, 有 e∉⋂i=1kAie\notin \bigcap_{i=1}^k A_ie∈/⋂i=1k​Ai​, 则 eee 不可能同时在每个 AiA_iAi​ , eee 最多同时出现在 k−1k-1k−1 个 Ai\AA_i\backslash AAi​\A 中。每一个 B\AB\backslash AB\A 中的元素最多在 k−1k-1k−1 个 Ai\AA_i\backslash AAi​\A 中，因此有 1k−1∑i=1k∣Ai\A∣≤∣B\A∣\frac{1}{k-1}\sum_{i=1}^k \vert A_i\backslash A\vert \le \vert B\backslash A\vertk−11​∑i=1k​∣Ai​\A∣≤∣B\A∣ , 于是：

∑i=1k∣Ai\A∣≤(k−1)∣B\A∣≤(k−1)∣B∣∑i=1k∣Ai∣−k∣A∣≤(k−1)∣B∣ \sum_{i=1}^k \vert A_i\backslash A\vert \le (k-1)\vert B\backslash A\vert \le (k-1)\vert B\vert\\ \sum_{i=1}^k \vert A_i\vert - k\vert A\vert\le (k-1)\vert B\vert ∑i=1k​∣Ai​\A∣≤(k−1)∣B\A∣≤(k−1)∣B∣∑i=1k​∣Ai​∣−k∣A∣≤(k−1)∣B∣

由于 (E,Fi)(E,\mathscr{F}_i)(E,Fi​) 是拟阵， Ai,BiA_i, B_iAi​,Bi​ 是在 $A\cup B $ 上的基，有 ∀i,∣Ai∣=∣Bi∣\forall i,\vert A_i\vert = \vert B_i\vert∀i,∣Ai​∣=∣Bi​∣ .因此

k∣B∣≤∑i=1k∣Bi∣≤∑i=1k∣Ai∣≤k∣A∣+(k−1)∣B∣∣B∣≤k∣A∣ k\vert B\vert \le\sum_{i=1}^k\vert B_i\vert \le\sum_{i=1}^k\vert A_i\vert \le k\vert A\vert+ (k-1)\vert B\vert\\ \vert B\vert \le k\vert A\vert k∣B∣≤∑i=1k​∣Bi​∣≤∑i=1k​∣Ai​∣≤k∣A∣+(k−1)∣B∣∣B∣≤k∣A∣

对 ∀F⊆E\forall F\subseteq E∀F⊆E, FFF 上任意两个不同的极⼤独⽴集A,BA, BA,B 有 ∣A∣≤∣B∣≤k∣A∣\vert A\vert \le \vert B\vert\le k\vert A\vert∣A∣≤∣B∣≤k∣A∣， 因此秩商最小为 1/k1/k1/k ，贪心解的近似比至少为 1/k1/k1/k 。