试题-若一个有向图的邻接矩阵对角线以下元素均为零,则该图的拓扑有序序列必定存在()

题目

若一个有向图的邻接矩阵对角线以下元素均为零,则该图的拓扑有序序列必定存在()

A.对

B.错

解答

正确答案是 A

对角线以下元素均为零，表明只有顶点i到顶点j（i<j）可能有边，而顶点j到顶点i一定没有边，即有向图是一个无环图，因此一定存在拓扑序列，但是该拓扑序列不一定唯一，可以举反例证明。另外，若题目说对角线以上均为1，以下均为0，则拓扑序列唯一。

C 11条回复评论

帖子还没人回复快来抢沙发