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

admin2019-05-10 32

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

学硕统考专业

简述10—13世纪大垦殖运动的内容及其影响。

下列不属于凯末尔主义内容的是()。

论述印度非暴力运动的过程和失败原因。

试分析第二次工业革命的特点及其影响。

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

在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(logn)的算法，确定树中第k个结点的位置。

已知某CPU有16根地址线、8根数据线，并用MREQ作为访存控制信号(低电平有效)。现有下列存储芯片：1K×4位ROM、2K×4位ROM、4K×8位ROM、4K×8位RAM、8K×4位RAM、8K×8位RAM和非门、与非门、或非门若干，如下图所

举例说明P、V操作为什么要求设计成原语(即对同一信号量上的操作必须互斥)。P(S)操作：S．value--；If(S．value＜0){AddthisprocesstoS．L；Block()；

运动中ATP消耗后的补充速度成为影响运动能力的重要因素。()

下列关于辅导目标制定原则的说法中不正确的是()

由日本管理大师石川馨所提出的战略分解工具是【】

市场预测中，预测过程可视为一个()过程。

皮亚杰认为儿童的道德发展大致分为两个阶段，10岁前称为他律道德，10岁后称为______。

儿童体格发育最重要及最常用的形态指标是()。

圆形的周长扩大至原来的2倍，它的面积比原来增大(　　)。

VIP客户端应用程序通常有三种类型：传统的FTP命令行、【　　】和VIP下载工具。

Whymoreandmorepeoplebecameinterestedinbecomingcomputerprogrammers?Whichkindofcompanyisfavoredbymostemployees