ChristofidesAlgorithm:因子为 1.5 的欧拉游走近似方法

Christofides算法 因子为 1.5 的欧拉游走近似方法 图上的欧拉游走是将图的每条边都包含一次的游走。 我们的下一个算法取决于图论中的以下基本定理：连通图 G 的每个顶点都有偶数度，当当 G 有欧拉游走。 顺便说一句，很容易看出欧拉游走只有在图的所有节点都具有偶数度的情况下才能存在：每次游走通过一个节点时，它必须使用两条边（一条进入节点，一条离开）。 在步行中没有边被遍历两次，所以如果一个节点被访问了 c 次，它必须有度 2c，一个偶数。 ##使用欧拉游走定理，我们可以得到一个因子 1.5 的近似值。 这种方法称为 Christofides 算法： 求给定图 G 的 MST。 识别 MST 中的所有奇度节点 图论中的另一个基本定理说，图中奇数节点的数量是偶数。 很容易理解为什么会这样：图中所有节点的度数之和是图中边数的两倍，因为每条边都将其连接的两个节点的度数都增加了 1