想知道我们是否可以证明以下内容或者是否已经证明我在哪里可以得到证明。
令 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 i.t 的循环 t->v1->v2->t 或 t->v2->v3->t。但是无法证明这一点。
谢谢
最佳答案
LET US USE THE METHOD OF PROOF BY CASES:
(由于打字困难，我 Handlebars 写的几页扫描出来，附在这里供大家引用。)
让我们考虑一个图 G，其顶点为 v1、v2、v3...vn。设图 G 为无环有向图。
如果k=0， 显然 t->vi->vj->t 有一个长度为 3 的子循环。
因此证明。
希望对您有所帮助!
关于algorithm - 有向图中的循环，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7266468/