《欧拉图相关的生成与计数问题探究》学习笔记
基本概念
定义： 度（自环统计计两次），入度，出度。奇顶点，偶顶点，孤立点。连通，连通图，弱连通图。桥。路径，回路。欧拉回路（每条边经过恰一次），欧拉路径。欧拉图（存在欧拉回路），半欧拉图（存在欧拉路径）。简单图。
欧拉图的判定
无向欧拉图
定理： 一张无向图为欧拉图当且仅当该图连通且无奇顶点。
定理： 一张无向图为半欧拉图当且仅当该图连通且奇顶点数恰为两个。此时两个奇顶点为欧拉路径的起点和终点。
定理： 若一张无向连通图有 (2k) 个奇顶点，则可以用 (k) 条路经将该图的每条边经过一次，且至少要用 (k) 条路径。
有向欧拉图
定理： 一张有向图为欧拉图当且仅当该图弱连通且所有点的入度等于出度。
定理： 一张有向图为半欧拉图当且仅当该图弱连通且恰有一个点 (u) 入度比出度小 (1)，一个点 (v) 入度比出度大 (1)。此时 (u) 和 (v) 分别为欧拉路径的起点和终点。
定理： 若一张有向弱连通图中所有节点的入度与出度之差的绝对值之和为 (2k)，则可以用 (k) 条路经将该图的每条边经过一次，且至少要用 (k) 条路径。
欧拉回路的生成
问题： 给定无向欧拉图 (G)，求出 (G) 的一条欧拉回路。
Fleury 算法
维护当前经过 (k) 条边的欧拉路径 (p_k)，并且保证任意时刻未访问的边构成的子图 (G_k=Gsetminus p_k) 除去孤立点后连通。具体地，可以每次暴力枚举待扩展的边，删掉它然后 bfs/dfs 判断连通性。时间复杂度 (O(m^2))。
同时，该算法可以通过回溯来求一张无向欧拉图（半欧拉图）的所有欧拉回路（路径）。
Hierholzer 算法
随意选取起始点进行 dfs，沿着任意未访问的边走到相邻节点，直至无路可走，此时必然会回到起点形成回路。若仍有边为访问过，则退栈时找到有未访问边的节点，以它开始求出另一回路并与之前回路拼接。如此反复直到所有边都被访问。时间复杂度 (O(m))。
同时，该算法可以用于求解有向图的情况、求解欧拉路径、求解对字典序有要求的问题、求最少路径数将图的所有边经过一次。
欧拉图相关的性质
定理： 对于任意无向连通图，一定存在回路使得每条边经过恰好两次。进一步地，存在回路使得每条边的两个方向各经过一次。
证明： 将该图的每一条边变成两条重边，能够得到无向欧拉图；将该图的每一条边变成两条方向相反的有向边，能够得到有向欧拉图。
例题： （CF 788 B）
定理： 一张无向图有圈分解当且仅当该图无奇顶点。
例题： （BZOJ 3706）
定理： 对于不存在欧拉回路的图，若最少用 (a) 条路径将图中的每条边经过一次，最少在图中中加入 (b) 条边使其成为欧拉图，那么 (a=b)。
例题： （CF 209 C）
欧拉图的生成问题
De Bruijin 序列
问题： 求出一个 (2^n) 位的环形 0/1 串，满足所有 (2^n) 个长为 (n) 的子串恰为所有 (2^n) 个 (n) 位 0/1 串。
解法： 构造一个 (2^{n-1}) 个点，(2^n) 次方条边的有向图。其中每个点代表一个 (n-1) 位 0/1 串，每条边代表一个 (n) 位 0/1 串。其中有向边 (x_1x_2ldots x_n) 连接 ((x_1,x_2ldots x_{n-1},x_2x_3ldots x_n))。于是原问题等价于求此图上的欧拉回路。由于此图的每个节点都恰有两条出边和两条入边，所以解一定存在。
同时，该序列可以扩展到 (k) 进制。
例题： （POJ 1780）
混合图欧拉回路
问题： 给定包含有向边和无向边的弱连通图，求出该图的一条欧拉回路或判断无解。
解法： 将所有无向边定向之后就容易解决，但要满足定向之后所有点的入度等于出度。考虑先随意定向，然后通过网络流进行调整、构造。
例题： （Luogu 3511）
中国邮递员问题
问题： 给定有向带权连通图，求出一条总边权和最小的回路，使得经过每条边至少一次。
解法： 原问题等价于复制一些边若干次，使得所有点入度等于出度，最小化总边权。可以转化成费用流问题进行求解。
问题： 给定无向带权连通图，求出一条总边权和最小的回路，使得经过每条边至少一次。
解法： 原问题等价于复制一些边若干次，使得所有点度数为偶，最小化总边权。容易发现每次选定两个奇顶点，复制它们最短路上的边是使它们变为偶顶点的最佳方案。于是对所有奇顶点进行一般图最小权完美匹配即可。
欧拉图相关的计数
欧拉图计数
问题： 求 (n) 个节点无奇顶点的有标号简单无向图个数。
解法： 考虑 (n) 号点的连边，与 (n-1) 个节点的有编号任意简单无向图进行双射。答案为 (2^{inom{n-1}{2}})。
问题： 求 (n) 个节点的有标号简单连通欧拉图个数。
解法： 容斥（枚举 (n) 号点所在连通块的大小）/生成函数（ln/求逆）。
欧拉子图计数
问题： 给定 (n) 个节点 (m) 条边的无向连通图，求该图有多少无奇顶点的支撑子图。
解法： 考虑一棵生成树。每条非树边都有选或不选两种选择，所有非树边都确定后树边只有一种可能的选择方案。答案为 (2^{m-n+1})。
问题： 给定 (n) 个节点 (m) 条边的无向图，求该图有多少无奇顶点的支撑子图。
解法： 对每个连通块单独计算，再累乘。
欧拉回路计数
问题： 给定 (n) 个节点 (m) 条边的有向欧拉图，求从 (1) 号点开始的欧拉路径数。
解法： 考虑一种构造方案。找到一棵以 (1) 号点为根的内向树，对于一个点所有不在树上的出边指定顺序。此方案与从 (1) 号点开始的欧拉路径构成双射：
- 此方案 ( ightarrow) 欧拉路径：考虑 Fleury 算法的过程。对于每个点，先按照指定顺序访问不在树上的出边，再访问树边。容易证明方案合法。
- 欧拉路径 ( ightarrow) 此方案：将除了一号点之外的所有点在路径中访问的最后一条出边设为树边，其余边按访问次序决定顺序。容易证明选择的树边无环。
答案为 (T_1d_1!prod_{i=2}^n(d_i-1)!)。其中 (d_i) 为 (i) 号点的出度，(T_i) 为以 (i) 号点为根的内向树个数（可以用矩阵树定理求出）。
问题： 给定 (n) 个节点 (m) 条边的有向欧拉图，求欧拉回路数。 （BEST 定理）
解法： 考虑用同样的方法求出。为了去重，钦定 (1) 号点的一条出边为第一条访问边。答案为 (T_1prod_{i=1}^n(d_i-1)!)。
问题： 给定 (n) 个节点 (m) 条边的有向半欧拉图，求欧拉路径数。
解法： 将该图添加一条有向边变成欧拉图，新图的欧拉回路和原图的欧拉路径构成双射，用 BEST 定理计算即可。
例题
CF 788 B
简要题意
给定 (n) 个点，(m) 条边的无向连通图。求出有多少条路径满足经过其中 (m-2) 条边各两次，剩下两条边各一次。两条路径不同当且仅当存在一条边在两条路径中的经过次数不同。
题解
将该图的每一条边变成两条重边，原问题转化为删除两条边使得奇顶点个数 (leq 2)。分类讨论然后计数即可。
code
#include<cstdio>
#include<algorithm>
#define ll long long
#define N 1000005
int n,m;
int hd[N],_hd;
struct edge{
int v,nxt;
}e[N<<1];
inline void addedge(int u,int v){
e[++_hd]=(edge){v,hd[u]};
hd[u]=_hd;
}
bool vis[N];
inline void dfs(int u){
vis[u]=1;
for(int i=hd[u];i;i=e[i].nxt)
if(!vis[e[i].v])
dfs(e[i].v);
}
int deg[N],cnt;
inline ll C2(int x){
return 1ll*x*(x-1)/2;
}
ll ans;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
vis[i]=1;
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
if(u==v)
cnt++;
else{
deg[u]++;
deg[v]++;
}
addedge(u,v);
addedge(v,u);
vis[u]=vis[v]=0;
}
for(int i=1;i<=n;i++)
if(!vis[i]){
dfs(i);
break;
}
for(int i=1;i<=n;i++)
if(!vis[i]){
puts("0");
return 0;
}
ans=C2(cnt)+1ll*cnt*(m-cnt);
for(int i=1;i<=n;i++)
ans+=C2(deg[i]);
printf("%lld
",ans);
}
BZOJ 3706
简要题意
给定 (n) 个点，(m) 条边的无向图，边有黑白两种颜色。你每次操作可以选择一条回路将其反色。求出将所有边变成白色的最小操作次数或判断无解。会进行若干次对一条边反色，每次反色后求出答案。
题解
要满足条件当且仅当所有黑边经过奇数次，所有白边经过偶数次。于是可以将图的每一条白边变成两条重边，有解当且仅当新图可以圈分解。最小操作数为包含黑边的连通块数量。
code
#include<cstdio>
#include<algorithm>
#define N 1000005
int n,m,q;
struct Edge{
int u,v,col;
}E[N];
int deg[N];
int f[N];
inline int fnd(int x){
return f[x]?f[x]=fnd(f[x]):x;
}
int cnt,sz[N];
int ans;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u,v,col;
scanf("%d%d%d",&u,&v,&col);
E[i]=(Edge){u,v,col};
int fu=fnd(u),fv=fnd(v);
if(fu!=fv)
f[fu]=fv;
if(col){
deg[u]^=1;
deg[v]^=1;
}
}
for(int i=1;i<=n;i++)
cnt+=deg[i];
for(int i=1;i<=m;i++)
sz[fnd(E[i].u)]+=E[i].col;
for(int i=1;i<=n;i++)
if(!f[i]&&sz[i])
ans++;
scanf("%d",&q);
while(q--){
int opt;
scanf("%d",&opt);
if(opt==1){
int i;
scanf("%d",&i);
i++;
int u=E[i].u,v=E[i].v,col=E[i].col;
E[i].col^=1;
int fu=fnd(u);
ans-=sz[fu]>0;
sz[fu]+=E[i].col-col;
ans+=sz[fu]>0;
cnt-=deg[u]+deg[v];
deg[u]^=1,deg[v]^=1;
cnt+=deg[u]+deg[v];
}
else{
if(cnt)
puts("-1");
else
printf("%d
",ans);
}
}
}
CF 209 C
简要题意
给定 (n) 个点，(m) 条边的无向图。求最少添加多少条无向边后，图中存在从号点 1 出发的欧拉回路。
题解
转化为将图中每条边经过一次的最少路径数，对每个连通块分别考虑即可。注意特判 1 号点为孤立点的情况。
code
#include<cstdio>
#include<algorithm>
#define N 1000005
int n,m;
int hd[N],_hd;
struct edge{
int v,nxt;
}e[N<<1];
inline void addedge(int u,int v){
e[++_hd]=(edge){v,hd[u]};
hd[u]=_hd;
}
int deg[N],cnt;
bool vis[N];
inline void dfs(int u){
vis[u]=1;
cnt+=deg[u]&1;
for(int i=hd[u];i;i=e[i].nxt)
if(!vis[e[i].v])
dfs(e[i].v);
}
int co,ce;
int ans;
int main(){
scanf("%d%d",&n,&m);
if(!m){
puts("0");
return 0;
}
for(int i=1;i<=n;i++)
vis[i]=1;
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
deg[u]++;
deg[v]++;
addedge(u,v);
addedge(v,u);
vis[u]=vis[v]=0;
}
for(int i=1;i<=n;i++)
if(!vis[i]){
cnt=0;
dfs(i);
if(!cnt){
ans++;
ce++;
}
else{
ans+=cnt/2;
co++;
}
}
if(ce==1&&co==0&°[1])
ans=0;
if(!deg[1])
ans++;
printf("%d
",ans);
}
POJ 1780
简要题意
给定 (n)，求出一个字典序最小的长度为 (10^n+n-1) 的 (10) 进制串，满足所有 (10^n) 个长为 (n) 的子串恰为所有 (10^n) 个 (n) 位 (10) 进制串。
题解
仿照 0/1 串的 De Bruijin 序列的解法，建出 (n) 位 (10) 进制串对应的图，找到字典序最小的欧拉路径即可。
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#define pii std::pair<int,int>
#define mp std::make_pair
#define fir first
#define sec second
#define M 1000005
int n,m;
int vis[M][10];
std::stack<pii> st;
std::vector<int> ans;
int main(){
while(1){
scanf("%d",&n);
if(!n)
break;
m=1;
for(int i=1;i<=n;i++)
m*=10;
ans.clear();
memset(vis,0,sizeof(vis));
vis[0][0]=1;
st.push(mp(0,0));
while(st.size()){
int u=st.top().fir,c=st.top().sec;
int flg=0;
for(int i=0;i<10;i++)
if(!vis[u][i]){
vis[u][i]=1;
st.push(mp((u+i*m/10)/10,i));
flg=1;
break;
}
if(!flg){
ans.push_back(c);
st.pop();
}
}
std::reverse(ans.begin(),ans.end());
for(int i=1;i<n;i++)
putchar('0');
for(int i=0;i<ans.size();i++)
putchar('0'+ans[i]);
puts("");
}
}
Luogu 3511
简要题意
给定 (n) 个点，(m) 条边的图，每条边正着走和反着走有不同的边权。求一条最大边权最小的从 (1) 号点出发的欧拉回路。
题解
二分答案后转化为混合图欧拉回路问题。
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define inf 0x3f3f3f3f
#define N 1005
#define M 2005
namespace MF{
int n,s,t;
int hd[N],_hd;
struct edge{
int v,f,nxt;
}e[(M+N)<<1];
inline void addedge(int u,int v,int f){
e[++_hd]=(edge){v,f,hd[u]};
hd[u]=_hd;
e[++_hd]=(edge){u,0,hd[v]};
hd[v]=_hd;
}
inline void init(int n_,int s_,int t_){
for(int i=1;i<=n;i++)
hd[i]=0;
_hd=1;
n=n_,s=s_,t=t_;
}
std::queue<int> q;
int cur[N],dis[N];
inline bool bfs(){
for(int i=1;i<=n;i++)
cur[i]=hd[i];
for(int i=1;i<=n;i++)
dis[i]=inf;
dis[s]=0;
q.push(s);
while(q.size()){
int u=q.front();
q.pop();
for(int i=hd[u];i;i=e[i].nxt){
int v=e[i].v,f=e[i].f;
if(f&&dis[v]>dis[u]+1){
dis[v]=dis[u]+1;
q.push(v);
}
}
}
return dis[t]<inf;
}
inline int dfs(int u,int lmt){
if(u==t||!lmt)
return lmt;
int res=0;
for(int i=cur[u];i;i=e[i].nxt){
cur[u]=i;
int v=e[i].v,f=e[i].f;
if(dis[v]!=dis[u]+1)
continue;
f=dfs(v,std::min(lmt,f));
e[i].f-=f,e[i^1].f+=f;
lmt-=f,res+=f;
if(!lmt)
break;
}
return res;
}
inline int sol(){
int res=0;
while(bfs())
res+=dfs(s,inf);
return res;
}
}
int n,m;
struct Edge{
int u,v,a,b;
}E[M];
int cnt;
namespace DSU{
int f[N],sz[N];
inline int fnd(int x){
return f[x]?f[x]=fnd(f[x]):x;
}
inline void mrg(int u,int v){
int fu=fnd(u),fv=fnd(v);
if(fu==fv)
return;
if(sz[fu]<sz[fv]){
f[fu]=fv;
sz[fv]+=sz[fu];
}
else{
f[fv]=fu;
sz[fu]+=sz[fv];
}
}
inline void init(){
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++)
sz[i]=1;
}
}
int hd[N],_hd;
struct edge{
int v,nxt;
}e[M];
inline void addedge(int u,int v){
e[++_hd]=(edge){v,hd[u]};
hd[u]=_hd;
}
bool vis[M];
std::vector<int> p;
inline void dfs(int u,int c){
for(int i=hd[u];i;i=e[i].nxt)
if(!vis[i]){
vis[i]=1;
dfs(e[i].v,i);
}
if(c)
p.push_back(c);
}
int deg[N],id[M];
inline bool chk(int x,int tp){
memset(deg,0,sizeof(deg));
MF::init(n+2,n+1,n+2);
for(int i=1;i<=m;i++){
int u=E[i].u,v=E[i].v,a=E[i].a,b=E[i].b;
if(a<=x&&b<=x){
deg[u]--,deg[v]++;
MF::addedge(v,u,1);
if(tp)
id[i]=MF::_hd;
}
else if(a<=x)
deg[u]--,deg[v]++;
else if(b<=x)
deg[u]++,deg[v]--;
else
return 0;
}
int sum=0;
for(int i=1;i<=n;i++){
if(deg[i]&1)
return 0;
if(deg[i]>0){
MF::addedge(MF::s,i,deg[i]/2);
sum+=deg[i]/2;
}
else
MF::addedge(i,MF::t,-deg[i]/2);
}
if(MF::sol()!=sum)
return 0;
if(!tp)
return 1;
for(int i=1;i<=m;i++){
int u=E[i].u,v=E[i].v,a=E[i].a,b=E[i].b;
if(a<=x&&b<=x){
if(MF::e[id[i]].f)
addedge(v,u);
else
addedge(u,v);
}
else if(a<=x)
addedge(u,v);
else if(b<=x)
addedge(v,u);
}
dfs(1,0);
std::reverse(p.begin(),p.end());
for(auto i:p)
printf("%d ",i);
puts("");
return 1;
}
int main(){
scanf("%d%d",&n,&m);
DSU::init();
for(int i=1;i<=m;i++){
scanf("%d%d%d%d",&E[i].u,&E[i].v,&E[i].a,&E[i].b);
DSU::mrg(E[i].u,E[i].v);
}
for(int i=2;i<=n;i++)
if(!DSU::f[i]&&DSU::sz[i]==1)
cnt++;
if(DSU::sz[DSU::fnd(1)]!=n-cnt){
puts("NIE");
return 0;
}
int l=1,r=1000,ans=-1;
while(l<=r){
int mid=(l+r)>>1;
if(chk(mid,0)){
ans=mid;
r=mid-1;
}
else
l=mid+1;
}
if(ans==-1)
puts("NIE");
else{
printf("%d
",ans);
chk(ans,1);
}
}