五味子

小舟从此逝,江海寄余生

0%

欧拉回路

参考自https://blog.csdn.net/qq_41730082/article/details/84927199

参考自《算法竞赛入门经典》

前置定义

欧拉通路: 通过图中每条边且只通过一次,并且经过每一顶点的通路

欧拉回路: 通过图中每条边且只通过一次,并且经过每一顶点的回路

有向图的基图:忽略有向图所有边的方向,得到的无向图称为该有向图的基图。

前置简单证明

不难发现,在欧拉道路中,“进”和“出”是对应的——除起点和终点外,其它点的“进出”此书应该相等。换句话说,除了起点和终点外,其它点的度数应该是偶数

无向图情况

欧拉通路:设G是连通无向图,则称经过G的每条边一次并且仅经过一次的路径为欧拉通路;

欧拉回路:如果欧拉通路是回路(起点和终点是同一个顶点),则称此回路是欧拉回路

欧拉图:具有欧拉回路的无向图G成为欧拉图

有向图情况

欧拉通路:设D是有向图,D的基图连通,则称经过D的每条边一次并且仅有一次的有向路径为有向欧拉通路

欧拉回路:如果有向欧拉通路是有向回路,则称此有向回路为 有向欧拉回路

欧拉图:具有有向欧拉回路的图D称为有向欧拉图

无向图中定理

无向图G存在欧拉通路的充要条件是:G为连通图,并且G仅有两个奇度结点(度数为奇数的顶点)或者无奇度结点。

推论

(1) 当G是仅有两个奇度结点的连通图时,G的欧拉通路必以此两个结点为端点;

(2)当G是无奇度结点的连通图时,G必有欧拉回路

(3)G为欧拉图(存在欧拉回路)的充分必要条件是 G为无奇度结点的连通图

有向图中定理

有向图D存在欧拉通路的充要条件是:D为有向图,D的基图连通,并且所有顶点的出度与入度相等;或者 除两个顶点外,其余顶点的出度与入度都相等,而这两个顶点中一个顶点的出度与入度之差为1,另一个顶点的出度与入度之差为-1.

推论

(1)当D除出、入度之差为1,-1的两个顶点之外,其余顶点的出度与入度相等时,D的有向欧拉通路必以出、入度之差为1的顶点作为始点,以出、入度之差为-1的顶点作为终点。

(2)当D的所有顶点的出、入度都相等时,D中存在有向欧拉回路。

(3)有向图D为有向欧拉图的充要条件是 D的基图为连通图,并且所有顶点的出、入度都相等。

求解

dps解法

用欧拉定理判断出一个正确的起点,以此开始遍历,记录下遍历的顺序

1
2
3
4
5
6
7
8
9
10
11
12
//代码是逆序输出
//同时适用欧拉回路和欧拉通路,但欧拉通路时必须传入正确起点
void euler(int u)
{
for(int v = 0; v < n; ++v)
if(G[u][v] && !vis[u][v])
{
vis[u][v] = vis[v][u] = 1;
euler(v);
printf("%d %d\n", u, v);
}
}

Fleury算法

  1. 任取G中一顶点v0,令P0=v0;

  2. 假设沿Pi=v0e1v1e2v2……eivi走到顶点vi,按下面方法从E(G)-{e1,e2,…,ei}中选ei+1

    ei+1与vi相关联

    除非无别的边可供选择,否则ei+1不应该是Gi=G-{e1,e2,…,ei}中的桥。当2不能再进行时算法停止。

  3. 可以证明的是,当算法停止时,所得到的简单回路Pm=v0e1v1e2v2……emvm,(vm=v0)为G中一条欧拉回路。

代码待更

相关题目

洛谷P1341(并查集+欧拉回路)

板子题,由于copy了题解再慢慢理解慢慢改的,代码规范并不好,有空再改(咕咕咕)

  • 很明显看出是用图来做
  • n条边,n+1个点解决问题,典型的一笔画问题
  • 先判断是否联通
  • 再判断是否有解
  • 再确定顶点开始搜索
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
//欧拉回路问题
//并查集
#include<cstdio>

int n;
int par[130];
int deg[130];
int G[130][130];
char ans[1500];
char a[3];
int head = 0;

int find(int x)
{
if(x == par[x])
return x;
else
return par[x] = find(par[x]);
}

void euler(int u)
{
for(int v = 64; v <= 125; ++v)
if(G[u][v])
{
G[u][v] = G[v][u] = 0;
euler(v);
}
ans[n--] = u;
}

int main()
{
scanf("%d", &n);
for(int i = 64; i <= 125; i++)
par[i] = i;
for(int i = 1; i <= n; i++)
{
scanf("%s", a);
G[a[0]][a[1]] = G[a[1]][a[0]] = 1;
deg[a[0]]++;
deg[a[1]]++;
int x = find(a[0]);
int y = find(a[1]);
par[x] = y; //并查集连起来
}

int cnt = 0;
for(int i = 64; i <= 125; i++) //若不连通
if(par[i] == i && deg[i])
cnt++;
if(cnt > 1)
{
printf("No Solution\n");
return 0;
}

cnt = 0;
head = 0;

for(int i = 64; i <= 125; i++) //奇数度结点个数
{
if(deg[i] & 1)
{
cnt++;
if(!head) head = i;
}
}

if(cnt && cnt != 2)
{
printf("No Solution\n");
return 0;
}

if(!head)//如果是欧拉回路
for(int i = 64; i <= 125; i++)
if(deg[i])
{
head = i;
break;
}
euler(head);
printf("%s\n", ans);
return 0;
}