Reincarnation

正因为梦易碎，才格外美好。

弦图 & 完美消除序列

发表于 更新于 分类于 ，
本文字数： 11k 阅读时长 ≈ 10 分钟

引弓而射，贯穿长空。

弦图

弦图（）是一种定义在简单无向图上的特殊图论结构。

定义

设 是一个简单无向图，我们用 来表示图上的结点。如果称 构成了一个环（），当且仅当 均有边相连，则该环长度为 。

定义一个图 是弦图，当且仅当 中所有长度 的环，一定存在一条连接环上不相邻两点的无向边，此时称这条边是该环的弦（）。

这里还可以通过生成子图改写弦图的定义：简单无向图 是弦图，当且仅当不存在长度 的结点序列 使得 包含且仅包含 边。

什么是生成子图

设 是无向图， 是原图的一个结点子集。定义 关于 的生成子图 是以 为顶点集的图，其边集是 中两端都在 里的所有边。

生成子图又称导出子图。

定义申明

为了后期方便理解与表示，这里我们再给出一些有关图论的定义：

完全图

对于图 ，如果 ，都有 ，则 为完全图。

团

一个团是一个图的完全子图，即对于图 的一个结点子集 ，如果满足 的导出子图是一个完全图，则称其为 的团。

点割集

若点集 是 的点割集，则满足在原图中删除 的导出子图后， 不连通。

极小点割集

若点集 是 的极小点割集，那么不存在 的点割集 满足 。

最大团 / 极大团

最大团是一个图中点数最多的团。

若点集 的导出子图是极大团，则不存在点集 的导出子图是团，且 。

单纯点

设与结点 相连的点集为 ，若 为单纯点，则点集 的导出子图是一个团。

完美消除序列

令 ，完美消除序列是一个 的排列 ，满足 在点集 的导出子图中是单纯点。

一个无向图为弦图，当且仅当其存在完美消除序列。而一个弦图的完美消除序列不一定唯一。

最大势算法（MCS）

该算法能在 的时间内求出完美消除序列。

不严谨性

需要注意的是， 算法即使在非弦图中也能求出一个序列，但显然这并不是完美消除序列。所以求解之后，我们需要使用求出序列来判断当前无向图是否为弦图。

做法 & 证明

设 表示点 与已标记点相邻的个数，初始时所有点未被标记。

  1. 找到 最大的点 ，插入到完美消除序列的开头。标记 ；
  2. 更新其余点的 值。
  3. 返回至第 步直到所有结点都在完美消除序列中。

设 表示 在生成序列中的位置。

那么如果该序列是完美序列，则等价于对于任意序列中的元素 ，若存在 且 ，则一定有 。

这里我们使用反证法，如果 ，那么为了保证 ，一定存在结点 满足 。且 ，且 。但显然，这样会出现一个长度为 的环 ，且这个环上无弦。

然后我们考虑 的情况，因为 ，而 。为了保证 ，则一定存在点 使得 ，且 。否则依然会出现长度 的环。

反之如果有 ，那么 ，为了保证 ，一定也会存在 满足 且 。否则亦然。

而 加入后回到第一种情况的讨论，但 依然是完美消除序列的元素，所以 也会成为 继续分析，不断引入新结点，一定会触发矛盾。

每一条边至多会产生一个新的元素进入序列，但有效更新只会有 次，所以边贡献为 ，总时间复杂度不超过 。

实现

倒序对每个结点标号，动态维护 ，取出 并插入至完美消除序列。

最后插入顺序的倒序就是求出的完美消除序列。

参考实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
std::vector<int>Edges[MAXN],vec[MAXN];
bool Vis[MAXN],Mrk[MAXN];
int Deg[MAXN],Arr[MAXN],Hash[MAXN];
inline void Mcs()
{
	for(int i=1;i<=N;++i) vec[0].push_back(i);
	for(int cnt=N,p=0;cnt;--cnt)
	{
		int cur=0;
		while(!cur)
		{
			while(!vec[p].empty()&&Hash[vec[p].back()]) vec[p].pop_back();
			if(vec[p].empty()) --p;
			else cur=vec[p].back();
		}
		Arr[cnt]=cur,Hash[cur]=cnt;
		for(int v:Edges[cur])
			if(!Hash[v])
			{
				vec[++Deg[v]].push_back(v);
				if(Deg[v]>p) ++p;
			}
	}
}

代码中的 Arr[] 就是最后的完美消除序列。

应用

弦图判定

前文提到过，仅有弦图存在完美消除序列，所以我们可以通过 先求出一个序列，再通过这个序列反过来验证该无向图。

