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

admin2019-05-10 27

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

学硕统考专业

解放军渡江战役中横渡长江的东西两个攻击点是()。

下列关于塞尔维乌斯改革的叙述中，不正确的是()。

8世纪中期，控制东自黑龙江，西到阿尔泰山广大地区的民族是()。

国共十年对峙时期，以毛泽东为代表的中国共产党人之所以能开创出以农村包围城市的中国革命道路，其主要依据是()。

一棵：BS’r树共7个结点，值分别为1、2、3、4、5、6、7，形态为满二叉树，()不是插入序列。

在下列查找的方法中，平均查找长度与结点个数n无关的查找方法是()。

请利用队列的基本操作写出判定一棵二叉树是否为完全二叉树的算法。要求以二叉链表作为二叉树的存储结构。函数原型为：intIsFull_Bitree(BitreeT)。

A、全身散在斑丘疹、水疱疹B、感染性休克，惊厥，呼吸衰竭C、阵发性痉挛性咳嗽、吸气末鸡鸣样吼声D、发热、流涕、结合膜充血、口腔黏膜斑E、发热、全身皮肤充血、鸡皮样皮疹麻疹的临床特点是

根据不动产登记的内容和方式，产权登记制可分为()两种。

客户可以通过个人贷款服务中心、声讯电话、网上银行、电话银行等多种方式办理个人贷款业务，为个人贷款客户提供了极大的便利。()

判断弱式有效的标志是()。

“函数f(x)=log2a—1x在定义域内为增函数”是“函数f(x)=(a2一3)x在R上为增函数”的()．

2019年全国公安工作会议提出要牢牢把握公安现代化发展方向，加快构建符合新时代要求、体现实战化特点，具有中国特色的现代警务体系。下列选项中属于具体改革任务的有()。

(A)条件(1)充分，但条件(2)不充分(B)条件(2)充分，但条件(1)不充分(C)条件(1)和(2)单独都不充分，但条件(1)和(2)联合起来充分(D)条件(1)充分，条件(2)也充分(E)条件(1)和(2)单独都不充分，条件(1)和

试根据所学原理对材料2中的观点加以评析。比较材料1、2和3，指出它们在真理的检验标准问题上的区别与联系。

CluestoHelpExplaintheFrequencyofInjuriesThethreewomenareallseriousathletes,andtheyworktogetheratasmall