一个n个顶点的有向图最多有几条边

Question

如题所述

Answer 1

如果允许存在重边及自环的话应该可以有无穷多边，如果是单图的话，最多应该是其底图的最多的边数的2倍，即2*|e（kn）|=n*（n-1）条边。

Answer 2

设D=
为n阶有向简单图（即不含平行边，也不含环的图），若对于任意的顶点u,v属于V，既有有向边
,又有
,则称D是n阶有向完全图。数目求法：利用乘法原理，n×(n-1)就是最多的有向图边。

Answer 3

1个顶点没边，2个顶点1条，3个顶点3条，4个顶点6条，5个顶点10条
那么所以就有当n>=3多的时候，任意2个顶点就会有一条边，所以是c2/n