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

题目

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

A.对

B.错

上一题 下一题

解答

正确答案是 A

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

C 10条回复评论

骊山语罢

只要你努力，总会有前途

发表于 2023-12-07 21:00:00

0 0

是小橘子吖

很基础的题，但还是要细心才能做对

发表于 2023-06-02 21:00:00

0 0

壁虎极点多

收藏不息，战斗不止

发表于 2021-11-08 23:00:00

0 0

橘子狂人

我想咨询下，如果是做产品经理，考研可以考哪些相关专业

发表于 2021-09-11 21:55:00

0 0

大葫芦

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

发表于 2018-10-13 11:19:15

0 0

星辰大海

有向无环图一定存在拓扑排序，但拓扑排序不一定唯一

发表于 2018-10-13 11:19:01

0 0

窦先生

并不是所有的图都存在拓扑序列。
有向图存在拓扑序列的充要条件是“该图是有向无环图”

发表于 2018-10-13 11:18:49

0 0

虹猫

一个有向图有拓扑序列的充要条件是该图是有向无环图。对角线以下元素均为零，表明只有顶点i到顶点j（i<j）可能有边，而顶点j到顶点i一定没有边，即有向图是一个无环图，因此一定存在拓扑序列

发表于 2018-10-13 11:18:37

0 0

米米大户

如果以上也为0呢？那不是不存在拓扑系列吗

发表于 2018-10-13 11:18:30

0 0

繁星知晓

对角线元素为1呢，这不也是有环么

发表于 2018-10-13 11:18:21

0 0

问题信息

分类：数据结构 - 图的属性

难度:

最新校招难题刷题，快来进刷题群吧