Christofides 算法

MST 已经用较低成本连通所有顶点，但连通并不保证能一笔走完所有边。奇度顶点正是 Euler 回路的障碍：给两个奇点之间加入一条匹配边，会同时翻转它们的度数奇偶性。奇点总数为偶数，所以完美匹配能一次修复全部障碍；选择最小权匹配，则把修复成本控制在最优旅行商回路的一半以内。

Euler 回路提供的是一条可能反复经过顶点的连通遍历。度量三角不等式允许把这些重复绕行剪成直达边而不涨价，于是“便宜连通骨架—奇偶修复—Euler 遍历—shortcut”四步分别解决连通性、可遍历性和每点恰访一次。

没有三角不等式时，跳过重复顶点可能显著增重，$3/2$ 保证随即失效；一般非 metric TSP 不能套用本算法的近似证明。若输入是有限连通无向图且边权非负，可以先取全对最短路距离；含零边时得到的可能是伪度量，不同顶点距离可为零，但本页的非负性、对称性和三角不等式证明仍适用。在闭包上运行算法，再把直达边展开成原图路径，得到的是访问全部顶点的闭合游走，允许重复顶点和边，并对原图最短此类游走保留 $3/2$ 界；这不保证原稀疏图存在 Hamilton 回路。图不连通时无法产生有限的全点闭包。无向原图若含负边，沿该边往返就会使最短游走成本无界下降，因而不能产生有限度量闭包。

$T\uplus M$ 是多重图，平行边不能去重。这里的 Euler 回路是“每条多重边恰走一次”的图论对象；它与树上把 DFS 进入、退出序列化的Euler tour 技巧理路树的 Euler Tour 技巧Euler tour technique for trees用 DFS 次序把子树或树上行走线性化，并区分三种常见序列。只是同名对照，后者既不修复奇度，也不为 Christofides 提供所需回路。

$3/2$ 近似保证 ​

按近似比理路近似比Approximation ratio近似算法解值与最优值之间的最坏情形乘法保证。比较算法回路与最优 metric TSP 回路，记最优值为 $\mathrm{OPT}$。从最优 Hamilton 回路删除一条边会得到一棵生成树，因此

按最优回路上的出现顺序连接奇点集合 $O$ 中的相邻顶点，并对每段中间路径做 metric shortcut，可得到一个经过全部奇点的 cycle，其总权不超过 $\mathrm{OPT}$。对 $|V|\ge 3$ 的树，$|O|\ge 2$。当 $|O|=2$ 时，这个闭合行程包含同一端点对的两份边，分别视为两条独立副本；一般偶数 $|O|$ 时按环次序处理。因此其边可交替拆成两份完美匹配；两份总权不超过 $\mathrm{OPT}$，所以较轻一份至多 $\mathrm{OPT}/2$。算法选择最小权完美匹配，故

结合 MST、匹配与 shortcut 三个界，得到

这条证明同时解释了三个条件为何不能省：MST 提供不超过最优值的连通骨架，最小完美匹配控制奇偶修复成本，度量性保证最后从 Euler 回路恢复 Hamilton 回路时不增加成本。

计算成本 ​

算法须调用精确的最小权完美匹配子程序；无权最大基数匹配并不能控制这里的修复成本。若完整距离矩阵显式给出，除 MST 与加权匹配的求解成本外，读取输入需 $\mathrm{\Theta }(|V{|}^2)$，而所得多重图只有 $O(|V|)$ 条边。用边身份、邻接表与栈构造 Euler 回路并 shortcut 只需 $O(|V|)$ 次基本操作。有限有理距离采用多项式时间的 MST 和一般图最小权完美匹配实现，就得到关于输入编码长度的多项式算法。