首先有一个暴力的 算法，但那显然不是我们希望的，我们希望这个判定算法能够和 拥有同等的效率。

对于完美消除序列 ，考虑现在我们已经判定出 是一个完美消除序列，现在了判断 是否为完美消除序列。

设 与 中直接相连的点为 ，其中满足 。根据定义，一定有 的导出子图是完全图。

而 本来就和其它结点相连，所以只需要 的导出子图是完全图即可。

而对于 ，如果其为完美消除序列，那么如果 与其它结点有边相连，则 的导出子图一定是完全图。

以此类推，我们对于每一个 ，分别求出其对应的 并判断 是否与其它结点直接相连即可。

直接把 压成哈希表查询即可。时间复杂度 。

参考实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
inline bool check()
{
	for(int i=1;i<=N;++i)
	{
		int cur=Arr[i];
		int Mn=N+1,id=0,tot=0;
		Vis[cur]=1;
		for(int v:Edges[cur])
			if(!Vis[v])
			{
				Mrk[v]=1,++tot;
				if(checkMin(Mn,Hash[v])) id=v;
			}
		if(!tot) continue;
		int sum=1;
		for(int v:Edges[id]) if(Mrk[v]&&v!=id) ++sum;
		for(int v:Edges[cur]) if(!Vis[v]) Mrk[v]=0;
		if(sum!=tot) return 0;
	}
	return 1;
}

题目简介

题目名称：
题目来源：

评测链接：https://www.spoj.com/problems/FISHNET/

形式化题意：判断一个图是否为弦图。多测。

数据范围：

AC Code
 
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
// ----- Eternally question-----
// Problem: Fishing Net
// Contest: SPOJ - Classical
// URL: https://www.spoj.com/problems/FISHNET/
// Memory Limit: 1536 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-09-23 16:10:05
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e4+10;
int N,M;
std::vector<int>Edges[MAXN],vec[MAXN];
bool Vis[MAXN],Mrk[MAXN];
int Deg[MAXN],Arr[MAXN],Hash[MAXN];
inline void Mcs()
{
	for(int i=1;i<=N;++i) vec[0].push_back(i);
	for(int cnt=N,p=0;cnt;--cnt)
	{
		int cur=0;
		while(!cur)
		{
			while(!vec[p].empty()&&Hash[vec[p].back()]) vec[p].pop_back();
			if(vec[p].empty()) --p;
			else cur=vec[p].back();
		}
		Arr[cnt]=cur,Hash[cur]=cnt;
		for(int v:Edges[cur])
			if(!Hash[v])
			{
				vec[++Deg[v]].push_back(v);
				if(Deg[v]>p) ++p;
			}
	}
}
inline bool check()
{
	for(int i=1;i<=N;++i)
	{
		int cur=Arr[i];
		int Mn=N+1,id=0,tot=0;
		Vis[cur]=1;
		for(int v:Edges[cur])
			if(!Vis[v])
			{
				Mrk[v]=1,++tot;
				if(checkMin(Mn,Hash[v])) id=v;
			}
		if(!tot) continue;
		int sum=1;
		for(int v:Edges[id]) if(Mrk[v]&&v!=id) ++sum;
		for(int v:Edges[cur]) if(!Vis[v]) Mrk[v]=0;
		if(sum!=tot) return 0;
	}
	return 1;
}
inline void init()
{
	for(int i=0;i<=N;++i)
	{
		Edges[i].clear(),vec[i].clear();
		Hash[i]=Deg[i]=Arr[i]=0,Vis[i]=Mrk[i]=0;
	}
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	while(true)
	{
		read(N,M);
		if(N==0&&M==0) break;
		init();
		for(int i=1,u,v;i<=M;++i)
		{
			read(u,v);
			Edges[u].push_back(v),Edges[v].push_back(u);
		}
		Mcs();
		puts(check()?"Perfect":"Imperfect");
		puts("");
	}
	return 0;
}
/*

*/

弦图运用 I

题目简介

题目名称：简单图论题
题目来源：省选模拟

形式化题意：给定一个无向图 ，现在要求给 条边定向，满足定向后的图 是一个 ，且对于任意 ， 之间一定存在一条边。

数据范围：

对于原图而言，不能出现无向图定义下的长度 的环，这个弦的定义类似，所以我们从弦图方向考虑构造解。

我们考虑完美消除序列，此时任意一个点向后连边都是一个团，正好与题目的条件相对应，而如果这个图是一个弦图，那么一定存在完美消除序列，

所以我们判断这个图是否为弦图，也就判断是否有解，然后如果有解，我们构造出其完美消除序列，作为 的拓扑序，然后根据拓扑序构造出 即可。

时间复杂度 。

