弦图

弦图

• 弦图是一种有着特殊性质的图，部分 (NP-Hard) 问题可以在弦图上解决

性质/定义：

1. 团：点集，满足任意两点之间都有边相连
2. 团数： 最大团的点数
3. 最小染色数：满足任意一条边所连两点颜色不同的情况下，颜色种类数的最小值
4. 最大独立集：点集，满足任意两点之间没有边直接相连
5. 最小团覆盖：用团覆盖整张图的最少团数
6. 弦图：任意长度大于 (3) 的环都有一个弦
7. 单纯点：若点 (x) 和与它相连的所有的点的导出子图为一个团，那么我们称 (x) 为单纯点
8. 完美消除序列：1到 (n) 的排列{(v_1,v_2,dots v_n)} 满足 (v_i) 在 {(v_{i+1}dots v_n)} 的导出子图中是单纯点

结论：

1. 团数 (le) 色数

   证明： 对最大团的导出子图进行染色，至少需要等于团数种颜色

2. 最大独立集数 (le) 最小团覆盖数

   证明：每个团中只可能选 (0/1) 个

3. 弦图的任意导出子图还是弦图

4. 弦图的任意两点之间的最小点割集的导出子图一定是一个团

5. (u,v)的点割集将弦图划分成许多连通块，点割集中一定包含 (u,v) 所在连通块的点

   （搞不懂这个结论有什么用）

6. 任何一个弦图都有至少一个单纯点，任何一个不是完全图的弦图都有至少两个不相邻的单纯点

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

相关知识点

• 弦图的判定：

  1. 最大势算法 (MCS)：求一张弦图的完美消除序列，逆序给点编号，记 (label_x) 表示与 (x) 相邻的已标号的点的个数，每次找出 (label) 最大的点进行标号，并且更新 (label) 复杂度 (O(n+m))

  2. 完美消除序列的判定：对于 (MCS) 求出的序列，我们要判断其是否是一个完美消除序列，从前向后遍历序列，从前向后找出与 (v_i) 在原图上直接相邻的点 (x_1,x_2dots x_k) 判断 (x_1) 与 (x_i) 是否都有点相连，复杂度 (O(n+m))

  3. 代码：

     #include<bits/stdc++.h>
     #pragma GCC optimize(2)
     #define pii pair<int,int>
     #define mk(x,y) make_pair(x,y)
     #define lc rt<<1
     #define rc rt<<1|1
     #define pb push_back
     #define fir first
     #define sec second
     #define inl inline
     #define reg register
     
     using namespace std;
     
     namespace zzc
     {
     	inline int read()
     	{
     		int x=0,f=1;char ch=getchar();
     		while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
     		while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
     		return x*f;
     	}
     	
     	const int maxn = 1005;
     	const int maxm = 2e6+5;
     	int n,m,ti,now;
     	int g[maxn][maxn],label[maxn],seq[maxn],rk[maxn];
     	vector<int> v[maxn],son[maxn];
     	bool ins[maxn];
     	
     	void msc()
     	{
     		int best=0;
     		for(int i=1;i<=n;i++) v[0].pb(i),ins[i]=false;
     		for(int i=n;i;i--)
     		{
     			bool flag=false;
     			while(!flag)
     			{
     				for(int j=v[best].size()-1;j>=0;j--)
     				{
     					if(!ins[v[best][j]])
     					{
     						now=v[best][j];
     						flag=true;
     						break;
     					}
     					else v[best].pop_back();
     				}
     				if(!flag) best--;
     			}
     			seq[i]=now;rk[now]=i;ins[now]=true;
     			for(auto j:son[now])
     			{
     				if(!ins[j])
     				{
     					v[++label[j]].pb(j);
     					best=max(best,label[j]);
     				}
     			}
     		}
     	}
     	
     	bool check()
     	{
     		for(int i=1;i<=n;i++)
     		{
     			now=-1;
     			for(auto j:son[seq[i]])
     			{
     				if(rk[j]<rk[seq[i]]) continue;
     				if(now==-1||rk[now]>rk[j]) now=j;
     			}
     			for(auto j:son[seq[i]])
     			{
     				if(rk[j]<rk[seq[i]]) continue;
     				if(now!=j&&g[now][j]!=ti)
     				{
     					return false;
     				}
     			}
     		}
     		return true;
     	}
     	
     	void clear()
     	{
     		for(int i=0;i<=n;i++) son[i].clear(),v[i].clear(),label[i]=0;
     	}
     	
     	void work()
     	{
     		int a,b;
     		n=read();m=read();
     		while(n||m)
     		{
     			ti++;
     			for(int i=1;i<=m;i++)
     			{
     				a=read();b=read();
     				g[a][b]=g[b][a]=ti;
     				son[a].pb(b);son[b].pb(a);
     			}
     			msc();
     			if(check()) puts("Perfect");
     			else puts("Imperfect");
     			clear();
     			n=read();m=read();
     		}
     	
     	}
     
     }
     
     int main()
     {
     	zzc::work();
     	return 0;
     }
     
     

• 弦图的极大团：求出完美序列，找出每一个点作为单纯点时和序列后面的点形成的团，判断是否为最大团，一张图最多有 (n) 个极大团

• 弦图的色数/团数： 从后往前对完美消除序列上的每一个点进行染色，共用了 (t) 种颜色，由于团上每一个点都不同色所以 (t=团数ge 色数) 由结论 1 可得 $色数ge 团数 $ 所以 团数=色数 ，染色复杂度 (O(n+m)) ，特别，如果不要求染色方案数 团数 = (max|{x}+N(x)|=max(label_x+1))

• 弦图最大独立集/最小团覆盖：对于完美消除序列从前向后不断选能选的点，然后每次更新一下不能选的点，复杂度 (O(n+m))

例题：

SP5446 FISHNET - Fishing Ne

传送门

没什么可说的，弦图判定裸题

P3196 [HNOI2008]神奇的国度

传送门

没什么可说的 +1 , 弦图色数裸题

P3852 [TJOI2007]小朋友

传送门

没什么可说的 +2, 弦图最大独立集裸题