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

admin2019-05-10 48

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

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

答案D

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

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

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

计算机408
学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

“一战”后，协约国与奥地利签订的确认奥匈帝国解体的文件是()。

试析第三次科学技术革命对人类社会和历史进程的影响。

印度列国时代出现了16个国家，其中大部分是王国，只有少数的共和国。下列属于共和国的是()。

下列对1918年德国十一月革命说法不正确的是()。

对斯大林时期形成的高度集中的社会主义经济政治体制的叙述，不确切的是()。

在计算机中，指令和数据均是以二进制代码存放的，那么能够区分指令和数据的部件是()。

Inanagewhereglobalizationisthetrend,learningaforeignlanguagebecomesessential.Becauseofglobalization,citizensof

Inthesecondhalfofeachyear,manypowerfulstormsareborninthetropicalAtlanticandCaribbeanseas.Ofthese,onlyabout

胆总管依行程可分为

A．大连翘汤B．清胃解毒汤C．透疹凉解汤D．清瘟败毒饮E．宣毒发表汤

A、胰岛素B、磺酰脲类口服降糖药C、双胍类口服降糖药D、α-糖苷酶抑制剂E、噻唑烷二酮类降糖药能增强靶组织对胰岛素的敏感性，减轻胰岛素抵抗的是（）。

土地同一般商品类似,在不同的阶段满足不同的目的,会形成不同的()。

()是物业管理服务活动过程中突然发生的，可能对服务对象、物业管理企业和公众产生危害，需要立即处理的事件。

于1872年颁布，规定6～14岁的8年初等教育为强迫义务教育阶段的法案是

下图中画出了曼彻斯特编码和差分曼彻斯特编码的波形图，实际传送的比特串为__________。(2011年下半年试题)