15

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

4

1 回答 1

27

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

所有边的总和：(N-1) + (N-2) + .. + 1 + 0 == (N-1)(N)/2

于 2012-07-28T07:19:51.110 回答