首页 > 试题广场 >

n 个顶点的有向图中含有向边的数目最多为 ( )

[单选题]

n 个顶点的有向图中含有向边的数目最多为()

  • n-1
  • n
  • n(n-1)/2
  • n(n-1)
题目应对重边和自环的情况做个解释吧
发表于 2020-08-07 11:38:16 回复(0)
有向图,每个顶点都可以指向剩下的n-1个顶点,双向有向图??
发表于 2018-05-19 21:16:59 回复(0)
选D
n阶无向完全图:n(n-1)/2;
n阶有向完全图:n(n-1)。
发表于 2020-07-13 19:33:42 回复(0)
n阶无向完全图:n(n-1)/2;
n阶有向完全图:n(n-1)。
发表于 2019-04-24 08:24:37 回复(0)
注意:有向图
无向图则选C
发表于 2017-09-27 20:35:26 回复(0)
n(n-1),每个顶点都可以有(n-1)个有向边,所以是n(n-1)
发表于 2017-09-28 09:05:50 回复(0)
n阶无向完全图:n(n-1)/2;
n阶有向完全图:n(n-1)
选C
发表于 2022-11-14 15:24:43 回复(0)
当第一个结点指向其他n-1个结点时,第二个结点只能指向其余n-2个结点而不能指向第一个,否则成环。
从拓扑排序角度理解为何最大:
假设图用邻接矩阵存储同时编号成三角矩阵(有向无环图可以拓扑排序肯定可以编号),当存满上(或下)三角矩阵时边达到最多,同时假设还有有向边在下(或上)三角则必定成环。
发表于 2023-04-05 14:50:38 回复(0)