有向图中两个顶点之间的循环

Question

我知道在无向图中必须至少有三个顶点才能形成一个循环。我的问题是，在有向图中，如果两个顶点有两条边互相指向，是否被视为循环？

这是一个例子：

这是循环图吗？

相关问题：

• 无向图中，最简单的环必须有3个节点？
• 图任意两个顶点之间存在环
• 无向图中的循环

Answer 1

如果存在一条从某个顶点开始并在同一顶点结束的非空路径，则图具有循环。在上图中，路径

A -> C -> A

上有一个循环。同样，让我们想象一个有向图，有 2 个顶点

A

和

B

以及 2 个边

AB

和

BA

（其中第一个字母是源顶点）。这意味着存在一个循环

A -> B -> A

，因此在 2 个顶点的有向图中可以有一个循环。

Answer 2

我想说（A-C-A）是一个循环。但我的角度不同：你可能知道，对于一个有向无环图（dag），它上面有一个拓扑排序；否则就没有了。

拓扑排序确实是偏序的线性扩展 <=. Thus, dag is the graphical representation of a partial order <=. Be aware that according to the anti-symmetry property of a partial order <= (i.e., if a<=b and b<=a, then a=b), there is no possibility that two edges (a,b) and (b,a) simultaneously exist between two distinct vertices a and b.

综上所述，不存在环=>存在拓扑排序，因为你的有向图上没有拓扑排序，所以一定存在环（A-C-A）。

Answer 3

不，如果有向图中两个顶点有两条边互相指向，则不认为是环。它们被称为平行边。

Answer 4

根据这个定义¹：

电路是一条至少有一条边的封闭路径

A-C 被视为一个电路。
A-C 也符合这个定义²:

循环是一个回路，除了第一个顶点（即 也是最后一个）出现不止一次。

所以这也是一个循环。

---

¹ 来源：https://proofwiki.org/wiki/Definition:Circuit
²来源：https://proofwiki.org/wiki/Definition:Cycle_(Graph_Theory)

Answer 5

不，因为您不会重复使用边缘。您至少只存储邻接列表表示的传出或传入。因此，如果没有其他边可以让您回到另一个顶点，那么无向图中两个顶点之间就不存在循环。但是，如果无向图中的 2 个顶点之间确实有平行边，我相信这将是一个循环。