拟阵

(latest updated on 2020-08-10)

大量基础定义警告，参考了wiki和2018论文《浅谈拟阵的一些拓展及其应用》，如果想看大段详细证明请移步论文

拟阵的概念比较抽象，有多种定义方法，结合这些定义方法可以更具体地了解拟阵的基础性质

前言

很多问题可以转化为拟阵，但是并不是所有问题都可以通过简单的拟阵操作得到答案

在具体问题中，很多时候有着更优的算法解决拟阵运算无法解决的操作

但是对于一个奇怪的问题，如果转化为类似拟阵的操作后，就有很多性质可以拿过来套

拟阵的应用，更多还是用 诸多的性质 把复杂,抽象问题向更简单的方向转化(便于乱搞)

也可以便于简化问题的证明，所以这个东西了解一下也差不多了

(不会有人丧心病狂到专门出一个拟阵交的题吧)

符号及约定

$|S|$集合大小

$S-T$，删除$S$中在$T$中的元素

$a\Rightarrow b$若$a$则$b$

$a\Leftrightarrow b$，$a,b$等价

$a\in b$元素$a$是集合$b$中的一个元素

$a\sube b$，集合$a$是集合$b$的子集

$\exists$ 存在

$\forall$ 任意

幂集

一个集合$S$的所有$2^{|S|}$个子集构成的集合是$S$的幂即$P(S)$或者$2^S$

集族

给定集合$S$ 的一些子集构成的类$F$叫做$S$的子集族（或称S 上的集合族）,$F \sube 2^S$

用独立集定义拟阵(似乎是最直观的定义)

一个二元组$M=(E,I)$，其中$E$是基础集，$I$是$E$的一些子集构成的集族(即$I\sube 2^S$)，称之为独立集，在独立集中的子集称之为独立的

拟阵可以用独立集$I$定义，则$I$需满足性质:

1.空集：有$\emptyset \in I$，所以有$I\ne \emptyset$

2.遗传性：若$A\sube B,B\in I$，则$ A\in I$

3.扩充性：若$\exists A,B\in I,|A|>|B|$，则$\exists i\in A,(B\cup \{i\}) \in I$

例子：对于$S=\{1,2,3\}$，$\{\emptyset \},\{\emptyset,\{1\} \}$是合法的独立集，但$\{\emptyset,\{1\},\{2\},\{3\},\{2,3\} \}$不是，因为它不满足扩充性

$\{ \{1,2\},\{2,3\},\{1\},\{2\},\{3\},\{\emptyset \} \}$也是合法的独立集

对于$S=\{1,2,3,4,5\}$,$I=\{ \{1,2,3\},\{3,4,5\},\{1,2\},\{2,3\},\{1,3\},\{3,4\},\{3,5\},\{4,5\},\{1\},\{2\},\{3\},\{5\},\{\emptyset\} \}$不是合法的独立集，因为它不满足扩充性($A=\{1,2,3\},B=\{3,4\}$时)

用基底和基定义拟阵(似乎是最简洁的描述)

基底:$E$的一个独立的极大子集称为其的一个基底，独立的极大子集即其加入任意元素得到的子集不独立

基:$E$的基$B$为其所有基底构成的集合

拟阵可以用基$B$定义，则$B$需满足性质:

1.非空：$B\ne \emptyset$，最小的$B=\{\emptyset\}$

2.交换公理：对于两个基底$a,b$，若用$b$中$a$没有的元素换掉一个$a$中原先的元素，得到的集合依然是基底

推论：基底等大，即$\forall a\in B,b\in B,|a|=|b|$(否则就不满足扩充性)

例如：若$\{1,2\},\{1,3\}$是基底，则$\{2,3\}$也是基底(否则不满足扩充性)

可以得到拟阵的等价定义，且$I=\bigcup _{T\in B} 2^T$

用环路集定义拟阵

环路:$S$的一个子集是环路，则这个子集是一个极小的非独立集，即去掉任意一个元素都会称为独立集

所有环路构成的集合称为环路集$C$，如对于$E=\{1,2\},I=\{\emptyset,\{1\} \}$，环路集为$\{ \{2\} \}$

拟阵可以用环路集$C$定义，则$C$需满足性质：

1.$C$可以为空(此时$I=P(S)$)，且$\emptyset \not \in C$

2.环路互相之间不是真子集，即$\exists a\in C,b\in C,a\sube b\Rightarrow a=b$ (否则不满足遗传性)

3.若$\exists a\in C,b\in C,a\ne b$以及一个元素$i\in a\cap b$，则$a\cup b-\{i\}$不是独立集

推论：$A\sube I \Leftrightarrow \nexists B\in C,B\sube A$

环路不一定等大

环路和基底的一些关系

1.环路和基底之间不能通过加减一个元素转化

2.基底加上一个元素得到的非独立集恰好包含一个环路

