欧拉回路和欧拉路径
概述
若图 G 中存在这样一条路径,使得它恰好通过 G 中每条边一次,则称该路径为 欧拉路径。若该路径是一个环路,则称为 欧拉(Euler)回路。
具有欧拉回路的图称称为 欧拉图。
具有欧拉路径但不具有欧拉回路的图称为 半欧拉图。
有关欧拉路的重要性质
无向图
- 一个无向图 G 存在欧拉路径当且仅当无向图 G 是连通图,且该图中有两个奇度顶点(度数为奇数)或者无奇度顶点。
- 当无向图 G 是包含两个奇度顶点的连通图时,G 的欧拉路径必定以这两个奇度顶点为端点。
- 一个无向图 G 存在欧拉回路当且仅当无向图 G 连通且不存在奇度顶点。
有向图
- 一个有向图 G 存在欧拉路径当且仅当 G 是弱连通的有向图(将有向边全部看成无向边后该图是连通图),且满足以下两个条件之一:
- 所有顶点的入度和出度相等;
- 有一个顶点的出度与入度之差为 1,一个顶点的出度与入度之差为 -1,其余顶点的入度和出度相等。
- 当有向图 G 包含两个入度和出度不相同的顶点且有欧拉路径时,欧拉路径必定以这两个入度出度不相同的顶点为端点。
- 一个有向图 G 存在欧拉回路当且仅当图 G 是连通的有向图,且所有顶点的入度和出度相等。
性质 | 图 |
---|---|
没有奇度顶点的无向连通图 | 欧拉图 |
有且仅有两个奇度顶点的无向连通图 | 半欧拉图 |
所有顶点入度和出度相等的有向弱连通图 | 欧拉图 |
有且仅有两个顶点入度与出度不等且一个入度与出度差为 1 另一个为 -1 的有向弱连通图 | 半欧拉图 |
判断无向图的欧拉回路和欧拉路径
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100;
const int M = 10000;
struct edge {
int v, next;
edge() {}
edge(int _v, int _next):v(_v), next(_next) {}
} E[N];
int p[N], eid;
void init() {
memset(p, -1, sizeof p);
eid = 0;
}
void insert(int u, int v) {
E[eid] = edge(v, p[u]);
p[u] = eid++;
}
void insert2(int u, int v) {
insert(u, v);
insert(v, u);
}
int cnt;
bool vis[N];
int n, m;
int degree[N];
void dfs(int u) {
vis[u] = true;
cnt++;
for (int e = p[u]; e != -1; e = E[e].next) {
int v = E[e].v;
if (!vis[v]) {
dfs(v);
}
}
}
void eulor() {
memset(vis, false, sizeof vis);
dfs(1); // dfs判断该图是否连通
if (cnt != n) {
cout << "It doesn't have an eulor path" << endl;
return;
}
int cnt_odd = 0;
for (int i = 1; i <= n; i++) { //统计奇度顶点的个数
if (degree[i] % 2 == 1) {
cnt_odd++;
}
}
//根据奇度顶点来判断
if (cnt_odd == 0) {
cout << "It has an eulor circuit!" << endl;
} else if (cnt_odd == 2) {
cout << "It has an eulor path!" << endl;
} else {
cout << "It doesn't have an euler path!" << endl;
}
}
int main() {
init();
memset(degree, 0, sizeof degree);
cin >> n >> m;
int u, v;
for (int i = 0; i < m; i++) {
cin >> u >> v;
insert2(u, v);
degree[u]++;
degree[v]++;
}
eulor();
return 0;
}
判断有向图的欧拉回路和欧拉路径
我们让
euler
函数返回一个int
类型的值表示如果存在欧拉回路或欧拉路径,起始点是哪一个,如果不存在,我们让它返回值为 0,如果是欧拉回路,我们就取点 1 作为起始点,如果是欧拉路径,我们应该取入度与出度差为 -1 的点为起始点。为了判断方便,我们可以声明两个变量
first
和last
来记录入度与出度差为 -1 的点和 1 的点是哪个点,如果不存在这样的点,值为 0。现在我们来声明
euler
函数,声明变量first
和last
,并写下循环框架,我们将会遍历每个点的入度和出度差进行判断,如果遇到一个点的入度和出度之差小于 -1 或者大于 1 了,那么该图肯定没有欧拉路径,我们进行输出并返回 0。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100;
const int M = 10000;
struct edge {
int v, next;
edge() {}
edge(int _v, int _next): v(_v), next(_next) {}
} E[N];
int p[N], eid;
void init() {
memset(p, -1, sizeof p);
eid = 0;
}
void insert(int u, int v) {
E[eid] = edge(v, p[u]);
p[u] = eid++;
}
int degree[N];
int n, m;
int euler() {
int first = 0, last = 0;
for (int i = 1; i <= n; i++) {
if (degree[i] < -1 || degree[i] > 1) {
cout << "It doesn't have an euler path!" << endl;
return 0;
} else if (degree[i] == -1) {
if (first != 0) {
cout << "It doesn't have an euler path!" << endl;
return 0;
} else {
first = i;
}
} else if (degree[i] == 1) {
if (last != 0) {
cout << "It doesn't have an euler path!" << endl;
return 0;
} else {
last = i;
}
}
}
if (first == 0 && last == 0) {
cout << "It has an euler circuit!" << endl;
return 1;
} else if (first != 0 && last != 0) {
cout << "It has an euler path" << endl;
return first;
} // 剩下的情况不可能存在,因为有向图中入度和出度的总和一定是一样的
}
int main() {
init();
cin >> n >> m;
int u, v;
for (int i = 0; i < m; i++) {
cin >> u >> v;
insert(u, v);
degree[u]--;
degree[v]++;
}
euler();
return 0;
}
无向图欧拉路径
计算无向图的欧拉路经可以用“套圈法”、基于深度优先搜索来实现。
从一个合适的顶点出发进行深度优先搜索。当搜到一个顶点 u 时:
- 如果此时没有顶点与该顶点相连,那么就将 u 加入路径中并回溯;
- 如果有顶点 v 与顶点 u 相连,那么就删除无向边 <u, v>,并继续搜索顶点 v 。将所有和 u 相邻的顶点遍历完之后,将 u 加入路径中。
const int MAX_N = 100;
int mat[MAX_N][MAX_N];
int match[MAX_N]; // 表示顶点剩余的度
int n; // 顶点个数
void solve(int u) {
if (match[u] > 0) {
for (int i = 0; i < n; ++i) {
if (mat[u][i]) {
mat[u][i]--;
mat[i][u]--;
solve(i);
}
}
}
// 将u加入路径中
}
有向图欧拉路经
计算有向图的欧拉路经同样可以用“套圈法”。和无向图唯一不同的是,在记录方案的时候将顶点编号插入栈中,并在最后将栈中的元素依次输出。也就是说,将之前输出的顺序逆置。
const int MAX_N = 100;
const int MAX_M = 10000;
int mat[MAX_N][MAX_N];
int match[MAX_N]; // 表示顶点剩余的度
int n; // 顶点个数
int stk[MAX_M], top = 0; // 用数组 stk 来模拟一个栈
void solve(int u) {
if (match[u] > 0) {
for (int i = 0; i < n; ++i) {
if (mat[u][i]) {
mat[u][i]--;
solve(i);
}
}
}
stk[top++] = u; // 将顶点 u 插入栈中
}
如果存在欧拉回路,“套圈法” 可以从任意点开始搜索。如果是欧拉路径,需要找到一个起点,然后再套用 “套圈法”。
而访问一个点以后我们为什么不先输出,而是等这个点搜索完成以后再输出呢。可以看下面这个反例。如果从 11 开始搜索,先搜索 1,2,3,61,2,3,6,那么可能最后输出的路径为 1,2,3,6,1,4,5,3,而这个路径是错误的,而后输出的路径为 1,6,3,5,4,3,2,1,才是正确的欧拉回路。
例题:De Bruijin 序列
De Bruijin 序列是指这样一个序列:对于一个包含 n 个元素的字符集,生成一个仅包含 n 种字符的字符串,使得这个字符串中 $k^n$ 种长度为 k 的子串均恰好出现一次。
例如,对于 n=2,k=2,S={0,1} 的 De Bruijin 序列,有如下满足要求的一个字符串:
00110
00
01
11
10
解析:
我们可以把这个问题转化为图论问题:图中的顶点代表每种长度为 k-1 的子串,每条边代表一个子串增加一个字符后的转移,如下图所示:
对于 n=2, k=2, S={0,1} 的情况,0
增加一个字符0
后,变成00
,最后 k-1 位是0
,所以从0
连向0
一条边00
;0
增加一个字符1
后,变成01
,最后 k-1 位是1
;以此类推。
我们用 n=2,k=3,S={0,1} 来进一步理解这个建模:
图中的每条边都对应着一个长度为 k 的子串,而每走一条边,就意味着在整个字符串的最后增加一个字符。这样,图中的一个欧拉路径就对应着一个满足要求的完整字符串。例如上图中,一个欧拉路径01 11 11 10 01 10 00 00 01
就对应着字符串0111010001
,其中恰好包含 $2^3=8$ 种不同的子串,且每种子串刚好出现一次
有向图求欧拉路径代码
#include <iostream>
#include <cstring>
#include <stack>
using namespace std;
// 求有向图的欧拉路径
const int N = 100;
const int M = 10000;
struct edge {
int v, next;
edge() {}
edge(int _v, int _next): v(_v), next(_next) {}
} E[M];
int p[N], eid;
void init() {
memset(p, -1, sizeof p);
eid = 0;
}
void insert(int u, int v) {
E[eid] = edge(v, p[u]);
p[u] = eid++;
}
int n, m;
int degree[N];
int euler() {
int first = 0, last = 0;
for (int i = 1; i <= n; i++) {
if (degree[i] > 1 || degree[i] < -1) {
return 0;
} else if (degree[i] == -1) {
if (first != 0) {
return 0;
} else {
first = i;
}
} else if (degree[i] == 1) {
if (last != 0) {
return 0;
} else {
last = i;
}
}
}
if (first == 0 && last == 0) {
return 1;
} else if (first != 0 && last != 0) {
return first;
} else {
return 0;
}
}
stack<int> path;
void dfs(int u) {
while(p[u] != -1) {
int v = E[p[u]].v; // 拿到和u相邻的点v
p[u] = E[p[u]].next; // 删除边<u, v>
dfs(v);
}
path.push(u);
}
bool euler_find() {
int start = euler();
if (start == 0) {
return false;
} else {
dfs(start);
return path.size() == m + 1;
}
}
int main() {
cin >> n >> m;
int u, v;
for (int i = 0; i < m; i++) {
cin >> u >> v;
insert(u, v);
degree[u]--;
degree[v]++;
}
if (!euler_find()) {
cout << "It doesn't have an euler path!" << endl;
} else {
while (!path.empty()) {
cout << path.top() << endl;
path.pop();
}
}
return 0;
}