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

admin2012-06-26 55

问题以下关于图的说法正确的是( )。．
I在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧
Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O，则该图的拓扑序列必定存在
Ⅲ在．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的位置一定在v_j之前，而上述拓扑序列v₀，v₁，…，v_n-1中，由于i>j，即v_i的位置在v_j之后，导致矛盾。因此说法Ⅱ是正确的。

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

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

计算机408
学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

下面条约没有涉及德国的赔款问题的是()。

火的使用，是人类在征服自然的进程中所取得的伟大成果。人类开始使用天然火是在()。

下列不属于清统治者加强文化专制和思想控制的是()

以下对于清初恢复发展经济的措施论述正确的一项是()。①停止圈地②“更名田”③奖励垦荒④整顿赋役制度⑤废除匠籍

门罗宣言的内容及实质是什么?

从1939年春天起，国共双方军队在驻防结合部的摩擦冲突不断升级，不是这一时期惨案的是()

1948年，南斯拉夫对从苏联照搬来的“行政命令式的国家集权式”体制进行改革逐步形成有自己特色的建设社会主义的理论和方法，其核心是()。

洋务派创办军事工业的方式是()。

操作数地址存放在寄存器的寻址方式叫()。

下列的网络协议中，()的运输层协议是使用TCP的。

采用电阻应变片法测定石料压缩变形，要求应变片栅长应大于岩石矿物最大粒径()倍。

下列表述是地下贮库的建设应遵循的技术要求，错误的是()。

现金清查发现现金短款时，应贷记（）账户。

关于证券公司资产管理计划，下列说法中正确的是()。

导游员预防错接的措施有()。

新课程的一个重要理念是()，在这一理念的指导下，教师角色、教学方式和学生的学习方式均发生了质的变化，也就是说课堂教学行为主体是学生而不是教师。

简述数罪并罚的原则。

数据库管理系统的数据操纵语言(DML)所实现的操作一般包括

Forthispart,youareallowedthirtyminutestowriteacompositiononthetopic:ManandEnvironment--ProblemsandSolutions.

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

计算机408

学硕统考专业

下面条约没有涉及德国的赔款问题的是()。

火的使用，是人类在征服自然的进程中所取得的伟大成果。人类开始使用天然火是在()。

下列不属于清统治者加强文化专制和思想控制的是()

以下对于清初恢复发展经济的措施论述正确的一项是()。①停止圈地②“更名田”③奖励垦荒④整顿赋役制度⑤废除匠籍

门罗宣言的内容及实质是什么?

从1939年春天起，国共双方军队在驻防结合部的摩擦冲突不断升级，不是这一时期惨案的是()

1948年，南斯拉夫对从苏联照搬来的“行政命令式的国家集权式”体制进行改革逐步形成有自己特色的建设社会主义的理论和方法，其核心是()。

洋务派创办军事工业的方式是()。

操作数地址存放在寄存器的寻址方式叫()。

下列的网络协议中，()的运输层协议是使用TCP的。

采用电阻应变片法测定石料压缩变形，要求应变片栅长应大于岩石矿物最大粒径()倍。

下列表述是地下贮库的建设应遵循的技术要求，错误的是()。

现金清查发现现金短款时，应贷记（）账户。

关于证券公司资产管理计划，下列说法中正确的是()。

导游员预防错接的措施有()。

新课程的一个重要理念是()，在这一理念的指导下，教师角色、教学方式和学生的学习方式均发生了质的变化，也就是说课堂教学行为主体是学生而不是教师。

简述数罪并罚的原则。

数据库管理系统的数据操纵语言(DML)所实现的操作一般包括

Forthispart,youareallowedthirtyminutestowriteacompositiononthetopic:ManandEnvironment--ProblemsandSolutions.

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