Christofides算法实现：多重图中欧拉回路的判定与疑问

1. 合并后多重图的欧拉回路构造 #

合并最小生成树（MST）与完美权重匹配的边后，图中所有顶点的度数均为偶数——MST中的奇度顶点会被完美匹配的边补全度数（每个奇度顶点新增一条边，度数由奇变偶），偶度顶点要么不新增边，要么新增偶数条匹配边，度数保持偶数。因此必然存在欧拉回路，构造可采用Hierholzer算法：

• 任选任意顶点作为起始点（无需特意选奇度顶点，此时已无奇度顶点）
• 沿未使用的边遍历，标记已走过的边，直至回到起点形成一个环
• 若仍有未使用的边，从当前环上某个还连有未使用边的顶点出发，再构造一个环，将其插入到原环的对应位置
• 重复上述步骤，直至所有边都被遍历完毕

2. 序列3->2->1->4->2是否为有效欧拉回路 #

这个序列不是有效欧拉回路，原因有两点：

• 欧拉回路要求遍历所有边后回到起始顶点，该序列起点是3，终点是2，不满足回路的闭合要求
• 欧拉回路必须遍历图中所有边恰好一次，即便假设该序列覆盖了所有边，仅从“未回到起点”这一点就不符合欧拉回路的定义

3. Christofides算法中能否用欧拉路径替代欧拉回路 #

不能，原因如下：

• 从图的性质来看：合并MST与完美匹配后的图所有顶点度数均为偶数，仅存在欧拉回路（欧拉路径要求图中恰好有0个或2个奇度顶点，0个对应回路，2个对应路径），不存在欧拉路径的存在基础
• 从算法逻辑来看：Christofides算法需要通过欧拉回路遍历所有边，再通过跳过重复顶点（shortcut操作）得到闭合的哈密顿回路，满足旅行商问题“回到起点”的要求。若用欧拉路径，最终得到的是起点终点不同的路径，无法直接转化为符合TSP要求的闭合回路

内容的提问来源于stack exchange，提问作者J.Doe