在具有欧拉路径的欧拉图中，这个算法是否存在反例？

Question

以下是寻找欧拉图的欧拉路径的算法。然而，据说存在一个小于10个顶点的反例。给定的欧拉图是无向的，每个顶点的度数都是偶数，并且它将从一个顶点开始和结束。

1. Perform a DFS traversal of G and number the vertices in DFS-preorder.
2. Re-initialize all vertices and edges of G as unused.
3. Produce a cycle as follows:
    Start from the vertex with preorder number 1 (computed in step 1), and
    repeatedly go to the vertex with highest preorder number possible along 
    an unused edge.
    Stop when all edges incident to the current vertex are used.

在过去的三天里，我一直在尝试使用6到9个顶点，但真的找不到一个例子。感谢任何帮助！谢谢。

- swordgit

---

你为什么认为有反例呢？所谓的“欧拉图”，是指具有欧拉路径或欧拉回路的图吗？ - Codor

@Codor 感谢您的回复。欧拉图是指每个顶点的度数都是偶数。提示中提到反例应该少于10个顶点。希望能给出一个反例。 - swordgit

好的，那么我想知道是什么让你认为有反例；如果每个顶点的度数都是偶数，无论邻居的偏好如何，都不会被卡住，我相信这一点。 - Codor

嗯，有被卡住的可能性；这个问题很有趣——到目前为止，我也没能想出反例。真是太神奇了。 - Codor

请纠正我如果我错了，但是算法不会被卡住吗？ A ---- B \ / C /
D ---- E 使用DFS- C A B D E 现在由于C是节点1，我们将从它开始，并且必须再次访问它才能进入其他循环。 如果您的代码理解正确，具有2个或多个公共节点的类似示例将导致错误。 - monster

Answer 1

根据欧拉图的定义，每个顶点的度数都是偶数，这有点学究，那么如果我们考虑该图是不连通的呢？

A---C   E---G
|   |   |   |
B---D   F---H

要在不同的组件上运行DFS - 需要在第一步之前发现完整的图形。

以下图形也不起作用，因为算法会经过路径：{0,3,4,7,1,3,2,1,0}，缺少5,6。

- Elliott de Launay

Answer 2

我发表这篇文章作为一个“答案”，因为我不知道如何在“评论”中正确显示图形，正如你所看到的那样。

嗯，如果我错了，请纠正我，但是按照以下图表，算法会被卡住吗？

 A---B
  \ /
   C 
  / \
 D---E

使用DFS- C A B D E

现在，由于C是节点编号1，我们将从它开始，并且必须再次访问它以转到其他循环。

如果您的代码理解正确，则具有2个或更多具有公共节点的类似图形将导致错误。

附言- 有人能告诉我如何在注释中开始新行吗？

- monster

---

我不确定我正确理解了你的观点；从 C 开始，使用给定的 DFS 序列，所提出的算法是成功的。 - Codor