欧拉图 学习笔记

模板及讲解

定义

欧拉路:能从无向图的一个点出发走一条路径,每条边恰好经过一次,这样的路叫欧拉路
欧拉回路:能从无向图任意一个点出发走一条路径,每条边恰好经过一次,并且回到该点,这样的路叫欧拉路
欧拉图:具有欧拉回路的图称为欧拉图,具有欧拉路无欧拉回路的图称为半欧拉图

性质

至多两个奇点(度数为奇数)的无向图一定存在欧拉路

当有两个奇点时欧拉路必然从一个奇点到另一个奇点
当有没有奇点时欧拉路必然是一个欧拉回路

欧拉图中所有点都是偶点并且所有点连通

一笔画:
连通分量是一个孤立的点, 只需要0笔可以完成
连通分量是一个欧拉图或半欧拉图, 只需要1笔可以完成
否则需要奇点数目/2笔可以完成
简单证明为一个联通分量中两个奇点(非欧拉图/半欧拉图)就要有一条笔画划过,如果没有奇点(就是一个欧拉图)也要用一条笔画划过,结论得证
HDU 3018

题目

判断是否有欧拉回路/欧拉路

Hdu 1878
题意:欧拉回路是指不令笔离开纸面,可画过图中每条边仅一次,且可以回到起点的一条回路。现给定一个图,问是否存在欧拉回路?
解:欧拉图中所有点都是偶点并且所有点连通。用并查集判连通,记录度数即可。

代码:

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
int n, m, de[1005], f[1005];
int find(int x) {return x == f[x] ? x : f[x] = find(f[x]);}
void clean() {}
int solve() {
clean();
for (int i = 1; i <= n; i++) de[i] = 0, f[i] = i;
for (int x, y, i = 1; i <= m; i++) {
scanf("%d%d", &x, &y);
de[x]++, de[y]++;
int u = find(x), v = find(y);
if (u != v) f[u] = v;
}
int ans1 = 0, ans2 = 0;
for (int i = 1; i <= n; i++) find(i);
for (int i = 1; i <= n; i++) ans1 += (f[i] == i), ans2 += ((de[i] % 2) ? 0 : 1);
if (ans1 != 1) return printf("0\n"), 0;
if (ans2 != n) return printf("0\n"), 0;
return printf("1\n"), 0;
}
int main() {
while (scanf("%d%d", &n, &m) == 2 && n && m) solve();
return 0;
}

欧拉路存在条件(图连通):
有向图:有一个点入度等于出度加一,有一个点出度等于入度加一,其余所有点入度等于出度
无向图:至多有两个奇点(无向图中奇点个数为奇数)
欧拉回路存在条件(图连通):
有向图:所有点入度等于出度
无向图:没有奇点

找欧拉回路/欧拉路

poj 2230
题意:在有向图中从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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
struct edge {
int v, vis;
}ed[100000 + 5];
int n, m, en;
vector<int> G[100000 + 5];
void ins(int x, int y) {
ed[++en] = (edge){y, 0}, G[x].push_back(en);
ed[++en] = (edge){x, 0}, G[y].push_back(en);
}
void clean() {
en = 0;
for (int i = 0; i <= 100000; i++) G[i].clear();
}
void dfs(int u) {
for (int i = 0; i < (int)G[u].size(); i++) {
edge &a = ed[G[u][i]];
if (!a.vis) a.vis = 1, dfs(a.v);
}
printf("%d\n", u);
}
int solve() {
clean();
for (int x, y, i = 1; i <= m; i++) scanf("%d%d", &x, &y), ins(x, y);
dfs(1);
return 0;
}
int main() {
scanf("%d%d", &n, &m), solve();
return 0;
}

混合图欧拉回路

常见题型

1、判断是否有欧拉回路
2、找欧拉回路/欧拉路

------ 本文结束 ------