这个算法在欧拉图中寻找欧拉路径有反例吗？

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.

在过去的3天里，我一直在尝试从6到9的顶点，但我真的想不出一个例子。如有任何帮助，我们不胜感激！谢谢。

Answer 1

我将此作为answer发布，因为我不知道如何在comment中正确显示图形，正如您所看到的那样。

好吧，如果我错了，请纠正我，但是算法不会因为下面的图而受到打击-

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

使用DFS- C A B D E

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

如果我对你的代码的理解是正确的，那么具有2个或更多具有公共节点的循环的类似图将会给出错误。

PS-有人能告诉我如何在评论中开始换行符吗？

Answer 2

根据欧拉图是一个每个顶点都有偶数度的图的定义，这有点书呆子气，那么如果我们认为这个图是不连通的呢？

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

为了在不同的组件上运行DFS -在#1之前需要有一个步骤来发现完整的图。

下面的图也不会工作，因为算法将采用路径：{0,3,4,7,1,3,2,1,0}缺少5,6。

​

​