以下关于图的说法正确的是( )。　 Ⅰ在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧＜a，b＞Ⅱ若一个有向图的邻接矩阵中对角线以下元素均为0，则该图的拓扑序列必定存在Ⅲ在AOE网中一定只有一条关键路径

admin2019-05-10 29

问题以下关于图的说法正确的是( )。
　 Ⅰ在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧＜a，b＞Ⅱ若一个有向图的邻接矩阵中对角线以下元素均为0，则该图的拓扑序列必定存在Ⅲ在AOE网中一定只有一条关键路径

选项 A、Ⅰ、Ⅱ
B、Ⅱ、Ⅲ
C、Ⅰ、Ⅲ
D、仅有Ⅱ

答案D

解析说法工是错误的，在一个有向图的拓扑序列中，若顶点a在顶点b之前，只能说明顶点a到顶点b有一条路径。
说法Ⅲ是错误的，AOE网中可能有不止一条关键路径，它们的路径长度相同。
说法Ⅱ是正确的。任意n个顶点的有向无环图都可以得到一个拓扑序列。设拓扑序列为v₀，v₁，…，v_n-1，证明此时的邻接矩阵A为上三角矩阵，可用反证法证明。假设此时的邻接矩阵不是上三角矩阵，那么，存在下标i和j(i＞j)，使得A[j]不等于0，即图中存在从v_i到v_i的一条有向边。由拓扑序列的定义可知，在任意拓扑序列中，v_i的位置一定在v_j之前，而上述拓扑序列v₀，v₁，…，v_n-1中，由于i＞j，即v_i的位置在v_j之后，导致矛盾。因此说法Ⅱ是正确的。

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

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

计算机408
学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

简述采邑制的内容及其影响。

有关斯巴达国家建立传说的社会改革是()。

下列叙述不正确的是()。

17世纪英国资产阶级革命中，曾利用了古老文件同专制王权作斗争，这一古老文件是（）。

印度列国时代出现了16个国家，其中大部分是王国，只有少数的共和国。下列属于共和国的是()。

电子计算机的发展经过了四代，①电子数值积分计算机(ENIAC)；②集成电路计算机；③大规模集成电路计算机；④晶体管计算机；⑤人工智能计算机，其先后顺序是()。

(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，

编写判定给定的二叉树是否是二叉排序树的函数。

下列关于抢劫罪说法错误的是（）。

在柱顶水平集中力作用下，单层厂房排架柱顶总剪力应按

风湿性疾病疼痛的部位的叙述正确的是

有助于早期妊娠诊断的是

注射用无菌粉针用溶剂或注射液的稀释剂是（）。

在债券回购交易中，以券融资方在初始交易前，必须将足够的资金存入其委托的证券经营机构的证券清算账户。()

《中华人民共和国刑法》中规定了死刑缓期执行限制减刑制度，下列选项中可以适用该制度的是()。

与其他领域的信息相比，物流信息所具有的特点是()。

传统教育主张以学生为中心。()

甲、乙两车分别从A、B两地同时出发，相向而行，3小时后两车相遇。相遇后，甲车调头返回A地，乙车继续往前行驶。甲车到达A地后又调头行驶，半个小时后遇到乙车。问乙车从B地到A地需要多少小时?