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

admin2021-08-17 49

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

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

答案D

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

转载请注明原文地址:https://kaotiyun.com/show/qW3i777K

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

计算机408
学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

将一个A[1．．100，1．．100]的三对角矩阵，按行优先存入-维数组B[1．．298]中，A中元素A66,65(即该元素下标i=66，j=65)，在B数组中的位置k为()。

下列关于银行家算法的叙述中，正确的是

现有一种解决无向连通图的最小生成树的方法：将图中所有边按权重从大到小排序为(e1，e2，…，em)；i=1；while(所剩边数≥顶点数){从图中删去ei；若图不再连通，则恢复ei；i++；

下列说法正确的是()。Ⅰ．当各边的权值相等时，广度优先遍历算法可用来解决单源最短路径问题Ⅱ．广度优先遍历算法可用来求无向图的所有连通分量Ⅲ．广度优先遍历算法类似于树中的后序遍历算法

在主机和外设的信息传送中，()没有使用程序控制方式。

CRT显示器显示图形图像的原理是图形图像()。

________，是指人们对他人的认知判断首先主要是根据个人的好恶得出的，然后再从这个判断推论出认知对象的其他品质的现象。晕轮效应的最大弊端就在于以偏概全。

地西泮有哪些药理作用及临床用途?

宋某15周岁，因喜好计算机，某日深夜潜入一公司内盗窃价值3万余元的计算机元器件，事发后均被追回。现问，对宋某的行为应如何处理?()

某化学反应在任何温度下都可以自发进行，此反应需满足的条件是()。

实施促进中部地区崛起战略，最重要的是要()，正确认识和把握中部地区的发展定位和特点，充分发挥比较优势，以新的思路促进中部崛起。

在基金销售业务信息管理中，交易清算、资金处理的功能，属于()。

企业如果延长信用期限，可能导致的结果有()。

根据《合同法》的规定，下列要约中，不得撤销的有()。

()是实施美育的重要途径，对于培养德、智、体等方面全面发展的社会主义事业的建设者和接班人，塑造完美的人格，提高全民族的素质，具有不可替代的作用。

入职后，你发现工作的单位与你的理想有很大的距离，怎么办?