有向图中的循环

Question

想知道我们是否可以证明以下内容,或者是否已经证明我可以在哪里获得证据.

令v1,v2,v3 ... vn和t为有向图中的n + 1个顶点.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.但是无法证明这一点.

谢谢

Answer 1

基本思想是最短周期的长度为3,因为(我假设)t通过一个且只有一个边连接到任何其他顶点,而其他顶点不形成没有t的周期.

所以一个循环至少有t和另外两个顶点.

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

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

想象一下v [a]和v [b]之间的路径作为车轮的一部分,路径上的顶点v [i]连接到t作为辐条...你总能在v [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的长度.

Answer 2

让我们按案例使用证明方法:

(因为很难输入符号,我扫描了手写页面,我附在这里供你参考.)

让我们考虑一个图G,其顶点为v1,v2,v3 ...... vn.让Graph G成为非循环有向图.

如果k = 0,则显然t-> vi-> vj-> t具有长度为3的子循环.

因此证实.

希望有所帮助!