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

admin2021-08-17 79

问题以下关于图的说法正确的是( )。
  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

学硕统考专业

主机H通过快速以太网连接Internet，IP地址为192．168．0．8，服务器S的lP地址为211．68．71．80。H与S使用TCP通信时，在H捕获的其中5个IP分组如题47一a表所示。请回答下列问题。若题47一a表中的某个IP分组在S发出时

为支持CD-ROM中视频文件的快速随机播放，播放性能最好的：艾件数据块组织方式是

硬磁盘共有4个记录面，存储区域内半径为10cm，外半径为15．5cm，道密度为60道／cm，外层位密度为600bit／cm，转速为6000r／min。问：将长度超过一个磁道容量的文件记录在同一个柱面上是否合理?

以下关于校验码的叙述中，正确的是()。I．校验码的码距必须大于2Ⅱ．校验码的码距越大检错纠错能力越强Ⅲ．增加奇偶校验位的位数可以提高奇偶校验的正确性Ⅳ．采用奇偶校验可检测出一位数据错误的位置并加以纠正

16位真彩色显示器可显示的颜色种数为()。

在人类思想史上第一次科学而全面地论述了道德的起源问题的理论是()

机体内环境的稳态是指

瘰疬溃破后疮口的特点是

建设项目业主进行投资决策的依据是()。

后退法的优点是()。

小组以形成方式分类可分为()。

1．题目：平移2．内容：3．基本要求：(1)联系生活实际让学生明白平移；(2)要有互动，设置纠错环节；(3)要有板书；(4)试讲时间10分钟。请根据以上要求进行试讲。

教育的质的规定性是指()。

甲、乙两船驶向不能同时停靠两条船的码头，它们一天到达时间是等可能的，如果甲停靠，则停靠的时间为1小时，若乙停靠，则停靠的时间为2小时，求它们不需要等的概率．

Accordingtothespeaker,howdocommutersfeelaboutcrossingtheGoldenGateBridgebycar?