想知道我们是否可以证明以下内容，或者是否已经证明哪里可以找到证明。有向图中的循环
设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-> v1-> v2-> v3-> t。这样的循环似乎肯定涉及长度为3的循环，或者t→v1→v2→t或者t→v2→v3→t。但是，一个不能够证明这一点。
由于
让我们用证明方法的案件：
（因为它是很难输入的符号，我扫描的手写页和我附上这里供您参考。）
让我们考虑一个图G，顶点为v1，v2，v3 ... vn。并让图G是无环向图。
若k = 0， 很明显的情况下T-> VI-> vj-> T具有长度3.
的子周期。因此证明。
希望帮助！
+1，因为你打败了我......并且爱上了手写的笔记。 – davmac
认真地说，爱手写笔记...非常感谢..我回来后，我学习证明 –
@Juggler Iam堆栈溢出只。如果您需要证明任何部分的证明，现在就问自己。 –
的基本思想是，最短的周期具有长度为3，因为（I假设）t被通过一个连接到任何其它顶点且只有一个边缘，而另一个顶点不形成没有吨周期。
所以一个循环至少有t个和另外两个顶点。
与t形成一个循环的两个顶点之间的任何路径长度为3或更大。
对于这样一个周期，则可以查找既连接到t直接连接到彼此（邻居）的路径上的两个顶点，因此它们形成与长度3.
一个周期想象V之间的路径[a]和v [b]作为轮的一部分，以及到t的路径上的顶点v [i]的连接作为辐条...总是可以找到v [a]和v [ b]。
[用于定向GRAPH ADDITION]
令v [A]来自T和V [B]去T和V [A]领先至V [B]。 如果v [a]和v [b]之间的循环长度为3，则该语句成立。 否则，必须是后一个顶点v [α]将T（但不是V [B]），或v前一顶点并[b]从吨到来（但不是V并[a]），其周期是至少一种较短（只有两个方向可供选择：从t到t）。 重复使用周期短，直到到达长度3
@Archimedix ...你是对的，但我如何正式表明这一点。此外，我的图是一个有向图。谢谢 –
我已经通过归纳法添加了一些证明信息，应该不会太难以从那里形式化（顺便说一句，我猜这是一些任务，所以也许你应该尝试做那部分:-)）。 – Archimedix
您的解决方案是正确的。选择另一个是因为努力，他/她似乎是一个学生。希望它可以。 –
简单的证明：
假设t是一个循环，它包括VA和VB，和其他节点，其中存在边缘吨的一部分 - > VA和VB - >吨
那么在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.
这就是我试图提供的。但是我用2页的图解释了许多图表，但是你在一个段落中做了同样的事情，+ 1为简短而甜蜜的解释。 –
@davmac ...谢谢。 –
T-> V1-> V2-> 2必须是T-> V1-> V2->吨？ –
是否通过有向边 - 单向或两个方向连接到vn？如果前者，我认为你的结论是不正确的。如果是后者，证明是微不足道的;然而，在这种情况下，也可以说t和其他节点之间的长度为2的周期。 – davmac
@davmac .... t通过单一方向连接到vn ...我的结论可能不正确，因此希望通过证明查看它。你能举一个不正确的例子吗？谢谢 –