use*_*262 6 graph directed-acyclic-graphs
在具有n个顶点的有向无环图中,其中有向边的最大可能数是多少？
Ric*_*tze 20
假设N个顶点/节点,让我们探索构建具有最大边的DAG.考虑任何给定的节点,比如说N1.在这个早期阶段它可以指向的最大节点数或边数是N-1.让我们选择第二个节点N2:它可以指向除自身和N1之外的所有节点 - 即N-2个额外边缘.继续剩余的节点,每个节点可以指向比之前节点少一个边缘.最后一个节点可以指向其他0个节点.
所有边的总和:(N-1)+(N-2)+ .. + 1 + 0 ==(N-1)(N)/ 2
归档时间：
13 年，10 月 前
查看次数：
12378 次
最近记录：
8 年，7 月 前