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

admin2019-05-10 60

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

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

计算机408
学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

阅读材料，回答以下问题：材料一：与其等农民自下而上来解放自己，不如自上而下来解放农民。——亚历山大二世材料二：农民这样地获得一定数量的土地为私产后，因为赎买了土地，他们就摆脱了对地主的义务，而成为

简述诺曼征服的过程及其影响。

简述资产阶级改良派与革命派论战的主要内容。

论述世界反法西斯联盟形成的过程。

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

1920年，苏俄农民中流传着这样的说法：“土地属于我们，面包却属于你们；水属于我们，鱼却属于你们；森林属于我们，木材却属于你们”，它反映的是战时共产主义政策()。

下列关于民族大迁徙的说法不正确的是()。

某浮点机字长16位，其浮点数格式为：阶码5位(含1位阶符)，采用补码表示，尾数11位(含1位数符)，采用补码表示，且尾数为规格化形式。已知X=0．1011000011×20.0101，Y=0．0001100000×20.1000，试求X+Y．要求写出详细的

如何运用SBA的运行规则和战略主体、战略关系、战略关键分析法?

临产4小时，宫缩25～35秒，间隔4～5分钟，胎儿140次／分，先露浮，突然破水，羊水清亮，查宫口开大1cm，下列哪些处理是恰当的

关于自首，下列哪一选项是正确的?

关于项目方案净现值与基准收益率关系的说法，正确的是()。

在编制机械台班使用定额时，不可避免的中断时间包括()。

报关员的记分周期从每年()。

某6年期零息债券面值100元，发行价格为76元。另一信用等级相同的6年期付息债券，面值1000元，票面利率6％，每年付息，则其发行价格为()元。

以下哪些是声誉风险管理中应强调的内容?()

上市公司的行为被认定为虚假陈述行为后，某投资人在基准日之前卖出持有证券的，其投资差额损失的计算方式是()。

两个不透明的布袋A和B里面各放着6个球，其中，布袋A中的球有3个标为数字1．2个标为数字2，1个标为数字3；而布袋B中的球分别标为1、2、3、4、5、6。若某人分别从布袋A和B里取一个球，这两个球的数字之和不大于3的概率是多少?