欧拉图
本页面将简要介绍欧拉图的概念、实现和应用。
定义
本文中仅讨论有限图。
在图论中,欧拉路径(Eulerian path)是经过图中每条边恰好一次的路径,欧拉回路(Eulerian circuit)是经过图中每条边恰好一次的回路。 如果一个图中存在欧拉回路,则这个图被称为欧拉图(Eulerian graph);如果一个图中不存在欧拉回路但是存在欧拉路径,则这个图被称为半欧拉图(semi-Eulerian graph)。
Warning
此处定义中虽然使用「路径」一词,但严格说来此处使用的概念应该是「迹(trail)」。欧拉路径与欧拉回路仅能使用每条边恰好一次,但并没有对经过顶点的情况进行限制。
性质
以下我们假设所讨论的图
对于连通图
是欧拉图; 中所有顶点的度数都是偶数(对于有向图,每个顶点的入度等于出度); 可被分解为若干条不共边回路的并。
以下我们对等价性进行证明。
若一个图
若一个图
若一个连通图
以上的性质同时也构成了欧拉图的判断条件。具体地说,一个图是欧拉图当且仅当非零度顶点互相(强)连通,且顶点的度数都是偶数(或入度与出度相等)。
对于半欧拉图,其性质与欧拉图相似:一个半欧拉图具有恰好两个奇度数的顶点,且这两个顶点就是欧拉路径的两个端点。通过将这两个点连接起来,可以将半欧拉图转化为欧拉图。通过删除欧拉图中的任意一条边,可以得到一个半欧拉图。 由此可以导出半欧拉图的判别法:一个图是半欧拉图当且仅当非零度顶点互相(强)连通,且奇度数顶点恰好有两个。对于有向图,第二个条件为恰存在两个顶点
欧拉回路/欧拉路径的构造
此处我们介绍最常用的 Hierholzer 算法,该算法的核心思想为利用上述欧拉图性质中的第三点,即欧拉图可以被拆解为若干条不共边回路的并。 可以注意到,在上述证明中其实已经提到了完整可行的将不共边回路合并为欧拉回路的操作,且在使用合适的数据结构储存时(如使用类链表的结构储存环)实现并不困难。
算法的具体流程为先从图中找到一条回路作为当前回路,每次从当前回路中选取剩余度数不为零的点,从该点出发找到一条新的简单回路,并将该简单回路与当前回路合并,重复该过程直到当前回路中的所有点均无剩余度数,此时的当前回路即为欧拉回路。
该算法同样适用于有向图。对于半欧拉图,可以从图中找到一条连接两个奇度数点的路径作为当前路径,每次选取度数非零的点寻找简单回路并将其与当前路径合并,最后得到欧拉路径。
实现
Hierholzer 算法的伪代码如下:
时间复杂度分析
Hierholzer 算法的时间复杂度为
注意到在前述正确性分析中,在欧拉图或半欧拉图上寻找简单回路(或半欧拉图的初始路径)的过程是 无需回溯 的,只要沿着剩下的边一直走就必定可以发现所求的回路或路径,且 每条边仅会被访问一次。 为了利用这一性质,在实现上应采取类链表的方式储存图中的边,如邻接表或链式前向星,以便每条边在被访问过后即刻删除之。如果采用朴素的邻接矩阵进行储存,则每次寻边耗时
Note
事实上,该算法的准确复杂度应为
如果需要输出字典序最小的欧拉路或欧拉回路,则需要将边排序,时间复杂度为
应用
有向欧拉图可用于计算机译码。
设有
构造如下有向欧拉图:
设
规定
顶点
边
这样的
任求
例题
洛谷 P2731 骑马修栅栏
给定一张有 500 个顶点的无向图,求这张图的一条欧拉路或欧拉回路。如果有多组解,输出最小的那一组。
在本题中,欧拉路或欧拉回路不需要经过所有顶点。
边的数量 m 满足
解题思路
本题为 Hierholzer 算法的直接应用。
保存答案可以使用 std::stack<int>
,因为如果找的不是回路的话必须将那一部分放在最后。
注意,不能使用邻接矩阵存图,否则时间复杂度会退化为 std::vector
存图。示例代码使用 std::vector
。
示例代码
#include <algorithm>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
struct edge {
int to;
bool exists;
int revref;
bool operator<(const edge& b) const { return to < b.to; }
};
vector<edge> beg[505];
int cnt[505];
constexpr int dn = 500;
stack<int> ans;
void Hierholzer(int x) { // 关键函数
for (int& i = cnt[x]; i < (int)beg[x].size();) {
if (beg[x][i].exists) {
edge e = beg[x][i];
beg[x][i].exists = beg[e.to][e.revref].exists = false;
++i;
Hierholzer(e.to);
} else {
++i;
}
}
ans.push(x);
}
int deg[505];
int reftop[505];
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
for (int i = 1; i <= dn; ++i) {
beg[i].reserve(1050); // vector 用 reserve 避免动态分配空间,加快速度
}
int m;
cin >> m;
for (int i = 1; i <= m; ++i) {
int a, b;
cin >> a >> b;
beg[a].push_back(edge{b, true, 0});
beg[b].push_back(edge{a, true, 0});
++deg[a];
++deg[b];
}
for (int i = 1; i <= dn; ++i) {
if (!beg[i].empty()) {
sort(beg[i].begin(), beg[i].end()); // 为了要按字典序贪心,必须排序
}
}
for (int i = 1; i <= dn; ++i) {
for (int j = 0; j < (int)beg[i].size(); ++j) {
beg[i][j].revref = reftop[beg[i][j].to]++;
}
}
int bv = 0;
for (int i = 1; i <= dn; ++i) {
if (!deg[bv] && deg[i]) {
bv = i;
} else if (!(deg[bv] & 1) && (deg[i] & 1)) {
bv = i;
}
}
Hierholzer(bv);
while (!ans.empty()) {
cout << ans.top() << '\n';
ans.pop();
}
}
习题
创建日期: 2018年7月11日