graph-algorithm - 该算法在欧拉图中找到欧拉路径是否有反例？

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

根据定义欧拉图是每个顶点的度数为偶数的图，这有点迂腐，那么如果我们认为该图是不连通的呢？

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

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

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