有向图中的环

Question

有向图中的环

3

想知道我们是否可以证明以下内容或者它已经被证明了，我应该去哪里获取证据。

设有n+1个顶点v1,v2,v3...vn和t组成一个有向图。v1,v2,v3...vn形成一个有向无环图。t与v1,v2,v3...vn中的每个顶点都相连。现在由于v1,v2,v3...v4以无环方式连接，如果存在一个循环，则它将涉及到t。我们能否证明所有长度大于3的循环都将始终涉及到长度为3的循环。请记住，t与每个v1,v2...vn相连，且不存在成对循环。

进一步解释问题。

假设顶点v1,v2,v3..vn的无环有向图是v1->v2->v3->...vn。每个v都与t有一条边相连。假设存在一个循环t->v1->v2->v3->t。这样的循环似乎肯定涉及长度为3的循环，即t->v1->v2->t或t->v2->v3->t。但是我们无法证明这一点。

谢谢

- Lipika Deka

t->v1->v2->2 应该变为 t->v1->v2->t 吗？ - Muthu Ganapathy Nathan

它是通过有向边连接到vn的 - 单个方向 - 还是双向连接？如果是前者，我认为你的结论是不正确的。如果是后者，则证明是微不足道的；然而，在这种情况下，t和每个其他节点之间也存在长度为2的循环，这也可以说是一个争议。 - davmac

@davmac....t 通过单向连接与 vn 相连...我的结论可能是不正确的，因此想要通过证明来确认。你能否举一个不正确的例子？谢谢。 - Lipika Deka

@Juggler，实际上我认为结论是正确的，证明如下。 - davmac

3个回答

5

让我们采用按情况证明的方法:

(由于符号难以输入，我扫描了手写页面并附在此供您参考。)

让我们考虑一个有顶点v1、v2、v3...vn的图G，让图G成为一个无环有向图。

如果k=0，则显然存在t->vi->vj->t的长度为3的子循环。

因此，证毕。

希望这能帮助到您！

- Muthu Ganapathy Nathan

+1 因为你比我先完成了它...而且手写笔记也很棒。 - davmac

真的很喜欢手写笔记...非常感谢...学习证明后会再联系。 - Lipika Deka

@Juggler 我只在 Stack Overflow 上。如果您需要证明的任何部分的理由，请立即提出。 - Muthu Ganapathy Nathan

@Juggler 大多数人都会犹豫不决地问这个问题：这是你的作业还是你在哪种情况下接触到这个概念的？实际上，这是一个很好的概念。 - Muthu Ganapathy Nathan

@Eager_student，不是作业。这个问题是我正在处理的事务序列化问题衍生出来的。再次感谢您的帮助。 - Lipika Deka

2

简单证明：

假设t是包括va和vb以及其他节点的一个环的一部分，其中有一条边t -> va和vb -> t
那么在va和vb之间的循环中存在一系列节点[vc、vd、ve...]；
取集合中的第一个节点-vc。从t到vc或从vc到t都存在一条边（如你所述）；

4a. 如果边是从t到vc的，则存在比涉及[t、va、vb]更短的循环，因为我们可以直接从t跳到vc，绕过va；此外，如果这个新的循环长度大于3，那么就可以从步骤1开始在新的循环上重复此过程。

4b. 否则，边是从vc到t的，并且存在长度为3的循环-t到va，va到vc，vc到t。

因此，任何循环都可以缩短到长度为3。

- davmac

这正是我试图传达的内容。但是我用了两页纸和许多图表来解释，而你只用了一个段落就做到了。简短而精炼的解释加1分。 - Muthu Ganapathy Nathan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Arc · Accepted Answer

基本的想法是最短的循环长度为3, 因为(t连接了任何一个顶点)假设t只通过一条边与其他顶点相连,而且其他顶点没有不包含t的循环.

所以,一个循环至少有t和其他两个顶点.

任何形成与t循环的两个顶点之间的路径都至少有3个长度或更多.

对于这样的循环, 你可以找到在路径上直接相互连接(相邻)又都与t相连的两个顶点,因此它们组成长度为3的循环.

将v[a]和v[b]之间的路径想象成轮子的一个部分，并将路径上的顶点v[i]与t连接看作是轮辐…您总是可以找到v[a]和v[b]之间更短的路径。

[针对有向图的补充] 让v[a]来自t，v[b]去往t，v[a]通向v[b]。如果v[a]和v[b]之间的循环长度为3，则该语句成立。否则，必须存在一个跟在v[a]之后去向t的顶点（但不是v[b]），或者在v[b]之前来自t的顶点（但不是v[a]），其循环长度至少缩短了一个（只有两个方向可选：从t到达或到t）。重复缩短循环，直到长度为3。