有向图: Euler路径

Question

在标准定义的基础上，欧拉路径是图中的一条路径，精确地访问每条边一次。

现在，我试图在有向图中找到一条欧拉路径。我知道欧拉电路的算法。如果一个图有Euler电路，它有Euler路径，这似乎很简单。

​

图片来源: geeksforgeeks.org

因此，对于上述有向图，它有一个Euler电路，也有Euler路径。

现在，如果我删除边缘，让我们说从4到0，它不再是一个欧拉电路。

1. 如果从顶点0启动我的DFS，我仍然有Euler路径。
2. 如果从顶点3开始，我没有Euler路径

那么，是否要求有向图必须在Euler电路中才能成为Euler路径？我想，欧拉路径应该比欧拉电路更少限制。

有无有向图可以是Euler路径，但不能是Euler电路。

Answer 1

那么，是否要求有向图必须在Euler电路中才能成为Euler路径？

不是

我想，欧拉路径应该比欧拉电路更少限制。

对，是这样

有无有向图可以是Euler路径，但不能是Euler电路。

是

我认为，您的困惑源于这样一个事实:当您从不同的节点开始使用有向图时，您可能会得到不同的结果，因为当您从不同的节点启动时，可能无法访问某些节点。这与欧拉路径/小径的定义无关。为了在有向图中“实现”对欧拉路径的搜索，您应该从每个节点运行DFS，并且只有当所有结果返回False (没有找到欧拉路径)时，才能确定不存在欧拉路径。如果存在欧拉循环，则必须有一个节点，您可以从该节点启动DFS并找到欧拉路径。

Answer 2

图具有欧拉电路/路径的要求：

• 电路(也算作路径)：没有顶点有奇数度。
• 路径(但没有电路)：两个顶点有奇数度；在这种情况下，路径将从一个奇点开始，在另一个点结束。