到目前为止，求解TSP问题的启发式算法可以说是数不胜数，但是能通过理论而不仅仅是实验结果来保证算法求出的最优解与实际最优解之间差距的算法特别少，Christofides提出了一个具有该功能的经典算法，很多学者也在此基础上做了部分改进，个人感觉这个算法将图论的基本知识运用地非常巧妙，值得学习。

本篇文章将从Christofides Algorithm的伪代码入手，结合示意图解释其流程及近似比计算。

生成树：包含n-1条边，连接图G中n个点的连通图。

最小生成树：总长度最小的生成树。

度数：某顶点连接的边数。（奇数度的顶点用蓝色标出）

为什么说O中有偶数个顶点（即度数为奇数的顶点个数为偶数）？ （1）一条边的两个端点都会算上一个度，即一条边就有两个度，所以总度数是边数的两倍，为偶数。

（2）图的顶点度数要么是奇数要么是偶数，所以用总度数减去所有偶数度顶点的度数就是奇数度顶点的总度数，两个偶数相减肯定为偶数，公式如下图。

（3）因为奇数度顶点每个点度数均为奇数，所以其个数一定是偶数。

完全图：完全图是一个简单的无向图，其中每对不同的顶点之间都恰连有一条边相连。

匹配（或称独立边集）是指这个图之中，任意两条边都没有公共的顶点，这时每个顶点都至多连出一条边。

完全匹配是一个包括了图G中所有顶点的匹配。

最小完全匹配是连接边总长度最小的完全匹配。

O集的最小完全匹配如下：

为什么每个顶点都是偶数度的？ （1）最小生成树上偶数度的顶点没有变化，仍然是偶数度。

（2）最小生成树上奇数度的顶点因为附加了其自身的最小完全匹配，而最小完全匹配每个点只连接一条边，也就是度数只增加1，奇数加1就是偶数。

取完并集的示意图如下：

欧拉回路：从起点经过图中所有的边又回到出发点，且每条边只经过一次。

一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数，且该图是连通图。

从点1出发，其欧拉回路如下图：

哈密顿回路：从一点出发经过所有其他节点且只经过一次最后又回到出发点的线路。

跳过部分重复的顶点可得到以下哈密顿回路：

根据上一部分的伪代码解释，求解过程可用图简单表示如下：

假设原图的TSP最优路线为I，其长度为L(I)。Christofides Algorithm 计算出的最优TSP路线H（伪代码最后一步得到的哈密顿回路），路线长度为L(H)，计算过程中的最小生成树T的边总长度为L(T)，奇数度顶点集O的最小完全匹配M总长度为L(M)。

（1）欧拉回路E长度：L(E)=L(T)+L(M)，哈密顿回路H长度：L(H)