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

· · 算法·理论

看了网上有关此算法的博客，感觉还不太明白的 OI 友可以看此篇文章

为什么写这篇文章

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

对 Hierholzer 算法过程的分析

这个算法本质是 CircleClear 与 CircleMerge 两个过程的结合

这是 oiwiki 上的代码片段（显然这个算法是以 dfs 为基础的）：

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);
}

断言：同一层的函数执行中，打 * 号的分支最多只会进入 2 次。（看了下面的分析你就明白了）

介绍 CircleClear

考虑这样一个过程：选定一个起点 s，从 s 开始，每次走到当前所在点随便一个邻居，并删掉当前点到选定邻居的这条边，直到当前点无路可走。你惊奇地发现，最后一定会停在 s 点。

简证（反证法）：设最后停留点为 t，则 s \to t 路径中间的点（即除开 s,t 的路径上的点）的度数被减少了偶数次，此外 s,t 的度数各被额外减了一次。若 s\ne t 则 t 当前的度数为奇数，显然还有路可走，矛盾。所以 s = t。

也就是说，在上述过程结束后，删掉的边构成了包含 s 的一个回路。我们称这个过程为一次 CircleClear。

介绍 CircleMerge

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

CircleClear + CircleMerge = Hierholzer

当我们选定一个起点 s 开始调用函数，函数会不断地进入 * 号所在分支并不断递归，直到当前点所有连出的所有边都已被走过。这其实是一个 CircleClear 的过程，由前分析，最后一定会在起点 s 停止递归（记这一次 CircleClear 找出的环为 c_1）。接下来是一个回溯过程，不断结束当前的函数调用并返回上一层，直到当前的点又有路可走（记这个点为 u），便再次进入 CircleClear 的过程（即第二次进入 * 所在分支，在这次 CircleClear 结束后，u 已没有连边，所以不会第三次进入 * 所在分支，记这次找到的环为 c_2）。

在函数退出是将点加入答案，最后将答案序列翻转，本质上是进行 c_1 与 c_2 的 CircleMerge（钦定了 s 为起点，u 为公共点）。因为只有这样，才能使 c_2 被“夹在”了 c_1 中间。

若要求出字典序最小的欧拉回路，便要在 dfs 的过程中每次优先访问最小的点，正确性证明如下：

证明过程

考虑归纳证明，设该算法能在点数 <n 时求出最小字典序的欧拉回路，证明它也能在点数为 n 时求出最优解。

算法会从字典序最小的位置开始，每次遍历字典序最小的节点，找到一条字典序最小的回路（CircleClear）。

若所有边已被遍历到，则它显然一定是字典序最小的欧拉回路。

否则，去掉这些被遍历的边，图必将分裂成若干联通子图，每个联通子图都是一个欧拉图。对于每一个联通子图，都必须将其一个欧拉回路插入到一开始找到的环中（CircleMerge）。

记找到的环上节点按遍历顺序依次为 v_1,v_2,\dots,v_k(v_1=v_k)，我们知道，对任意的 1\le i\le k-1, v_{i+1} 必然是 v_i 所有邻居中最小的那一个。因此，若在位置 i 的后面插入一段联通子图的欧拉回路 v'_1,v'_2,\dots,v'_t（使序列变为 v_1,v_2,\dots,v_i,v'_1,v'_2,\dots,v'_t,v_{i+1},v_{i+2},\dots,v_k）。由于 v'_1 是 v_i 的邻居，所以必有 v'_1>v_{i+1}，也就是说，一次这样的插入操作必然使序列从第 i+1 位开始字典序变大。

对于每一个联通子图的插入，我们的首要任务是使它插入的位置 i 尽可能大。由上论述，这会使字典序开始变大的位置尽可能靠后，从而保证了字典序的最小性。

在 Hierholzer 算法的回溯过程中，一遇到未访问的边就去遍历它，保证了这一点（因为回溯是从 k 往 1 回溯的）。

由归纳假设，v'_1,v'_2,\dots,v'_t 是所有可能中字典序最小的。

综上所述，该算法正确性得证。