专栏文章

证明Hierholzer算法求字典序最小的欧拉回路的正确性

WWJnY
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minjy4f3
此快照首次捕获于
2025/12/02 03:38
3 个月前
此快照最后确认于
2025/12/02 03:38
3 个月前
查看原文
看了网上有关此算法的博客，感觉还不太明白的 OI 友可以看此篇文章

为什么写这篇文章

Hierholzer 应该算是一个基础的算法（毕竟它的板子题只有绿）。可能因为这个原因，网上关于它的博客都比较肤浅，尤其是它用于求字典序最小的欧拉回路的正确性。所以本蒟蒻想给它一个完整的证明（可能以下内容对身为大佬的你来说是显然的事情）。

对 Hierholzer 算法过程的分析

这个算法本质是 CircleClear 与 CircleMerge 两个过程的结合
这是 oiwiki 上的代码片段（显然这个算法是以 dfs 为基础的）：
CPP
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);
}
断言：同一层的函数执行中，打 * 号的分支最多只会进入 22 次。（看了下面的分析你就明白了）

介绍 CircleClear

考虑这样一个过程：选定一个起点 ss，从 ss 开始，每次走到当前所在点随便一个邻居，并删掉当前点到选定邻居的这条边，直到当前点无路可走。你惊奇地发现，最后一定会停在 ss 点。
简证（反证法）：设最后停留点为 tt，则 s→ts \to t 路径中间的点（即除开 s,ts,t 的路径上的点）的度数被减少了偶数次，此外 s,ts,t 的度数各被额外减了一次。若 s≠ts\ne t 则 tt 当前的度数为奇数，显然还有路可走，矛盾。所以 s=ts = t。
也就是说，在上述过程结束后，删掉的边构成了包含 ss 的一个回路。我们称这个过程为一次 CircleClear。

介绍 CircleMerge

对于两条回路 c1c_1 和 c2c_2 有公共点 uu，钦定 c1c_1 上一个点 ss 为“起点”。取 c1c_1 上 ss 到 uu 的路径，拼上 c2c_2，再拼上 c1c_1 上 uu 到 ss 的路径，就能将这两个回路“合并”成一个新的合法回路。我们称这个过程为一次 CircleMerge。

CircleClear + CircleMerge = Hierholzer

当我们选定一个起点 ss 开始调用函数，函数会不断地进入 * 号所在分支并不断递归，直到当前点所有连出的所有边都已被走过。这其实是一个 CircleClear 的过程，由前分析，最后一定会在起点 ss 停止递归（记这一次 CircleClear 找出的环为 c1c_1）。接下来是一个回溯过程，不断结束当前的函数调用并返回上一层，直到当前的点又有路可走（记这个点为 uu），便再次进入 CircleClear 的过程（即第二次进入 * 所在分支，在这次 CircleClear 结束后，uu 已没有连边，所以不会第三次进入 * 所在分支，记这次找到的环为 c2c_2）。
在函数退出是将点加入答案，最后将答案序列翻转，本质上是进行 c1c_1 与 c2c_2 的 CircleMerge（钦定了 ss 为起点，uu 为公共点）。因为只有这样，才能使 c2c_2 被“夹在”了 c1c_1 中间。
若要求出字典序最小的欧拉回路，便要在 dfs 的过程中每次优先访问最小的点，正确性证明如下：

证明过程

考虑归纳证明，设该算法能在点数 <n<n 时求出最小字典序的欧拉回路，证明它也能在点数为 nn 时求出最优解。
算法会从字典序最小的位置开始，每次遍历字典序最小的节点，找到一条字典序最小的回路（CircleClear）。
若所有边已被遍历到，则它显然一定是字典序最小的欧拉回路。
否则，去掉这些被遍历的边，图必将分裂成若干联通子图，每个联通子图都是一个欧拉图。对于每一个联通子图，都必须将其一个欧拉回路插入到一开始找到的环中（CircleMerge）。
记找到的环上节点按遍历顺序依次为 v1,v2,…,vk(v1=vk)v_1,v_2,\dots,v_k(v_1=v_k)，我们知道，对任意的 1≤i≤k−11\le i\le k-1, vi+1v_{i+1} 必然是 viv_i 所有邻居中最小的那一个。因此，若在位置 ii 的后面插入一段联通子图的欧拉回路 v1′,v2′,…,vt′v'_1,v'_2,\dots,v'_t（使序列变为 v1,v2,…,vi,v1′,v2′,…,vt′,vi+1,vi+2,…,vkv_1,v_2,\dots,v_i,v'_1,v'_2,\dots,v'_t,v_{i+1},v_{i+2},\dots,v_k）。由于 v1′v'_1 是 viv_i 的邻居，所以必有 v1′>vi+1v'_1>v_{i+1}，也就是说，一次这样的插入操作必然使序列从第 i+1i+1 位开始字典序变大。
对于每一个联通子图的插入，我们的首要任务是使它插入的位置 ii 尽可能大。由上论述，这会使字典序开始变大的位置尽可能靠后，从而保证了字典序的最小性。
在 Hierholzer 算法的回溯过程中，一遇到未访问的边就去遍历它，保证了这一点（因为回溯是从 kk 往 11 回溯的）。
由归纳假设，v1′,v2′,…,vt′v'_1,v'_2,\dots,v'_t 是所有可能中字典序最小的。
综上所述，该算法正确性得证。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...