欧拉路径,欧拉回路,欧拉图
对于一个图,如果存在一条路径恰好经过所有边一次,则称这条路径为一条欧拉路径。
如果存在一条回路经过所有边恰好一次,则称这条路径为一条欧拉回路。
存在欧拉回路的图被称为欧拉图。
环分解
如果一个图的边集可以被分成若干个简单环,则称这个图可以环分解。
判定
判定定理 1: 一个图存在欧拉回路当且仅当这个图可以被环分解。
- 充分性: 如果可以环分解,那么每次选取两个相交的环合并成一个大环即可。
- 必要性: 对于一条欧拉回路,每次遇到重复点就把这段路径连成的环分解出去,这样一定能形成若干个简单环。
判定定理 2: 一个图可以被环分解当且仅当所有点度数都为偶数。
- 充分性: 每次选取一个简单环,删掉之后所有点度数依旧是偶数,归纳即可。
- 必要性: 每个点进入次数和出去次数相等,因此都是偶数。
结合上面两条我们可以得出欧拉回路的判定定理:
判定定理 3: 一个图存在欧拉回路当且仅当所有点度数都是偶数。
并且我们可以知道,一个图存在欧拉回路、可以被环分解、所有点度数都是偶数,这是三个完全等价的条件。
对于有向图,类似的可以得出充要条件是所有节点入度等于出度。
还有下面的推论:
推论: 一个图存在欧拉路径当且仅当恰好有两个结点的度数是奇数。
有向图的判定
对于有向图,我们需要考虑每个节点的入度 (in-degree) 和 出度 (out-degree)。判定前提同样需要图是连通的(忽略度数为 0 的孤立点后,基图连通)。
1. 有向图欧拉回路
判定定理 4: 一个有向图存在欧拉回路,当且仅当:
- 每个节点的入度等于出度,即对于所有节点 ,都有 。
2. 有向图欧拉路径
判定定理 5: 一个有向图存在欧拉路径,当且仅当满足以下两种情况之一:
- 符合欧拉回路的条件(起点和终点重合)。
- 恰好有两个节点的入度不等于出度:
- 其中一个节点满足 (此为起点)。
- 另一个节点满足 (此为终点)。
- 其余所有节点的入度等于出度。
Hierholzer (HE) 算法
Hierholzer 算法是寻找欧拉回路或欧拉路径的一种高效算法,其核心思想是“贪心搜索 + 回溯记录”。
1. 算法流程
- 确定起点:
- 如果找欧拉回路,可以从任意度数不为 0 的点出发。
- 如果找欧拉路径,必须从满足条件的“起点”(无向图中的奇度数点,或有向图中出度比入度多 1 的点)出发。
- DFS 遍历:
- 从当前节点出发,不断沿着未访问过的边向下搜索。
- 当前弧优化: 为了保证效率,每次访问一条边后,立刻将其从该点的边表中“逻辑删除”(通常用指针或索引移动),确保每条边只被扫描一次。
- 回溯入栈:
- 当某个节点的所有关联边都已经访问完毕(无法再继续走下去)时,将该节点压入结果栈(或数组)。
- 结果输出:
- 遍历结束后,将栈内的节点序列逆序输出,即得到一条完整的欧拉路径/回路。
3. 复杂度分析
- 时间复杂度: ,因为每条边只被访问并删除一次。
比较
| 类型 | 欧拉回路条件 | 欧拉路径条件 |
|---|---|---|
| 无向图 | 所有点度数为偶数 | 恰有 0 或 2 个奇度数点 |
| 有向图 | 所有点 | 所有点 ;或只有起点 且终点 |
De Bruijn 序列
1. 定义
De Bruijn 序列 是一个在一个大小为 的字符集上、包含所有长度为 的子串各一次的循环序列。
- 长度:(在圆环意义下)。
- 性质:任何长度为 的组合都在该序列中作为一个连续子串出现,且只出现一次。
示例 ():
循环序列 00010111 包含了 000, 001, 010, 101, 011, 111, 110, 100 全部 8 种情况。
2. 构造原理:De Bruijn 图与欧拉回路
构造 De Bruijn 序列的核心在于将其转化为一个图论问题。
构图规则
- 节点 (Nodes):代表所有长度为 的字符串。
- 节点总数:。
- 编号范围: 到 。
- 边 (Edges):代表一个“转移”操作,即添加一个新字符。
- 一条边对应一个长度为 的字符串。
- 边总数:。
转移逻辑 (滑动窗口)
从节点 (代表前缀)转移到节点 ,意味着:
- 扔掉 的最高位。
- 在末尾 添加 一个新字符 。
- 形成新节点 。
数学公式(二进制 ):
其中 mask 用于保留低 位,mask = (1 << (n-1)) - 1。
为什么是欧拉回路?
- 每个节点代表 位状态。
- 每个节点都有 个出边(加 0 或 加 1…)和 个入边。
- 图是连通的且 入度 = 出度。
- 因此,该图一定存在欧拉回路。
- 欧拉回路经过所有边恰好一次 生成所有长度为 的子串恰好一次。
#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;}分享文章
生成精美分享图或复制链接,与更多人分享本文。
继续阅读
换条路线
从其他文章中稳定抽取
最后更新于 ,距今已过 74 天
部分内容可能已过时