证明：对有向图的顶点适当地编号，可使其邻接矩阵为下三角形且主对角线为全O的充要条件是该图为无环图。

admin2019-01-16 33

问题证明：对有向图的顶点适当地编号，可使其邻接矩阵为下三角形且主对角线为全O的充要条件是该图为无环图。

选项

答案此题考查的知识点是无环图的定义。根据题意，该有向图顶点编号的规律是让弧尾顶点的编号大于弧头顶点的编号。由于不允许从某顶点发出并回到自身顶点的弧，所以邻接矩阵主对角线元素均为0。先证明该命题的充分条件。由于弧尾顶点的编号均大于弧头顶点的编号，在邻接矩阵中，非零元素(A[i][j]=1)自然是落到下三角矩阵中；命题的必要条件是要使上三角为0，则不允许出现弧头顶点编号大于弧尾顶点编号的弧，否则，就必然存在环路。(对该类有向无环图顶点编号，应按顶点出度顺序编号。)

解析

转载请注明原文地址:https://jikaoti.com/ti/tpfjFFFM

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

证明：对有向图的顶点适当地编号，可使其邻接矩阵为下三角形且主对角线为全O的充要条件是该图为无环图。

计算机408

学硕统考专业

罗马帝国疆域扩张到顶点是在()统治时期。

詹天佑自主设计修建了中国第一条铁路是在()。

中国第一条自行设计修建的铁路是在()。

“瓜步之战”发生在下列哪两个政权之间?()

中国第一条自行设计修建的铁路是在（）。

IP数据报的报文格式如下图所示。在没有选项和填充的情况下，报头长度域的值为()。

简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图G有n个结点，其邻接矩阵为A[1．．n，1．．n]，且压缩存储在B[1．．k]，则k的值至少为()。

若无向图G=(V,E)中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是____。

下图是某存储芯片的引脚图，请回答：(1)这个存储芯片的类型(是RAM还是ROM)?这个存储芯片的容量?(2)若地址线增加一根，存储芯片的容量将变为多少?(3)这个芯片是否需要刷新?为什么?刷新和重写有什么区别。(4)

CISC与RISC的区别表现在()。

A．中心静脉压低，动脉压低B．中心静脉压低，动脉压正常C．中心静脉压高，动脉压低D．中心静脉压高，动脉压正常E．中心静脉压正常，动脉压低

盐酸美他环素“杂质的吸收”的检查项目主要是控制

下列善治胃肠实热证的口舌生疮的实火证类非处方中成药是

麻风的最主要传染源是()。

在法学上，一般认为，划分法律部门的主要依据是()。

急に雨が降り()。