在n个顶点的有向无环无权图的邻接矩阵

Question

在n个顶点的有向无环无权图的邻接矩阵中至少有（）个零元素。
A n B n(n-1)2 C n(n+1)2 D n(n-1)

Answer 1

基于Monster 组和GPT的调写：
B

在有向无环无权图中，不存在从一个顶点出发经过若干个边回到该顶点的回路，因此在该图的邻接矩阵中，对角线上的元素一定为0。

又因为该图是无向的，对于矩阵中的每个元素a[i][j]，如果a[i][j]为1，则a[j][i]一定为0（否则存在从j到i的回路），因此矩阵上下三角的元素一定存在一个为0。

所以，该有向无环无权图的邻接矩阵中至少有 frac{n(n-1)}{2}个零元素。

因此，选项B n(n-1)/2 是正确的。