0
Follow
0
View

# The adjacency matrix of directed acyclic powerless graphs at n vertices

dy15145071020 注册会员
2023-02-26 16:20

The following answers are quoted from GPT-3 model, please use them wisely:

``````示例：

1  2  3  4  5
1   0  1  0  0  1
2   0  0  1  0  0
3   0  0  0  1  0
4   0  0  0  0  1
5   0  0  0  0  0

``````

dengkun1981922 注册会员
2023-02-26 16:20

B

In a directed acyclic unbounded graph, there is no loop from one vertex to that vertex through several edges, so in the adjacency matrix of the graph, the element on the diagonal must be 0.

Because the graph is undirected, for every element a[i][j] in the matrix, if a[i][j] is 1, then a[j][i] must be 0(otherwise there is a loop from j to i), so one of the elements of the upper and lower triangles of the matrix must be 0.

Therefore, the adjacency matrix of the directed acyclic powerless graph has at least frac{n(n-1)}{2} zero elements.

Therefore, choice B n(n-1)/2 is correct.

dongliming128 注册会员

Publish Time
2023-02-26 16:20
Update Time
2023-02-26 16:20