2

我正在查看 TopCoder 上的 PenLift 问题，在阅读了这篇社论之后，我现在明白了如何去做，但是有一件事我不明白。

一个众所周知的定理指出，要遍历连通图中的所有边需要 numOfOddVertices/2 个总路径。

这是什么理论？还有为什么会这样？我的第一个想法是通过添加边来找到欧拉路径，使所有顶点除了 2 之外的度数都是偶数，因为这将允许欧拉路径。我不确定这是否正确，如果正确，我怎么知道这是最好的方法，这似乎很贪婪，但我没有看到任何证据。有人可以将我链接到理论或解释它是如何工作的吗？提前致谢。

4

3 回答 3

3

这是什么理论？

图论。

还有为什么会这样？

我们需要假设至少一对奇度顶点。

下界：归纳证明具有 2k 个奇数度顶点的图至少需要 k 条路径。基本情况 k = 1：微不足道。步骤 k > 1：从具有 2k 个奇数度顶点的图中删除一条路径至少留下 2k-2 = 2(k-1) 个奇数度顶点。

上限：用连接成对不相交的奇度顶点对的 k 条边来扩充图。现在所有顶点的度数都是偶数，所以存在欧拉回路。从此电路中删除新边；剩下k条路径。

于 2013-04-03T12:37:04.973 回答
2

在图中，奇数顶点 (n) 的数量始终为零或偶数。如果 n = 0，您可以从任意点开始遍历整个图形。如果 n > 0，要遍历图形，您应该始终从一个奇数顶点开始，您将从另一个奇数顶点结束。假设您连续绘制的路径数为 K。

  • 如果 n = 2，您仍然可以一次遍历图形。即从一个奇数顶点开始，在另一个顶点结束。K = 1
  • 如果遍历一次后 n = 4，您将留下一个具有 2 个奇数顶点的子图。您可以一口气遍历该子图。K = 2
  • 如果 n = 6，您将不得不遍历图表 3 次。K = 3 以此类推......

请阅读我的博客文章以获取更多信息。http://jeewanthad.blogspot.com/2012/11/eulerian-trail.html

于 2013-04-03T13:09:35.927 回答
0

首先，原问题中提出的方法肯定是正确的：将除两个之外的所有奇数顶点配对，在每对之间添加一条边，然后计算欧拉路径。添加的边对应于最终遍历中的移动。

如果希望最小化笔式绘图仪或类似设备的运动，请考虑以下事项：绘制线条的运动始终等于边长的总和，因此保存运动的唯一方法是最小化运动。添加的边表示移动，因此目标是以最小化添加边长度的方式配对奇数顶点。这实际上是一个众所周知但相当困难的问题，称为“一般图上的最小成本完美匹配”（注意，一般图，而不是二分图）。有一种称为 Blossom 算法的算法可以在 O^3 时间内解决它，但我从未找到完整算法的令人满意的描述——所有这些都相当模糊和令人困惑。

于 2020-08-17T07:51:02.493 回答