弦图&区间图
Alioth_
2019-04-28 14:41:29
## 几个定义
### 诱导子图
在原图中选出几个点和他们之间的边组成的新图
### 团
是原图的诱导子图且为完全图
### 单纯点
这个点和它相连的点形成的诱导子图是一个团
### 弦图
任何一个大于等于四的环中都有一条弦（即最大只有三元环）
### 弦
环中的不相邻两点之间的一条边 把环分成更小环
### 完美消除序列
序列中每个点在序列中排在这个点后面的点的诱导子图中是一个单纯点
### 区间图
给定几个区间 编号后每个区间向和它相交的区间连边所构成的图 一定是弦图
## 最大势算法
求完美消除序列
倒序标号 每次找和最多已标号点相邻的未标号点（$lable$值最大的）把它标号 并更新相邻节点 标号即为这个点在完美消除序列中的位置
实现时用到双向链表存每个$lable$值
时间复杂度$\Theta(n+m)$
```cpp
// num中存点在完美消除序列中的编号
#include<bits/stdc++.h>
using namespace std;
const int maxn=10010;
const int maxm=1000100;
int n,m,tot,head[maxn],lable[maxn],num[maxn],Next[maxn<<1],pre[maxn<<1];
struct edge{
int to,nxt;
}e[maxm<<1];
void add(int x,int y){
e[++tot].to=y;e[tot].nxt=head[x];head[x]=tot;
e[++tot].to=x;e[tot].nxt=head[y];head[y]=tot;
}
void push(int x)//maxn+lable[x]为表头
{
Next[x]=Next[maxn+lable[x]];pre[Next[x]]=x;
pre[x]=maxn+lable[x];Next[pre[x]]=x;//插入到值为这个lable的表头的后面
}
void del(int x)
{
pre[Next[x]]=pre[x];
Next[pre[x]]=Next[x];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
}
for(int i=1;i<=n;i++)push(i);//对每个势值开一个双向链表
int ans=0,now=0;
for(int k=n;k;k--,now++)//now为当前最大的lable值 k倒着编号
{
while(!Next[maxn+now])now--;//找到有lable值的最大未标号节点
int x=Next[maxn+now];
del(x);
num[x]=k;//标号
int sum=1;
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(!num[y]){//未标号节点
del(y);
++lable[y];//势+1
push(y);
}
else ++sum;//y与x相邻 且y未标号 即y为完美消除序列中在x后面的点
//根据定义 x在后面这些点的诱导子图中为单纯点 与相连的这些点构成了一个团 计算贡献
}
ans=max(ans,sum);
}
cout<<ans;
}
```
## 应用
### 1.判断一个图是不是弦图
**一个图是弦图当且仅当它存在一个完美消除序列**
在构建完美消除序列时判断当前点和与它相邻的且在序列中排在这个点后面的点（即在这个点之前标号的点）是否构成一个团
```cpp
int flag=0;
for(int k=n,now=0;k;k--,now++)
{
while(!Next[now+maxn])now--;
int x=Next[now+maxn];
del(x);
num[x]=k;
int sum=1;
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(!num[y]){
del(y);
lable[y]++;
push(y);
}
}
int point=0;
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(num[y]>num[x]&&num[y]<num[point])
point=y;
}
if(!point)continue;
vis[point]=1;
for(int i=head[point];i;i=e[i].nxt)
vis[e[i].to]=1;
for(int i=head[x];i;i=e[i].nxt)
if(num[e[i].to]>num[x]&&!vis[e[i].to]){
flag=1;break;
}
memset(vis,0,sizeof(vis));
}
```
### 2.求弦图最小染色数
**定理：最小染色数等于最大团**
求完美消除序列时顺便求出这个单纯点所在环的大小
如$P3196$神奇的国度
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=10010;
const int maxm=1000100;
int n,m,tot,head[maxn],lable[maxn],num[maxn],Next[maxn<<1],pre[maxn<<1];
struct edge{
int to,nxt;
}e[maxm<<1];
void add(int x,int y){
e[++tot].to=y;e[tot].nxt=head[x];head[x]=tot;
e[++tot].to=x;e[tot].nxt=head[y];head[y]=tot;
}
void push(int x)//maxn+lable[x]为表头
{
Next[x]=Next[maxn+lable[x]];pre[Next[x]]=x;
pre[x]=maxn+lable[x];Next[pre[x]]=x;//插入到值为这个lable的表头的后面
}
void del(int x)
{
pre[Next[x]]=pre[x];
Next[pre[x]]=Next[x];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
}
for(int i=1;i<=n;i++)push(i);//对每个势值开一个双向链表
int ans=0,now=0;
for(int k=n;k;k--,now++)//now为当前最大的lable值 k倒着编号
{
while(!Next[maxn+now])now--;//找到有lable值的最大未标号节点
int x=Next[maxn+now];
del(x);
num[x]=k;//标号
int sum=1;
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(!num[y]){//未标号节点
del(y);
++lable[y];//势+1
push(y);
}
else ++sum;//y与x相邻 且y未标号 即y为完美消除序列中在x后面的点
//根据定义 x在后面这些点的诱导子图中为单纯点 与相连的这些点构成了一个团 计算贡献
}
ans=max(ans,sum);
}
cout<<ans;
}
```
### 3.求弦图点的最大独立集或最小团覆盖
两者相等（每个点都在后面的点中形成一个团）
构建出完美消除序列后遍历一遍序列 **点**能选就选
### 4.求弦图的极大团（最大团）=染色数
顺着完美消除序列判断，每个点都是单纯点，比较他们在后面的点中形成的团的大小
## 区间图
#### 区间图的一个完美消除序列为所有区间按右端点从小到大排序
### 1.从若干个区间中选最多的不相交区间
求最大独立集 (直接排序求出完美消除序列做)
### 2.有$n$个积木 高度均为1 宽度为$Li$到$Ri$ 选择一个下落顺序使高度尽量小
即区间图最小染色（同色在一行）
下落顺序 按照颜色顺序下落
建出区间图用排序后的顺序作为完美消除序列依次处理每个点