Christofides 算法

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

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

没有三角不等式时，跳过重复顶点可能显著增重，$3/2$ 保证随即失效；一般非 metric TSP 不能套用本算法的近似证明。若输入只给部分边且边权非负，可以先取全对最短路距离形成 metric closure，在度量闭包上运行算法，再把输出直达边展开成原图路径。无向原图若含负边，沿该边往返就会使最短游走成本无界下降，因而不能产生有限度量闭包。

$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}$。由于 $|O|$ 为偶数，这个 cycle 的边可交替拆成两份完美匹配；两份总权不超过 $\mathrm{OPT}$，所以较轻一份至多 $\mathrm{OPT}/2$。算法选择最小权完美匹配，故

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

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