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

admin2012-06-26 85

问题以下关于图的说法正确的是( )。．
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://www.kaotiyun.com/show/ryxi777K

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

计算机408
学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

在下列各项中，不属于列宁《四月提纲》内容的是

标志着清政府被迫放弃闭关政策，开始面向世界，基本上完成了从传统的理藩向近代外交转化的事件是1861年()。

秦代最基层的行政单位是()。

明成祖时期大力推崇理学，以国家力量编写了几部理学的大部头著作，下面不属于其中的是()。

下列各项内容和王羲之的书法成就有关的是()。①开始把字体由隶书转化为楷书②书法代表作有《兰亭序》、《黄庭经》等③他博采众长，世称“书圣”④其子王献之书法造诣也极高，父子合称“二王”

下列现象由中国近代社会的半殖民地半封建性质所决定的有()。①民族资产阶级提不出彻底的民主革命纲领②中国无产阶级先于中国民族资产阶级而产生③帝国主义在华的“租界”林立④中国革命必须走农村包围城市的道路

试析淝水之战前后南北政权的特点和变化。

略论中国近现代历史上的“军阀”问题。(北京大学2003年中国通史真题)

玛雅人的金字塔主要功能是()。

下列事件中，不是发生在上海的是()

男，59岁，2型糖尿病12年。空腹血糖506mmol／L，餐后2小时血糖14．6mmol／L，糖化血红蛋白706％。3年前眼底检查可见微血管瘤和出血。近2月来视力明显减退，眼底检查可见新生血管和玻璃体出血。目前糖尿病视网膜病变已进展为

下列对市场调节理解不正确的是()

下列各项中，契税的计税依据可由征收机关核定的是()。

商业助学贷款的利率按中国人民银行规定的利率政策执行，原则上()。

我国第一部清唱剧是()。

下列选项中，属于《永徽律疏》篇目的是()

试论全国人大代表的权利和义务。

DietingadvisorDr.RobertAtkinsrecommendseatingadiethighinproteinforthosewhowanttoloseweightandkeepitoff.Th

Thekeyelementtosuccessfulinterviewingisnotyourexperience,yourgrades,whatclassesyoutook,yourextracurricularacti

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

计算机408

学硕统考专业

在下列各项中，不属于列宁《四月提纲》内容的是

标志着清政府被迫放弃闭关政策，开始面向世界，基本上完成了从传统的理藩向近代外交转化的事件是1861年()。

秦代最基层的行政单位是()。

明成祖时期大力推崇理学，以国家力量编写了几部理学的大部头著作，下面不属于其中的是()。

下列各项内容和王羲之的书法成就有关的是()。①开始把字体由隶书转化为楷书②书法代表作有《兰亭序》、《黄庭经》等③他博采众长，世称“书圣”④其子王献之书法造诣也极高，父子合称“二王”

下列现象由中国近代社会的半殖民地半封建性质所决定的有()。①民族资产阶级提不出彻底的民主革命纲领②中国无产阶级先于中国民族资产阶级而产生③帝国主义在华的“租界”林立④中国革命必须走农村包围城市的道路

试析淝水之战前后南北政权的特点和变化。

略论中国近现代历史上的“军阀”问题。(北京大学2003年中国通史真题)

玛雅人的金字塔主要功能是()。

下列事件中，不是发生在上海的是()

男，59岁，2型糖尿病12年。空腹血糖506mmol／L，餐后2小时血糖14．6mmol／L，糖化血红蛋白706％。3年前眼底检查可见微血管瘤和出血。近2月来视力明显减退，眼底检查可见新生血管和玻璃体出血。目前糖尿病视网膜病变已进展为

下列对市场调节理解不正确的是()

下列各项中，契税的计税依据可由征收机关核定的是()。

商业助学贷款的利率按中国人民银行规定的利率政策执行，原则上()。

我国第一部清唱剧是()。

下列选项中，属于《永徽律疏》篇目的是()

试论全国人大代表的权利和义务。

DietingadvisorDr.RobertAtkinsrecommendseatingadiethighinproteinforthosewhowanttoloseweightandkeepitoff.Th

Thekeyelementtosuccessfulinterviewingisnotyourexperience,yourgrades,whatclassesyoutook,yourextracurricularacti

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