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

admin2019-05-10 28

问题以下关于图的说法正确的是( )。
　 Ⅰ在一个有向图的拓扑序列中，若顶点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://kaotiyun.com/show/u9Ci777K

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

计算机408
学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

简述董仲舒及其主要思想。

关于“一战”后构筑的凡尔赛体系，说法不正确的是()。

下列内容，哪些与垄断组织出现有关?()①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治和经济生活④积极向外扩张，从经济上瓜分世界

第二次世界大战后，资本主义经济出现的新特点有()。①美国资本加强了对西欧和日本的渗透②国家开始参与资本主义生产过程③国家成为资本主义私有制的保护者④科技成果更为迅速地转化为生产力

清政府被迫签订丧权辱国的《辛丑条约》后，彻底沦为“洋人的朝廷”。最能印证这一说法的是，清政府()

下列有关《布列斯特和约》的说法中，错误的一项是()。

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

下列不属于苏联高度集中的经济政治体制产生的条件的是()。

______isnotacomedy.()

(2008年第55题)乳腺髓样癌的病理组织学特点是

胃溃疡合并完全性幽门梗阻，手术前准备最重要的是()

根据《民事诉讼法》，下列案件纠纷均适用专属管辖的是()。

尿液用于营养评价的意义包括()

在当前打开的表中，显示"书名"以"计算机"开头的所有图书，下列命令中正确的是(　　)。

下列定义数组的语句中错误的是()。

A、父母B、领导C、她自己D、她的老师D说话人说“我最想感谢的一个人就是我的老师”，所以选D。

Britainhasannouncedthatitistocancelabout200millionpounds’worthofdebts【T1】______itbypoorerCommonwealthcountries

剪纸