拟阵的秩

拟阵的秩：拟阵的任意一个基底的元素个数是其秩$r$

为了同下文的秩函数相对应，也可说$\begin{aligned}r=\max_{R\in I} \{|R|\}\end{aligned}$，即最大的独立集大小

用秩函数定义拟阵

对于元素集$S$

若可以定义一个在$2^S$上的秩函数$r(T)$，满足以下性质:

1.大小有界:$r(T)\in[0,|T|]$

2.大小传递性:$A\sube B\Rightarrow r(A)\le r(B)$

3.次模性:$r(A\cup B)+r(A\cap B)\le r(A)+r(B)$

那么可以用这样的一个秩函数定义一个拟阵$M=(S,r)$，此时$r(T)$为$2^T$中极大的独立集大小，且拟阵的独立集就是$I=\{T|T\sube S,r(T)=|T|\}$

例子

均匀拟阵：$U_n^k=(S,I),|S|=n,I=\{T|T\sube S,|T|\leq k\}$

图拟阵：

对于无向图$G=(V,E)$，它的生成拟阵是$M=(E,\{T|T\sube E,T无环\})$

它的最大独立子集大小为$G$的最大生成森林边数，每个最大生成森林都是基底

匹配拟阵：

对于无向图$G=(V,E)$，它的匹配拟阵是$M=(V,\{T|T\sube V,存在一个边匹配覆盖T\})$

它的最大的独立子集大小为k最大匹配数，每个最优匹配的方案都是基底

异或线性基：

对于非负整数可重集合$S$，拟阵是$M=(S,\{T|T\sube S,T中的元素任意异或不会得到0\})$

(这是向量空间的线性基问题的一种)

注意分清楚 定义需要满足的条件 和 通过条件推导得到的性质 的区别 ，上面几种拟阵定义是等价的

一些应用

求最大权值独立子集

对于拟阵$M=(S,I)$，给每个$S$中每个元素一个非负权值，定义一个集合的权值为所有元素权值和，要求最大权值的独立子集

这是一个非常简单的问题，直接从大到小能加入就加入即可，设最终选出的集合为$P$

证明:

1.$P\in B$，否则可以再加入元素

2.假设存在更优解$Q\in B$，根据基底交换公理，一定可以用$P$中一个权值更大的元素换掉$Q$中一个元素，所以$Q$不是合法集合

在连通图拟阵上使用该算法，就是$\text{Kruskal}$最小生成数算法

在异或线性基上使用该算法，可以求得最大权值线性基

拟阵交

对于同基础集的拟阵$M_1=(S,I_1),M_2=(S,I_2)$，它们的交是独立集的交

但是它们的交不一定是拟阵

求解最大交:最小最大定理:

$\begin{aligned} \max_{A\in (I_1\cup I_2)} \{|T|\}=\min_{R\in S} \{r_1(R)+r_2(S-R)\}\end{aligned}$

这个东西的证明分为两步:

1.证明$\max\leq \min$

$|T|=|T\cap R|+|T\cap (S-R)|\leq r_1(R)+r_2(S-R)$

2.介绍找到两个最值的算法

这个算法的中心是，从空集开始扩展$T$，并且相应找到对应的$R$使得$|T|=r_1(R)+r_2(S-R)$，此时答案已经充分了

求解拟阵交的算法基于一个构造的图

对于当前的答案$T$，构造一个有向二分图，两侧点集分别为$T,S-T$

对于分别在两侧的点$x,y$，

存在$x\rightarrow y$的边: 当$T$中把$x$换成$y$之后是$M_1$的独立子集

存在$y\rightarrow x$的边: 当$T$中把$y$换成$x$之后是$M_2$的独立子集

设对于$I_1,I_2$可行的增广元素集合为$X_1,X_2 $(即加入元素后依然独立的集合)

每次的增广过程可以描述为:

(1.如果$X_1\cap X_2\ne \emptyset$，直接都加入$T$)

2.构图，找到一条从$X_1$的点出发，到达$X_2$的的最短的路径$P$(广搜即可)，将$I$变为$I\bigoplus P$ (这里原文是对称差，但是异或大家都懂哈)

当不存在增广时，找到了最大的$T$，此时对应合法的$R$为$\{e\in S|在图中存在e到达X_2的路径\}$

由于每次增广至少增加一个元素，该算法的复杂度上限为$O(r|S|^2)$，其中$r$为拟阵的秩，$|S|^2$为边数

带权拟阵交

每个元素带权

在增广时，图上每个点加上点权(加入为正，删除为负)，每次求出点权最短路进行增广即可

拟阵交的应用

二分图匹配问题

二分图匹配匈牙利算法 是 求解拟阵交的问题 的一种特殊情况

对于二分图$G=(V_1,V_2,E)$，构造

$M_1=(E,I=\{T\sube E|T中的边在V_1上没有公共点\})$

