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

admin2019-05-10 59

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

学硕统考专业

阅读材料，回答以下问题：材料一：与其等农民自下而上来解放自己，不如自上而下来解放农民。——亚历山大二世材料二：农民这样地获得一定数量的土地为私产后，因为赎买了土地，他们就摆脱了对地主的义务，而成为

简述资产阶级改良派与革命派论战的主要内容。

明朝中叶，美洲高产的农作物()的传入，对改变当时人们的食品结构产生了重大影响。

卡德纳斯改革的内容不包括()。

有关斯巴达国家建立传说的社会改革是()。

1642年英国内战爆发后，议会民兵武装力量远超王党军队，海军也支持议会，许多港口处于议会控制下，但议会军在战场节节失利，原因是

(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，

IEEE754标准规定的64位浮点数格式中，符号位为1位，阶码为11位，尾数为52位。则它所能表示的最小规格化负数为()。

患者，男，35岁。左腰部受伤后出现腰痛。体检：血压125／90mmHg，脉搏80次／分，左肾Ⅸ叩痛(+)，腹膜刺激征(－)。尿常规检查：红细胞5～10个／HP。该患者最可能的诊断是

A．柔软，疼痛，无粘连B．生长较快、质地硬、与周围组织粘连、活动度差C．容易缩小，消失D．质地较硬、易粘连，可出现波动感，破溃后形成瘘管，最终遗留瘢痕E．柔软，可出现波动感，但很快自行消退肿瘤性淋巴结肿大

半夏白术天麻汤的功用()天麻钩藤饮的功用是()

根据票据法律制度的规定，下列关于票据转让背书无效情形的表述中，正确的是()。

企业期末预提短期借款利息时，应该借记的会计科目是()。

2013年，我国研究生招生61．1万人，在学研究生179．4万人，毕业生51．4万人。普通本专科在校生2468．1万人，毕业生638．7万人。中等职业教育在校生1960．2万人，毕业生678．1万人。普通高中在校生2435．9万人，毕业生799

历史上最早以“式”为形式的法典是()

Stocksfinishedmixedinpost-holidaytradingyesterdayasWallStreetmeanderedthroughashortenedsession.(46)Themajorinde

下列代码段中声明了3个类：classPerson{};classStudent:publicPerson{};classUndergraduate:Student{};下列关于这些类之间关系的描述中，错误的是()。

A.physicalB.adaptC.regulationD.taughtE.accuracyF.suitG.rousedH.requiredI.popularJ.heldK.spreadL.o