确定 Christofides 算法多重图中的欧拉循环

Question

我正在实现Christofides算法来解决旅行商问题，并且已经达到了我需要在多重图中找到欧拉循环的步骤。我不确定在组合 MST 和完美权重匹配边后从具有奇数度数的顶点开始时如何继续。以下是我采取的步骤：

1。最小生成树

2。完美的体重搭配：

3. Multigraph（结合 MST 和完美权重匹配）：

给定这个多重图，欧拉循环应该是什么？序列 3->2->1->4->2 是有效的欧拉游览吗？此外，欧拉路径足以代替 Christofides 算法的循环吗？

Answer 1

如果一条边同时出现在 MST 和 PWM 中，则图形应包含两个节点之间的多条边。下图仅显示节点 2 和 3 之间的一条边，但在您的情况下应该有两条边。这就是为什么它是一个多重图，而不是一个简单的图。
当正确添加边时，所有节点的度数均为偶数，就不会有这个问题，您可以轻松找到欧拉循环。

如果您使用 Python，NetworkX 已经内置了带有

MultiGraph()

的多重图功能。如果由于某种原因，您需要使用简单的图并且不能允许平行边，您实际上可以将图变成简单的图：每次两个节点之间存在双边时，添加 2 个新节点 X 和 Y 并将两条边替换为一条穿过 X 的边和一条穿过 Y 的边（有点像用中间节点将边减半）。这样，您仍然保留欧拉属性，您仍然找到欧拉循环，但您有一个简单的图，并且可以简单地从您的图中重建原始多重图。