Skip to content

欧拉图

概念

  • 欧拉回路：经过每条边刚好一次的回路
  • 欧拉通路：经过每条边刚好一次的通路
  • 欧拉图：具有欧拉回路的图
  • 半欧拉图：具有欧拉通路但不具有欧拉回路的图

性质

  • 欧拉图：
    • 所有结点的度为偶数
    • 欧拉图是若干个环的并，并且每条边必然处于奇数个环中
      • 一个很不严谨的 Proof: 假设这条边是 \(e(u, v)\)，那么对于每一个环，必然存在一条边 \(e^\prime(v^\prime, u)\) 与此条边对应，从 \(e^\prime\) 到结点 \(u\)，走 \(e\) 离开 \(v\)，如果它存在于偶数个环中，那么每个 \(e^\prime\) 都会对 \(\deg(u)\) 产生 1 个贡献，加上 \(e\) 的贡献那么 \(\deg(u)\) 必然是奇数，与上一条性质矛盾

判别

  • 无向图
    • 欧拉图
      • 非零度结点连通
      • 结点的度数都是偶数
    • 半欧拉图
      • 非零度结点连通
      • 只有两个节点的度数为奇数
  • 有向图
    • 欧拉图
      • 非零度结点强连通
      • 结点入度等于出度
    • 半欧拉图
      • 非零度结点强连通
      • 至多 1 个结点入度 - 出度 = 1
      • 至多 1 个结点出度 - 入度 = 1
      • 其余结点出度等于入度

求欧拉路/欧拉回路

一般使用 Hierholzer 算法，实质是 dfs 一个个求解单个环的过程，每次经过一条边就将其删除，dfs 完一个结点就将其弹入栈中，记录下这条边（从哪里进入该结点）。

void dfs(int u) {
    // 使用邻接矩阵存储
    for (int &v = cnt[u]; v < g[u].size(); ++v) { // 每次 ++v 相当于 ++cnt[u]，避免重复访问 0 ~ cnt[u]-1 号结点
        if (g[u][v]) {
            g[u][v] = g[v][u] = 0;
            dfs(v);
        }
    }
    stk.push(u);
}
为什么一定要在回溯时将结点入栈

考虑下面这张图：

如果从 1 开始 dfs，那么从一开始就将 \(u\) 入栈会得到一个可能的欧拉路径 1 2 3 4 1，而回溯时入栈会得到正确的欧拉路径 1 4 3 1 2。

不难发现，如果在回溯时入栈，那么发生入栈操作只会是在找到最后一条完整的欧拉回路/欧拉路径的情况下才会发生，即便在走某条欧拉回路中途走了一段“岔路”也会先直接将这一段岔路入栈，然后走完了这条欧拉回路才完整地将整条回路入栈，避免了“断层”现象。


Comments