AC Code
 
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include<bits/stdc++.h>
clock_t t=clock();
namespace my_std{
    using namespace std;
    #define pii pair<int,int>
    #define fir first
    #define sec second
    #define MP make_pair
    #define rep(i,x,y) for (int i=(x);i<=(y);i++)
    #define drep(i,x,y) for (int i=(x);i>=(y);i--)
    #define go(x) for (int i=head[x];i;i=e[i].nxt)
    #define templ template<typename T>
    #define sz 202020
    typedef long long ll;
    typedef double db;
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    templ inline T rnd(T l,T r) {return uniform_int_distribution<T>(l,r)(rng);}
    templ inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
    templ inline bool chkmin(T &x,T y){return x>y?x=y,1:0;}
    templ inline void read(T& t)
    {
        t=0;char f=0,ch=getchar();double d=0.1;
        while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
        while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();
        if(ch=='.'){ch=getchar();while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();}
        t=(f?-t:t);
    }
    template<typename T,typename... Args>inline void read(T& t,Args&... args){read(t); read(args...);}
    char __sr[1<<21],__z[20];int __C=-1,__zz=0;
    inline void Ot(){fwrite(__sr,1,__C+1,stdout),__C=-1;}
    inline void print(register int x)
    {
        if(__C>1<<20)Ot();if(x<0)__sr[++__C]='-',x=-x;
        while(__z[++__zz]=x%10+48,x/=10);
        while(__sr[++__C]=__z[__zz],--__zz);__sr[++__C]='\n';
    }
    void file()
    {
        #ifdef NTFOrz
        freopen("a.in","r",stdin);
        #endif
    }
    inline void chktime()
    {
        #ifndef ONLINE_JUDGE
        cout<<(clock()-t)/1000.0<<'\n';
        #endif
    }
    #ifdef mod
    ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x%mod) if (y&1) ret=ret*x%mod;return ret;}
    ll inv(ll x){return ksm(x,mod-2);}
    #else
    ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x) if (y&1) ret=ret*x;return ret;}
    #endif
//	inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}
}
using namespace my_std;

int n,m;
struct Edge {int t,nxt;Edge(){}Edge(int a,int b):t(a),nxt(b){}}e[sz<<1];
int head[sz];

int num[sz],id[sz];

int d[sz],H[sz];
int pre[sz],nxt[sz];
bool vis[sz];

void mcs(int n) 
{
	for(int i=1;i<=n;i++) 
	{
		if (H[0]) pre[H[0]]=i;
		nxt[i]=H[0];
		H[0]=i;
	}
	int r=0;
	for(int i=1;i<=n;i++) 
	{
		while (!H[r]) r--;
		int x=H[r];
		vis[x]=1;
		num[i]=x;id[x]=i;
		if (nxt[x]) pre[nxt[x]]=0;
		H[r]=nxt[x];
		go(x) if (!vis[e[i].t]) 
		{
			int u=e[i].t;
			if (!pre[u]) H[d[u]]=nxt[u];
			if (pre[u]) nxt[pre[u]]=nxt[u];
			if (nxt[u]) pre[nxt[u]]=pre[u];
			d[u]++;
			r=max(r,d[u]);
			if (H[d[u]]) pre[H[d[u]]]=u;
			nxt[u]=H[d[u]];
			pre[u]=0;
			H[d[u]]=u;
		}
	}
}

vector <int> vt[sz];
int vis2[sz];

bool check(int n) 
{
	rep(i,1,n)
	{
		int maxn=0;
		for(int j=head[i];j;j=e[j].nxt) if (id[e[j].t]<id[i]&&id[e[j].t]>id[maxn]) maxn=e[j].t;
		if (maxn) vt[maxn].push_back(i);
	}
	rep(i,1,n)
	{
		for(int j=head[i];j;j=e[j].nxt) if (id[e[j].t]<id[i]) vis2[e[j].t]=i;
		rep(j,0,(int)vt[i].size()-1) 
		{
			int x=vt[i][j];
			for(int k=head[x];k;k=e[k].nxt) if (id[e[k].t]<id[i]&&vis2[e[k].t]<i) return 0;
		}
	}
	return 1;
}

int main() 
{
	read(n,m);
	int x,y;
	rep(i,1,m)
	{
		read(x,y);
		e[2*i-1]=Edge(y,head[x]);head[x]=2*i-1;
		e[2*i]=Edge(x,head[y]);head[y]=2*i;
	}
	mcs(n);
	if (!check(n)) return puts("-1"),0;
	rep(i,1,m) putchar((id[e[2*i-1].t]>id[e[2*i].t])?'1':'0');
	return 0;
}

相关文章