基于判定算法构造哈密顿回路：如何证明构造算法的正确性？

问题背景 #

设G(V,E)为无向图。哈密顿回路（Hamiltonian Cycle）是恰好访问G中每个顶点v一次的回路（起始顶点除外，它同时也是回路的终点）。假设存在一个高效算法可判定图是否存在哈密顿回路（返回True/False），称该算法为判定算法D。需证明：存在一个高效算法可返回哈密顿回路。

我的构造思路 #

我想到的构造方法是这样的：

• 首先调用D(G)，如果返回True（说明原图存在哈密顿回路），先复制原图G得到G'，初始时G'和G完全一致；
• 遍历原图E中的每一条边e，依次执行以下操作：
  • 从G'中移除边e，得到临时图G'' = G' \ {e}；
  • 调用判定算法D，得到结果d_boolean = D(G'')；
  • 如果d_boolean=False，说明移除e后G''再也找不到哈密顿回路了——这意味着e必然是原图中某个哈密顿回路的一部分，所以把e重新加回G'；
  • 如果d_boolean=True，说明移除e后G''仍然存在哈密顿回路，e不是所有哈密顿回路的必要边，直接保留移除e后的G'即可；
• 等所有边都遍历完成后，返回最终的G'。

正确性证明 #

接下来咱们就一步步证明这个算法最终返回的G'确实是一个哈密顿回路：

1. 最终的G'一定存在哈密顿回路

初始状态下G'=G，而G本身存在哈密顿回路。在每一步处理边e的操作中，我们只有在确认移除e后图仍然有哈密顿回路时，才会保留移除操作；如果移除e会导致图失去哈密顿回路，我们就把e加回去。也就是说，每一步操作后，G'始终保持“存在哈密顿回路”的性质。所以遍历完所有边后，G'肯定还是存在哈密顿回路的。

2. 最终的G'的边数恰好等于顶点数|V|

哈密顿回路的边数刚好是|V|（因为回路是一个环，每个顶点对应一条边，总共|V|条）。我们来证明最终G'的边数就是|V|：

• 假设G'的边数大于|V|，那必然存在某条边e'，移除e'后G' \ {e'}仍然存在哈密顿回路——但按照我们的算法逻辑，在遍历e'的时候，我们应该已经把它移除了，这就和“G'包含e'”矛盾了；
• 同时G'的边数不可能小于|V|：因为我们的操作只会移除边（或者恢复必要边），而G'始终存在哈密顿回路，哈密顿回路至少需要|V|条边，所以G'的边数不可能比|V|少。

既然G'的边数恰好是|V|，而且它存在哈密顿回路，那这个图本身就只能是哈密顿回路——因为边数为|V|的无向图，如果存在哈密顿回路，那它不可能有多余的边，否则边数会超过|V|。

3. 每条保留的边都是哈密顿回路的必要组成部分

对于最终G'中的任意一条边e，当我们当初处理e的时候，移除e后的图被判定为D(G'')=False，也就是没有哈密顿回路。这说明e是G'中所有哈密顿回路的必要边——没有它就构不成回路。而G'本身存在哈密顿回路，所以这条e必然属于这个回路。

综合以上三点，最终得到的G'的边集恰好构成一个哈密顿回路，算法的正确性就得到了证明。

内容的提问来源于stack exchange，提问作者Gilad Gur