1633 字
8 分钟
欧拉路径,欧拉回路,欧拉图

欧拉路径,欧拉回路,欧拉图#

对于一个图,如果存在一条路径恰好经过所有边一次,则称这条路径为一条欧拉路径。

如果存在一条回路经过所有边恰好一次,则称这条路径为一条欧拉回路。

存在欧拉回路的图被称为欧拉图。

环分解#

如果一个图的边集可以被分成若干个简单环,则称这个图可以环分解。

判定#

判定定理 1: 一个图存在欧拉回路当且仅当这个图可以被环分解。

  • 充分性: 如果可以环分解,那么每次选取两个相交的环合并成一个大环即可。
  • 必要性: 对于一条欧拉回路,每次遇到重复点就把这段路径连成的环分解出去,这样一定能形成若干个简单环。

判定定理 2: 一个图可以被环分解当且仅当所有点度数都为偶数。

  • 充分性: 每次选取一个简单环,删掉之后所有点度数依旧是偶数,归纳即可。
  • 必要性: 每个点进入次数和出去次数相等,因此都是偶数。

结合上面两条我们可以得出欧拉回路的判定定理:

判定定理 3: 一个图存在欧拉回路当且仅当所有点度数都是偶数。

并且我们可以知道,一个图存在欧拉回路、可以被环分解、所有点度数都是偶数,这是三个完全等价的条件。

对于有向图,类似的可以得出充要条件是所有节点入度等于出度。

还有下面的推论:

推论: 一个图存在欧拉路径当且仅当恰好有两个结点的度数是奇数。


有向图的判定#

对于有向图,我们需要考虑每个节点的入度 (in-degree) 和 出度 (out-degree)。判定前提同样需要图是连通的(忽略度数为 0 的孤立点后,基图连通)。

1. 有向图欧拉回路#

判定定理 4: 一个有向图存在欧拉回路,当且仅当:

  • 每个节点的入度等于出度,即对于所有节点 vv,都有 in(v)=out(v)in(v) = out(v)。

2. 有向图欧拉路径#

判定定理 5: 一个有向图存在欧拉路径,当且仅当满足以下两种情况之一:

  1. 符合欧拉回路的条件(起点和终点重合)。
  2. 恰好有两个节点的入度不等于出度:
    • 其中一个节点满足 out(v)=in(v)+1out(v) = in(v) + 1(此为起点)。
    • 另一个节点满足 in(v)=out(v)+1in(v) = out(v) + 1(此为终点)。
    • 其余所有节点的入度等于出度。

Hierholzer (HE) 算法#

Hierholzer 算法是寻找欧拉回路或欧拉路径的一种高效算法,其核心思想是“贪心搜索 + 回溯记录”。

1. 算法流程#

  1. 确定起点:
    • 如果找欧拉回路,可以从任意度数不为 0 的点出发。
    • 如果找欧拉路径,必须从满足条件的“起点”(无向图中的奇度数点,或有向图中出度比入度多 1 的点)出发。
  2. DFS 遍历:
    • 从当前节点出发,不断沿着未访问过的边向下搜索。
    • 当前弧优化: 为了保证效率,每次访问一条边后,立刻将其从该点的边表中“逻辑删除”(通常用指针或索引移动),确保每条边只被扫描一次。
  3. 回溯入栈:
    • 当某个节点的所有关联边都已经访问完毕(无法再继续走下去)时,将该节点压入结果栈(或数组)。
  4. 结果输出:
    • 遍历结束后,将栈内的节点序列逆序输出,即得到一条完整的欧拉路径/回路。

3. 复杂度分析#

  • 时间复杂度: O(V+E)O(V + E),因为每条边只被访问并删除一次。

比较#

类型 欧拉回路条件 欧拉路径条件
无向图 所有点度数为偶数 恰有 0 或 2 个奇度数点
有向图 所有点 in=outin = out 所有点 in=outin = out;或只有起点 out=in+1out=in+1 且终点 in=out+1in=out+1

CSES De Bruijn Sequence

De Bruijn 序列#

1. 定义#

De Bruijn 序列 B(k,n)B(k, n) 是一个在一个大小为 kk 的字符集上、包含所有长度为 nn 的子串各一次的循环序列。

  • 长度:knk^n(在圆环意义下)。
  • 性质:任何长度为 nn 的组合都在该序列中作为一个连续子串出现,且只出现一次。

示例 (k=2,n=3k=2, n=3): 循环序列 00010111 包含了 000, 001, 010, 101, 011, 111, 110, 100 全部 8 种情况。

2. 构造原理:De Bruijn 图与欧拉回路#

构造 De Bruijn 序列的核心在于将其转化为一个图论问题。

构图规则#

  • 节点 (Nodes):代表所有长度为 n−1n-1 的字符串。
    • 节点总数:kn−1k^{n-1}。
    • 编号范围:00 到 kn−1−1k^{n-1} - 1。
  • 边 (Edges):代表一个“转移”操作,即添加一个新字符。
    • 一条边对应一个长度为 nn 的字符串。
    • 边总数:knk^n。

转移逻辑 (滑动窗口)#

从节点 uu(代表前缀)转移到节点 vv,意味着:

  1. 扔掉 uu 的最高位。
  2. 在末尾 添加 一个新字符 valval。
  3. 形成新节点 vv。

数学公式(二进制 k=2k=2): v=((u≪1) ∣ val) & maskv = ((u \ll 1) \ | \ val) \ \& \ \text{mask} 其中 mask 用于保留低 n−1n-1 位,mask = (1 << (n-1)) - 1。

为什么是欧拉回路?#

  • 每个节点代表 n−1n-1 位状态。
  • 每个节点都有 kk 个出边(加 0 或 加 1…)和 kk 个入边。
  • 图是连通的且 入度 = 出度。
  • 因此,该图一定存在欧拉回路。
  • 欧拉回路经过所有边恰好一次 →\rightarrow 生成所有长度为 nn 的子串恰好一次。
#include <bits/stdc++.h>
#define N 100005
#define inf 0x3f3f3f3f3f3f3f3f
#define ll long long
#define pr pair<ll, ll>
using namespace std;
int n, m, q, ma, k, cnt;
vector<vector<tuple<int, int, int>>> map1;
const ll mod = 1e9 + 7;
int main() {
ios::sync_with_stdio(0);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n;
if (n == 1) {
cout << "10";
return 0;
}
map1.assign(1 << n, {});
for (int i = 0; i < (1 << (n - 1)); i++) {
auto x = i;
x >>= 1;
map1[i].push_back({++cnt, 0, x});
map1[i].push_back({++cnt, 1, x ^ (1 << (n - 2))});
}
vector<int> ans;
vector<bool> vis(cnt + 10, 0);
vector<int> cur(1 << n, 0);
auto dfs = [&](auto &&self, int x) -> void {
for (int &i = cur[x]; i < map1[x].size(); i++) {
auto [id, num, y] = map1[x][i];
if (!vis[id]) {
vis[id] = 1;
self(self, y);
ans.push_back(num);
}
}
};
dfs(dfs, 0);
reverse(ans.begin(), ans.end());
for (int i = 1; i < n; i++)
cout << 0;
for (auto x : ans)
cout << x;
return 0;
}

欧拉路径,欧拉回路,欧拉图
https://sanzenin.top/posts/obsidian/欧拉回路/
作者
Sanzenin 凪
发布于
2026-09-03
许可协议
CC BY-NC-SA 4.0

分享文章

生成精美分享图或复制链接,与更多人分享本文。

继续阅读

沿着主题读

基于共同的标签与分类

换条路线

从其他文章中稳定抽取