algorithm - 如何证明有向无环图中至少存在一个入度为零的顶点？

Question

我可以凭直觉看出这个假设是正确的，但在数学上我无法证明。任何帮助将不胜感激。

Answer 1

让这个图有n个顶点。

假设我们反转所有的边，那么我们试图证明存在一个出度为零的顶点。

如果不是，则只需从任何地方开始并沿着 n 条边行进(总是可能的，因为每个顶点的出度都不是零)。因此，我们访问了 n+1 个顶点 - 因此至少其中 2 个顶点必须相同(鸽子洞原则)，因此我们在您的无环图中找到了一个环。