0

好的，我知道有向无环图 (DAG) 有 E=V-1 边。E = 边数。V = 顶点数。

所以问题是，“在有向图 G 中，边的数量总是小于顶点的数量。” 对或错？

谢谢您的帮助。

4

1 回答 1

1

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

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

于 2013-09-25T04:06:56.383 回答