弦图:图上求解多种复杂问题的简单情况_nflsoj npc问题 弦图

正题

       如果想要严格证明,请到这里,这里只是用来背结论和性质的.

       弦图:每个大小>=4的环都必有一条不连接相邻点的边,注意辨析,只有三元环的图不一定是弦图,像一个六边形,中间有一个点,这个点连向所有六边形上的点,由于外部的六边形形成了一个环,但是没有一条不连接相邻点的边,所以这个图不是弦图.

       团:完全图

       诱导子图:点集是原图的点集的子集,边集是是原图边集的子集且满足两端点在点集内.

       弦图的诱导子图是弦图

       单纯点:与有连边的点的诱导子图形成了一个团.

       弦图至少有一个单纯点

       完美消除序列:一个排列,满足$v_i\to v_n$构成的诱导子图中,$v_i$是单纯点

       一个图是弦图当且仅当它有完美消除序列

      如何求解完美消除序列?

      倒着构造,每次选出与已加入完美消除序列点连边最多的点,具体用一个n个vector来维护每一个度数有哪些点.证明前往这里.

     

scanf("%d %d",&n,&m);
int x,y;
for(int i=1;i<=m;i++){
	scanf("%d %d",&x,&y);
	g[x][y]=g[y][x]=true;
}
for(int i=1;i<=n;i++) V[0].push_back(i),label[i]=0;
int top=0;
for(int i=n;i>=1;i--){
	int now=0;
	while(!now){
		for(int j=V[top].size()-1;j>=0;j--) if(!tf[V[top][j]]){now=V[top][j];break;}
		else V[top].pop_back();
		if(now) break;top--;
	}
	V[top].pop_back();
	a[i]=now;tf[now]=true;
	for(int j=1;j<=n;j++) if(g[now][j]	&& !tf[j]){
		label[j]++;
		V[label[j]].push_back(j);
		top=max(top,label[j]);
	}
}

      a序列就是完美消除序列.

      若图不是弦图,则a不是完美消除序列,运用定义,问问每一个$v_i$是不是单纯点即可,直接暴力问是否为单纯点复杂度爆表,实际上只需要问$v_i$向后连接的第一个点$v_j$,是否与$v_i$向后连接的其他点有边相连即可,因为已经保证了$v_j$是一个单纯点,这样就可以保证$v_j$与$v_i$后面连接的点一定形成一个团,从而证明$v_i$也是一个单纯点,若$v_j$没有这样的连边,也很容易证明$v_i$不是单纯点.

      最大独立集=最小团覆盖

      首先对于所有无向图,最大独立集<=最小团覆盖,因为每一个团里面至多选出一个点当最大独立集的点.

      对于完美消除序列,从前向后贪心,每次如果当前点$v_i$没有被覆盖,则选为最大独立集的点,将后面与$v_i$连接的点标记为选中即可.

      发现每一次覆盖一些点时,恰好形成了团,设一共分了t次,则有t<=最大独立集,最小团覆盖<=t,所以就有最大独立集=最小团覆盖=t

int ans=0;
for(int i=1;i<=n;i++) if(!tf[a[i]]){
	ans++;
	for(int j=1;j<=n;j++) if(g[a[i]][j]) tf[j]=true;
}

      色数=团数

      色数就是将整张图染色所需要的最小颜色,团数就是整张图的最大团的点数.

      首先有团数<=色数,因为将一个团染色至少需要团数这么多个颜色.

      考虑在完美消除序列上从后往前构造,对于一个点i,只要它与后面连接的点都不相同就可以了,这样色数就必定<=团数,从而证明色数=团数.

for(int i=1;i<=n;i++) mmax=max(mmax,label[i]);