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

admin2012-06-26 90

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

学硕统考专业

()是一部上起传说中的黄帝，下迄汉武帝时期的中国通史，是中国历史上第一部内容完整、结构周密的历史著作。

下列属于明太祖采取的措施的是()。

唐诗人温庭筠的《送渤海王子归国》：“疆理虽重海，车书本一家。盛勋归故国，佳句在中华。”此诗反映的是()

利玛窦与李之藻合译的()一书，介绍了西方数学中的算术知识，尤为可贵的是，其传入了中国所没有的西洋笔算法。

在1957年反右派运动严重扩大化过程中采取的错误斗争方式包括()。

利玛窦与李之藻合译的()一书，介绍了西方数学中的算术知识，尤为可贵的是，其传入了中国所没有的西洋笔算法。

简述隋唐三省六部制的职能与作用。(西北大学2005年中国古代史真题)

抗日战争期间，日本将沦陷区的许多矿产业、钢铁业等交给日本公司管理，而名义是()

克里特文明的文字类型是()。

古人时期，人们的经济来源主要来自()两大部门。

在表面活性剂中，一般毒性最小的是

胆道疾病首先的辅助检查方法是()。

测绘标准不包括()。

投资者持有一个期权，行权价格是$30，期权价值为$5，行权后的收益为$11，则行权时的股票价格是多少?

下列可以表示资金时间价值的利息率是()。

中国共产党第十八届中央委员会第四次全体会议审议通过了《中共中央关于全面推进依法治国若干重大问题的决定》，全会强调()是中国特色社会主义最本质的特征，是社会主义法治最根本的保证。

人脑是长在现实的人身上的；而现实的人又总是处在一定的社会关系之中的。所以()。

比特币是货币吗?近期。1比特币兑6000～12000美元大幅波动，分析其价格高和大幅波动的原因。

Cellscannotremainaliveoutsidecertainlimitsoftemperature,andmuchnarrowerlimitsmarkthebound-ariesofeffectivefunc

A—cashbusinessJ—modeofpaymentB—commissionreceivablesK—downpaymentC—loanextensionL—rep

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

计算机408

学硕统考专业

()是一部上起传说中的黄帝，下迄汉武帝时期的中国通史，是中国历史上第一部内容完整、结构周密的历史著作。

下列属于明太祖采取的措施的是()。

唐诗人温庭筠的《送渤海王子归国》：“疆理虽重海，车书本一家。盛勋归故国，佳句在中华。”此诗反映的是()

利玛窦与李之藻合译的()一书，介绍了西方数学中的算术知识，尤为可贵的是，其传入了中国所没有的西洋笔算法。

在1957年反右派运动严重扩大化过程中采取的错误斗争方式包括()。

利玛窦与李之藻合译的()一书，介绍了西方数学中的算术知识，尤为可贵的是，其传入了中国所没有的西洋笔算法。

简述隋唐三省六部制的职能与作用。(西北大学2005年中国古代史真题)

抗日战争期间，日本将沦陷区的许多矿产业、钢铁业等交给日本公司管理，而名义是()

克里特文明的文字类型是()。

古人时期，人们的经济来源主要来自()两大部门。

在表面活性剂中，一般毒性最小的是

胆道疾病首先的辅助检查方法是()。

测绘标准不包括()。

投资者持有一个期权，行权价格是$30，期权价值为$5，行权后的收益为$11，则行权时的股票价格是多少?

下列可以表示资金时间价值的利息率是()。

中国共产党第十八届中央委员会第四次全体会议审议通过了《中共中央关于全面推进依法治国若干重大问题的决定》，全会强调()是中国特色社会主义最本质的特征，是社会主义法治最根本的保证。

人脑是长在现实的人身上的；而现实的人又总是处在一定的社会关系之中的。所以()。

比特币是货币吗?近期。1比特币兑6000～12000美元大幅波动，分析其价格高和大幅波动的原因。

Cellscannotremainaliveoutsidecertainlimitsoftemperature,andmuchnarrowerlimitsmarkthebound-ariesofeffectivefunc

A—cashbusinessJ—modeofpaymentB—commissionreceivablesK—downpaymentC—loanextensionL—rep

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