3

以下是在欧拉图中找到欧拉路径的给定算法。但是，据说有一个顶点少于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 的顶点，但我真的想不出一个例子。任何帮助表示赞赏！谢谢你。

4

2 回答 2

0

我将其发布为答案，因为我不知道如何在评论中正确显示图表，如您所见。

好吧，如果我错了，请纠正我，但算法不会因以下图表而被击中-

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

与 DFS- C A B D E

现在和C节点 1 一样，我们将从它开始，并且必须再次访问它才能进入另一个循环。

如果我对您的代码的理解是正确的，则具有 2 个或更多周期的具有公共节点的类似图表将给出错误。

PS-谁能告诉如何在评论中开始换行

于 2017-04-04T09:22:09.127 回答
0

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

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

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

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

图形

于 2021-04-10T15:14:08.890 回答