DAG中可以有多少条边？

在有n个顶点的有向无环图中，有向边的最大可能数是多少？DAG中可以有多少条边？

2012-07-28 user1559262

这个问题是关闭堆栈溢出主题。您可以尝试http://math.stackexchange.com/，欢迎所有级别的数学问题。 – 2012-07-28 07:19:50

更何况，这听起来像一个家庭作业问题。而且我采取了诱饵： -/ – 2012-07-28 07:21:10

此外，它是[我如何证明最大边数？]的副本（http://math.stackexchange.com/questions/61579/how-can-i-prove-最大数量的边缘） – 2012-07-28 07:25:19

假设有N个顶点/节点，让我们探索构建一个具有最大边缘的DAG。考虑任何给定节点，比如N1。它在这个早期阶段可以指向的最大节点数或边数是N-1。我们选择第二个节点N2：它可以指向除自身和N1之外的所有节点 - 这是N-2个附加边。继续剩下的节点，每个节点可以指向比之前的节点更少的边。最后一个节点可以指向0个其他节点。

萨姆所有边缘的：（N-1）+（N-2）+ ... + 1 + 0 ==（N-1）（N）/ 2

来源

2012-07-28 07:19:51

非常感谢您的回答。 – user1559262 2012-07-28 07:32:04

嗯，[这]（http://stackoverflow.com/questions/5058406/what-is-the-maximum-number-of-ed-in-a-directed-graph-with-n-nodes）似乎争论与答案。 – 2012-09-13 03:06:15

@RealzSlaw区别在于DAG是“非循环”的;您提到的帖子一般会讨论有向图。 – 2012-09-14 04:24:03

DAG中可以有多少条边？

回答

相关问题