$M_2=(E,I=\{T\sube E|T中的边在V_2上没有公共点\})$

答案就是$M_1,M_2$交的最大值，匈牙利算法增广的过程是依次考虑$X_1$中的元素进行增广

(带权的二分图匹配问题，实际也是可以用拟阵解决的，但是好像$\text{KM}$还是最棒的)

拟阵交还可以解决一些看起来很抽象的 带有两个限制的 (可能带权) 的问题，比如论文里下面的这个例子

(Colorful Tree): 对于一个无向图，每条边给定一个颜色和一个权值，求颜色不能重复的最大生成树

类似这样的问题可以转化为拟阵交问题，但是这个东西的局限性实在太大，也没有人敢动

update:

有生之年竟然用上了这个东西？

**模拟赛有人搞了一个题:

对于一个无向图$G=(V,E),E=(u,v,w)$，其中$w$为每条边的颜色

要求选出一个最大的边集，满足：

1.每种颜色$i$选出的边不超过$c_i$条

2.选出的边不构成简单环

然后写了一次不太正规的拟阵交模板

令$M1$为个数的拟阵，$M2$为生成树拟阵

解释在代码里

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

int n,m,k;
int A[N],I[N];
// A为颜色个数的限制
int U[N],V[N],W[N],F[N];
// U,V,W为边
// F 为并查集
int Find(int x){ return F[x]==x?x:F[x]=Find(F[x]); }
int X[N],Y[N],P[N];

// 处理生成树的情况
vector <int> G[N];
int fa[N],fe[N],dep[N];
void dfs(int u,int f){
	dep[u]=dep[fa[u]=f]+1;
	for(int i:G[u]) {
		int v=U[i]==u?V[i]:U[i];
		if(v==f) continue;
		fe[v]=i,dfs(v,u);
	}
}

int main(){
	freopen("forget.in","r",stdin),freopen("forget.out","w",stdout);
	n=rd(),m=rd(),k=rd();
	rep(i,1,k) A[i]=rd();
	rep(i,1,m) U[i]=rd(),V[i]=rd(),W[i]=rd();
	rep(i,1,n) F[i]=i;
	while(1) {
		int f=0;
        // X, Y分别为 M1,M2的可拓展集合
        // I 记录已经在选边方案里的边
		rep(i,1,m) if(!I[i]) {
			X[i]=A[W[i]]>0,Y[i]=Find(U[i])!=Find(V[i]);
            // 如果X,Y有交，就直接加入集合
			if(X[i] && Y[i]) {
				A[W[i]]--,F[Find(U[i])]=Find(V[i]);
				I[i]=1,f=i;
			}
		} else X[i]=Y[i]=0;
		if(f) continue;
		static queue <int> que;
		while(!que.empty()) que.pop();
        // 预处理当前的生成树，便于处理M2的限制
		rep(i,1,n) G[i].clear();
		rep(i,1,m) if(I[i]) G[U[i]].pb(i),G[V[i]].pb(i);
		rep(i,1,n) dep[i]=0;
		rep(i,1,n) if(!dep[i]) dfs(i,0);
        // 从X中的某一个点出发
		rep(i,1,m) if(X[i]) que.push(i),P[i]=-1;
		else P[i]=0;
		f=0;
        // 广搜找交替 替换路径
		while(!que.empty()) {

			int u=que.front(); que.pop();
            // 找到一条满足X->Y的交替路径
			if(Y[u]){ f=u; break; }
			if(I[u]) {
                // u->v，交换之后满足M1
				rep(v,1,m) if(!P[v] && !I[v] && A[W[v]]+(W[u]==W[v])) P[v]=u,que.push(v);
			} else {
                // 满足拟阵M2，即交换这条边之后还是生成树，可以从目前生成树上的环上选取能够替换的边
				int x=U[u],y=V[u];
				if(Find(x)!=Find(y)) {
					rep(v,1,m) if(!P[v] && I[v]) 
						P[v]=u,que.push(v);
				} else {
					while(x!=y) {
						if(dep[x]<dep[y]) swap(x,y);
						int i=fe[x];
						if(!P[i]) P[i]=u,que.push(i);
						x=fa[x];
					}
				}
			}
		}
		if(!f) break;
        // 放置交替方案
		while(~f) {
			A[W[f]]+=I[f]?1:-1;
			I[f]^=1,f=P[f];
		}
		int cnt=0;
		rep(i,1,m) if(I[i]) cnt++;
        // 重构并查集
		rep(i,1,n) F[i]=i;
		rep(i,1,m) if(I[i]) F[Find(U[i])]=Find(V[i]);
	}
	int cnt=0;
	rep(i,1,m) if(!I[i]) cnt++;
	printf("%d\n",cnt);
	rep(i,1,m) if(!I[i]) printf("%d ",i);
}