若一个有向图的邻接矩阵对角线以下元素均为零,则该图的拓扑有序序列必定存在()
A.对
B.错
正确答案是 A
对角线以下元素均为零,表明只有顶点i到顶点j(i<j)可能有边,而顶点j到顶点i一定没有边,即有向图是一个无环图,因此一定存在拓扑序列,但是该拓扑序列不一定唯一,可以举反例证明。另外,若题目说对角线以上均为1,以下均为0,则拓扑序列唯一。
只要你努力,总会有前途
很基础的题,但还是要细心才能做对
收藏不息,战斗不止
我想咨询下,如果是做产品经理,考研可以考哪些相关专业
对角线以下元素均为零,表明只有顶点i到顶点j(i<j)可能有边,而顶点j到顶点i一定没有边,即有向图是一个无环图,因此一定存在拓扑序列,但是该拓扑序列不一定唯一,可以举反例证明。另外,若题目说对角线以上均为1,以下均为0,则拓扑序列唯一
有向无环图一定存在拓扑排序,但拓扑排序不一定唯一
并不是所有的图都存在拓扑序列。有向图存在拓扑序列的充要条件是“该图是有向无环图”
一个有向图有拓扑序列的充要条件是该图是有向无环图。对角线以下元素均为零,表明只有顶点i到顶点j(i<j)可能有边,而顶点j到顶点i一定没有边,即有向图是一个无环图,因此一定存在拓扑序列
如果以上也为0呢?那不是不存在拓扑系列吗
对角线元素为1呢,这不也是有环么
小程序没有分享到朋友圈的功能,但是产品为了推广,需要曲线实现这个功能,请给出设计方案?
B2C网站上促销价格出错了,如何做危机公关?
请你谈谈Cookie的弊端
cookies,sessionStorage 和 localStorage 的区别?
只要你努力,总会有前途
很基础的题,但还是要细心才能做对
收藏不息,战斗不止
我想咨询下,如果是做产品经理,考研可以考哪些相关专业
对角线以下元素均为零,表明只有顶点i到顶点j(i<j)可能有边,而顶点j到顶点i一定没有边,即有向图是一个无环图,因此一定存在拓扑序列,但是该拓扑序列不一定唯一,可以举反例证明。另外,若题目说对角线以上均为1,以下均为0,则拓扑序列唯一
有向无环图一定存在拓扑排序,但拓扑排序不一定唯一
并不是所有的图都存在拓扑序列。
有向图存在拓扑序列的充要条件是“该图是有向无环图”
一个有向图有拓扑序列的充要条件是该图是有向无环图。对角线以下元素均为零,表明只有顶点i到顶点j(i<j)可能有边,而顶点j到顶点i一定没有边,即有向图是一个无环图,因此一定存在拓扑序列
如果以上也为0呢?那不是不存在拓扑系列吗
对角线元素为1呢,这不也是有环么