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

admin2019-05-10 30

问题以下关于图的说法正确的是( )。
　 Ⅰ在一个有向图的拓扑序列中，若顶点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

学硕统考专业

下列有关西欧封建社会的表述，错误的一项是()。

简述英法百年战争爆发的原因、过程和影响

华盛顿会议召开的背景、主要内容及意义。

下列叙述不正确的是()。

第二次世界大战后，资本主义经济出现的新特点有()。①美国资本加强了对西欧和日本的渗透②国家开始参与资本主义生产过程③国家成为资本主义私有制的保护者④科技成果更为迅速地转化为生产力

下列关于马略军事改革的叙述，不正确的是()。

下列有关《布列斯特和约》的说法中，错误的一项是()。

下列有关元朝民族关系的叙述，不正确的是()。

Whatmakesachildspeakalanguagehaslongbeenapuzzletolinguists.【B1】speaking,therearetwoschoolsoflinguists,both

张某因孙某欠款不还向法院起诉。在案件审理中，孙某因盗窃被刑事拘留。关于本案，下列哪一选项是正确的?()(司考．2008．3．37)

依据我国《海商法》和《物权法》的相关规定，关于船舶所有权，下列哪一表述是正确的?()(司考．2014．3．33)

比对是在规定条件下，对相同准确度等级的同类基准、标准或工作计量器具之问的量值进行比较，其目的是考核量值的()。

控制计量器具使用状态的检定是()。

根据《物权法》，建设用地使用权属于()

政治记者汤姆分析了十届美国总统的各种讲话和报告，发现其中有不少谎话。因此，汤姆推断：所有参加竞选美国总统的政治家都是不诚实的。以下哪项和汤姆的推断的意思是一样的?

在因特网中，IP数据报的传输需要经由源主机和中途路由器到达目的主机，通常

A、Becausehewasneverafraidofanything.B、Becausehewasprotectedbyaspecialmedium.C、Becausehehadenoughexperience.D

Newtechnologylinkstheworldasneverbefore.Ourplanethasshrunk.It’snowa"globalvillage"wherecountriesareonlyseco