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

Question

我知道在一个无向图中，至少需要三个顶点才能形成一个循环。我的问题是，在一个有向图中，如果两个顶点互相指向彼此，这是否被认为是一个循环呢？

以下是一个例子：

这是一个循环图吗？

相关问题：

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

- Suragch

---

我会说那是一个循环，但我不知道是否有任何图形警察可以决定什么是循环和什么不是。然而，在无向图中称其为循环是愚蠢的，因为那样至少有一条边的任何图形都是环形的，该术语就失去了所有意义。 - Thomas Mailund

Answer 1

如果存在一个非空路径，起始于某个顶点并以同一顶点结束，则图形具有循环。在您上面的图表中，存在经过路径A -> C -> A的循环。同样，让我们想象一个包含2个顶点A和B以及2条边AB和BA（其中第一个字母是源顶点）的有向图. 这意味着存在一个循环A -> B -> A，因此你可以在一个包含2个顶点的有向图中拥有一个循环。

- Nick Clark

---

您使用术语“图”而不是“有向图”。您将此解释扩展到无向图吗？ - Suragch

正确。这也适用于有向图。我会更新我的答案，让它更清晰。谢谢！ - Nick Clark

感谢您在这里的解释。+1。我正在尝试为像我这样对图论不熟悉的人编写正式的解释。您知道有没有任何官方参考资料可以证明您所说的话？我找不到任何相关资料。 - Suragch

我没有我的旧大学教科书，但是维基百科对于循环的定义可以引导到那个逻辑。 - Nick Clark

Answer 2

我认为它（A-C-A）是一个循环。但我从不同的角度看待：您可能知道对于有向无环图（DAG），存在一种拓扑排序；否则，不存在拓扑排序。

拓扑排序实际上是一个偏序<=的线性扩展。因此，DAG是偏序<=的图形表示。请注意，根据偏序<=的反对称性质（即，如果a<=b且b<=a，则a=b），不存在两个边（a，b）和（b，a）同时存在于两个不同的顶点a和b之间。

总之，没有循环=>存在拓扑排序，因为在您的有向图中没有拓扑排序，因此必须存在一个循环（A-C-A）。

- Pat_Guangtailang

Answer 3

在有向图中，如果两个顶点彼此之间有两条互相指向的边，则不被视为循环。它们被称为平行边。

- Abhishek kumar

---

有向图上的平行边（或多重边）具有相同的源和目标顶点。您可以构建这样一个图形，使得一条边和一条反向边创建一个循环。 - Nick Clark

Answer 4

根据这个定义¹：

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

A-C被认为是一个电路。
A-C也符合这个定义²：

循环是一个电路，其中除了第一个（也是最后一个）顶点外，没有其他顶点出现超过一次。

所以它也是一个循环。

---

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

- c0der

---

根据这个定义，无向图中的两个相连顶点也会构成一个环，对吗？ - Suragch

这并没有回答问题。它询问了一个由两个顶点组成的图。 - Nick Clark

@NickClark，在我的例子中，A-C连接是两个顶点。我可能应该使用字母A-B来使其更清晰。 - Suragch