( ext{Part.1}) 基本定义
定义(1.1)
记(M=(S,I))表示一个定义在有限集(S)上，独立集的集合是(I)的拟阵。其中(Isubseteq2^{S})（即(I={Tsubseteq S|f(T)})）。若(M)满足下列公理，则我们称之为拟阵。
公理(1)（遗传性）
(forall Ain I,Bsubseteq ARightarrow Bin I)
公理(2)（扩张性）
(forall A,Bin Iwedge|B|>|A|,exists xin Bsetminus A,s.t. Acup{x}in I)
定义(1.2)
若(Ain I)，则我们称(A)是独立的，或者说(A)是独立集。否则称(A)是不独立的。
为了方便，我们认为(emptysetin I)。
( ext{ex.1})（均匀拟阵）
令拟阵(U_n^k=(S,I))，其中(|S|=n,I={Tsubseteq S||T|le k})。
( ext{ex.2})（无向图拟阵）
令无向图(G=(V,E))，无向图拟阵(M=(E,I))，其中(I={Fsubseteq E|F)无环(})。
无向图拟阵的遗传性是显然的。
对于扩张性，由于(|B|>|A|)，所以(A)的导出子图的连通块数一定比(B)的导出子图多，所以必然存在一个(B)的导出子图的连通块在(A)的导出子图中不连通，所以必然存在一条(B)的一条边可以加入(A)使得(A)无环。
( ext{ex.3})（有向图“拟阵”）
令有向图(G=(V,E))，有向图“拟阵”(M=(E,I))，其中(I={Fsubseteq E|F)无环(})。
然而这并不是拟阵。
( ext{ex.4})（匹配拟阵）
令无向图(G=(V,E))，匹配拟阵(M=(V,I))，其中(I={Wsubseteq V|)存在一组匹配可以覆盖(W})。
匹配拟阵的遗传性是显然的。
对于扩张性，可以考虑利用增广路来进行证明，具体留作读者自证。
( ext{ex.5})（向量拟阵）
令(S)为一个(n)维向量的集合，令拟阵(M=(S,I))，其中(I={Tsubseteq S|T)线性无关(})。
向量拟阵的遗传性是显然的。
对于扩张性，考虑两组线性无关的向量(a_1,cdots,a_n)和(b_1,cdots,b_{n+1})。
如果向量拟阵不满足扩张性，那么(b_1,cdots,b_{n+1})一定都能被(a_1,cdots,a_n)线性表示。
现在将(a_1,cdots,a_n,c_1,cdots,c_m)作为该向量集合的一组新的基。（因为我们无法满足(a_1,cdots,a_n)能够线性表示所有该向量集合中的所有向量，所以我们加入一些无关的其它向量）
然后我们用这组基将(b_1,cdots,b_{n+1})表示，得到的向量组所构成的矩阵的秩为(n)，小于这组向量的个数(n+1)，因此(b_1,cdots,b_{n+1})是一组线性相关的向量组，这与一开始定义的线性无关矛盾。
因此一定存在一个(b_i)满足它不能被(a_1,cdots,a_n)线性表示，由此可得向量拟阵满足扩张性。
( ext{Part.2}) 基&环
定义(2.1)
对于(M=(S,I))中的一个(Ain I)，若(forall xin Ssetminus A,A+{x}
otin I)，则我们称(A)为拟阵(M)的一个基，或者叫极大独立集。
对于(M=(S,I))中的一个(Asubseteq S,A
otin I)，若(forall xin A,Asetminus{x}in I)，则我们称(A)为拟阵(M)的一个环，或者叫极小非独立集。我们用(C(M))来表示拟阵(M)所有的环。
引理(2.1)
对于任意拟阵(M)，(M)的所有基的大小相同。
定理(2.1)（基交换定理）
对于任意拟阵(M)，若(M)有两个不相同的基(A,B)，那么(forall xin Asetminus B,exists yin Bsetminus A,s.t. A-{x}+{y}in I)。即(A-{x}+{y})是(M)的基。
推论(2.1)
(forall X,Yin C(M),Xsubseteq YRightarrow X=Y)
推论(2.2)
(forall X,Yin C(M)wedge X eq Y,forall ein Xcap Y,exists Cin C(M),s.t.Csubseteq Xcup Y-{e})
由推论(2.1)可知(Xsetminus Y)非空，设(fin Xsetminus Y)。
假设(Xcup Y-e)是独立集，因为(X)是环，所以(X-{f})是独立集。
设(Xcup Y)中最大的包含(X-{f})的独立集为(Z)。
因为(Y)是环，所以(Y otsubseteq Z)。
由此可得(|Z|le|Xcup Y-{f}|-1le |Xcup Y|-2<|Xcup Y-{e}|)。
因此(Xcup Y-{e})一定不是独立集。命题得证。
推论(2.3)
令(A)是(M=(S,I))的一个基，(ein Ssetminus A)，那么(A+{e})包含且仅包含一个环。
先证包含，由基和环的定义显然。
再证唯一，假如存在两个环(C_1,C_2)，那么有(ein C_1cap C_2)。
由推论(2.2)可得(C_1cup C_2-{e})包含环，与(A)是独立集矛盾。命题得证。
( ext{Part.3}) 秩
定义(3.1)
对于拟阵(M=(S,I))，(M)的基的大小称为拟阵的秩。
(forall Tsubseteq S)，定义秩函数(r(T))表示(T)中极大独立集的大小。
性质(1)（有界性）
(forall Tsubseteq S,0le r(T)le|T|)
性质(2)（单调性）
(forall Asubseteq Bsubseteq S,r(A)le r(B))
性质(3)（次模性）
(forall A,Bsubseteq S,r(Acup B)+r(Acap B)le r(A)+r(B))
令(Z)为(Acap B)的基，并由此扩展得到(Z_A)为(A)的极大独立集，(Z_B)为(B)的极大独立集，(Z_{AB})为(Acup B)的极大独立集。
将(Z_{AB})划分为(Acap B,Asetminus B,Bsetminus A)三部分。
由遗传性可知这三部分是独立的。且(Acup B)这部分的就是(Z)。我们再设(Asetminus B)部分的为(E_A)，(Bsetminus A)部分的为(E_B)。
那么有(r(Acup B)+r(Acap B)=|E_A|+|E_b|+|Z|+|Z|=(|E_a|+|Z|)+(|E_b|+|Z|)le r(A)+r(B))。命题得证。
如果存在一个满足(3)条性质的秩函数(r)，那么通过这个函数我们可以直接定义出拟阵(M=(S,I),I={Asubseteq S|r(A)=|A|})。
先证遗传性，令(B)为任意独立集，(Asubseteq B)。由次模性可知(|B|=r(B)le r(A)+r(B-A))，由有界性可知(r(A)le|A|,r(B-A)le|B-A|)，因此(r(A)=|A|,r(B-A)=|B-A|)，即(A)为独立集。
再证扩张性，令(A,B)为独立集，(|A|<|B|)，(B)中元素分别为(b_1,cdots,b_{|B|})。
先假设(A)加入(B)中任意一元素都不是独立集。
接下来通过归纳证明(r(Acup B)=|A|)。
首先我们有(r(Acup b_i)=|A|(iin[1,|B|]))。
然后若已知(r(Acup{b_1,cdots,b_n})=|A|)，由次模性可得(r((Acup{b_1,cdots,b_n})cup(Acup{b_{n+1}}))+r((Acup{b_1,cdots,b_n})cap(Acup{b_{n+1}}))le r(Acup{b_1,cdots,b_n})+r(Acup{b_{n+1}}))。
即(r(Acup{b_1,cdots,b_{n+1}})+|A|le|A|+|A|)，所以(r(Acup{b_1,cdots,b_{n+1}})=|A|)。
由此可知(r(Acup B)=|A|)。由单调性可知(|B|=r(B)le r(Acup B))，这导出了矛盾。故扩张性得证。
( ext{Part.4}) 拟阵上的最优化问题
给定拟阵(M=(S,I))，函数(f:S ightarrow R)，定义一个(Tsubseteq S)的权值(f(T)=sumlimits_{ein T}f(e))。现在我们需要找一个(Ain I)，最大化(f(A))。
下面先不加证明地给出构造的算法：
(1.)将(S)中的每个元素(e)按照(f(e))降序排序。
(2.)先令(A=emptyset)，然后按顺序枚举(e)，如果(Acup{e})是独立集，就把(e)加入(A)。
证明分为两部分：证明最后得到的(A)是拟阵的一个基，证明这个基是最优解。
第一部分考虑归纳证明。
令(U_i={e_1,cdots,e_i})，我们证明对于任意时刻(i)，都有(r(U_i)=|A_i|)。
当(i=0)时命题显然成立。
现在假定命题(i)成立，需要证明命题(i+1)成立。
(1.r(U_{i+1})=r(U_i))，显然成立，(A_i)不可能扩张。
(2.r(U_{i+1})=r(U_i)+1)。若(A_icup{e_{i+1}})，那么命题得证。
否则考虑现在的一组基(A_{i+1}')，因为(|A_{i+1}'|>|A_{i+1}|)，根据交换性，一定有一元素(xin A_{i+1}'setminus A_{i+1})可加入(A_{i+1})。因为(x)一定不可能是(e_{i+1})，所以一定有(xin U_i)。这说明之前存在一个大小(>r(U_i))的独立集，这导出了矛盾。故命题得证。
现在证明第二部分。假设最优解在某一步没有选择(e_i)而是选择了(e_{i'}(i'>i))，那么因为(f(e_i)ge f_{e_{i'}})之后一定存在某个选择(f(e_j)le f(e_{j'})(j'<j))。由于基交换定理，(A-{s_j}+{s_{j'}})也是独立集，因此该算法一定会选择(e_{j'})，从而不劣于(A')。命题得证。
( ext{Part.5}) 一些补充定义
定义(5.1)
对于拟阵(M=(S,I))，定义(M)的对偶拟阵(M^*=(S,I^*))，其中(I^*={Asubseteq S|)存在(M)中的基(Bsubseteq Ssetminus A})。
容易求得(r^*(U)=|U|-r(S)+r(Ssetminus U))。
定义(5.2)
对于拟阵(M=(S,I))和集合(Zsubseteq S)，定义(M)删除子集(Z)的拟阵为((Ssetminus Z,I'),I'={Asubseteq Ssetminus Z|Ain I})。记为(Msetminus Z)。
定义(5.3)
对于拟阵(M=(S,I))和集合(Zsubseteq S)，定义(M)收缩子集(Z)的拟阵为((M^*setminus Z)^*)。记为(M/Z)。
容易求得(r_{M/Z}=r_M(Zcup U)-r_M(Z))。
不难发现收缩本质上就是钦定(Z)中的一组基，(M/Z)中的独立集的要求就是并上(Z)中的独立集之后仍是(M)的一个独立集。
对一个拟阵施以以上三种操作中任意一个得到的都是一个拟阵，可以通过秩函数证明，这里不做赘述。
定义(5.4)
对于拟阵(M)，经过一系列删除和收缩操作得到的任意拟阵(M')，称作(M)的极小元。
( ext{Part.6}) 拟阵的交
定义(6.1)
给定两个定义在相同基础集上的拟阵(M_1=(S,I_1),M_2=(S,I_2))，定义(M_1)和(M_2)的交是所有的集合(A)，满足(A)同时在两个拟阵内都是独立的。
拟阵交问题一般是求两个拟阵的公共独立集中最大的独立集。这个问题的难点在于两个拟阵的交并不一定还是拟阵。接下来的一个定理可以解决这个问题。
定理(6.1)（最小最大定理）
(maxlimits_{Ain I_1cap I_2}|A|=minlimits_{Tsubseteq S}(r_1(T)+r_2(Ssetminus T)))
先给出(maxlimits_{Ain I_1cap I_2}|A|leminlimits_{Tsubseteq S}(r_1(T)+r_2(Ssetminus T)))的证明：
(|I|=|Icap T|+|Icap Ssetminus T|le r_1(T)+r_2(Ssetminus T))
然后如果我们能够给出一组(I,T)使得等号成立，那么我们就证明了这个定理。
接下来我们会给出算法构造性地证明该定理。
定义(6.2)
对于拟阵(M=(S,I))和(Asubseteq S)，定义(A)的闭包算子(cl(A)={ein S|r(Acup{e})=r(A)})。
引理(6.1)
对于拟阵(M=(S,I))，如果(Asubseteq Bsubseteq S)，那么(cl(A)subseteq cl(B))。
假设有一个(ein cl(A))。由次模性可知(r(Acup{e})+r(B)ge r((Acup{e})cap B)+r((Acup{e})cup B)ge r(A)+r(Bcup{e}))。
因为(r(Acup{e})=r(A))，所以(r(B)ge r(Bcup{e}))即(r(B)=r(Bcup{e}))。因此(ein cl(B))。因为(forall ein cl(A))，有(ein cl(B))，所以(cl(A)subseteq cl(B))。
引理(6.2)
对于拟阵(M=(S,I))和(Asubseteq S,forall ein cl(A),cl(A)=cl(Acup{e}))。
由引理(6.1)可知(cl(A)subseteq cl(Acup{e}))，因此只需证(cl(Acup{e})subseteq cl(A))。
具体证明类似于引理(6.1)的证明，此处不做赘述。
引理(6.3)
对于拟阵(M=(S,I))和(Asubseteq S,cl(A)=cl(cl(A)))。
利用引理(6.2)逐步将(cl(A)setminus A)的元素加入(A)即可。
定理(6.2)（强基交换定理）
对于任意拟阵(M)，若(M)有两个不相同的基(A,B)，那么(forall xin Asetminus B,exists yin Bsetminus A,s.t.A-{x}+{y},B-{y}+{x})都是(M)的基。
因为(B)是基，所以(B+{x})包含一个唯一的环(C)且(xin C)。所以有(xin cl(C-{x}))。由引理(1)可得(cl(C-{x})subseteq cl((Acup C)-{x}))，所以(xin cl((Acup C)-{x}))。由引理(2)可得(cl((Acup C)-{x})=cl(Acup C))。
因为(A)是基，所以(Ssubseteq cl(A)subseteq cl(Acup C))，即(cl((Acup C)-{x})=cl(Acup C)=S)。因此(cl((Acup C)-{x}))一定包含一个基，记之为(A')。
因为(A')和(A-{x})都是独立集，且有(|A-{x}|<|A|=|A'|)，所以一定存在(yin A'setminus(A-{x}),s.t.A-{x}+{y})是基。
因为(A'setminus(A-{x})subseteq C-{x}subseteq B)，所以一定存在(yin B,s.t.A-{x}+{y})是基。同时由于(C)是环，所以(B-{y}+{x})也是基。命题得证。
接下来我们将提出一种算法。从空集开始扩展，直到得到最大的独立集(A)。同时还可以构造出(T)，以此证明这就是我们要求的最大独立集。
定义(6.3)
对于拟阵(M=(S,I))和独立集(Ain I)，定义(M)中(A)的交换图(D_M(A))为(G=(V,E))。其中(V=S,E={(y,x)|xin Ssetminus A,yin A,A-{y}+{x}in I})。很显然(G)是一个二分图。
引理(6.4)
令(A,B)都是(M)的独立集且(|A|=|B|)，那么(D_M(A))中存在一个关于(Asetminus B)和(Bsetminus A)的完美匹配。
定义一个新的拟阵(M'=(S,I'),I'={A'in I||A'|le|A|})。那么(A,B)都是(M')的基。
然后利用强基交换定理即可递归证明。
定理(6.3)
令(A)是(M=(S,I))的独立集，(Bsubseteq Swedge|B|=|A|)。(D_M(A))中存在唯一的(Asetminus B)到(Bsetminus A)的完美匹配(Rightarrow Jin I)。
先转有向图，把不属于这个匹配的边反向，那么这一定是个拓扑图，然后给每个点标号使得边都从小号到大号，然后再利用反证法即可。
定义(6.4)
对于矩阵(M_1=(S,I_1),M_2=(S,I_2))和(Ain I_1cap I_2)，定义(A)的交换图(D_{M_1M_2}(A)=(V,E))。其中(V=S,E={<y,x>|xin Ssetminus A,yin A,A-{y}+{x}in I_1}cup{<x,y>|xin Ssetminus A,yin A,A-{y}+{x}in I_2})。
然后我们开始叙述算法流程。
( ext{1:})令(A=emptyset)，定义(X_1={x otin A|A+{x}in I_1},X_2={x otin A|A+{x}in I_2})。
( ext{2:})每次在交换图(D_{M_1M_2})中找到一条(X_1)到(X_2)的最短路(P)，然后令(A)变为(ADelta P(ADelta B=(Acup B)setminus(Acap B)))。
我们称这个过程为增广过程，每次增广会扩张恰好(1)个元素。
( ext{3:})重复增广过程直到找不到任意一条(X_1)到(X_2)路径，此时我们就得到了最大的(A)，并得到了(T={xin S|x)可以到达(X_2})。
( ext{4:})如果(X_1cap X_2)非空，那么我们将会直接拓展一个(X_1cap X_2)中的元素。
然后来证明这个算法的正确性。我们需要证明两点：
一是最后算法运行结束之后，(|A|=r_1(T)+r_2(Ssetminus T))。
二是算法运行中的任意一个时刻(ADelta P)都是独立集。
证明咕了，有空再说吧。
现在（假装）我们证明了上述算法的正确性，同时证明了最小最大定理，并给出了一个求拟阵交的算法。
时间复杂度
令(r=max(r_1(S),r_2(S)),n=|S|)，我们每次构建出来的图都是(n)个点，(rn)条边的图。
在无权图上找最短路的复杂度是(O(n+m))的，因此单次增广的复杂度就是(O(rn))的。
因为每次增广独立集中必然增加一个元素，所以增广次数不会超过(r)次。
因此拟阵交算法的复杂度为(O(r^2n))。
带权拟阵交
给定(f:S ightarrowmathbb R)，要求(maxlimits_{Ain I_1cap I_2}sumlimits_{ein A}f(e))。
给交换图中的点定义点权(w(e))：
(forall xin A,w(x)=-f(x))
(forall xin Ssetminus A,w(x)=f(x))
然后我们把增广找的路径变成：在路径上的点的点权和最大的情况下经过的边数最少的(X_1)到(X_2)的路径即可。
复杂度
求增广路径由(O(n+m))变成(O(nm))（因为有负权边所以只能用SPFA），所以总复杂度就是(O(r^2n^2))。
多个拟阵交
NP-Hard
拟阵的并
之后再说。