首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
以下关于图的说法正确的是( )。 Ⅰ在一个有向图的拓扑序列中,若顶点a在顶点b之前,则图中必有一条弧<a,b>Ⅱ若一个有向图的邻接矩阵中对角线以下元素均为0,则该图的拓扑序列必定存在Ⅲ在AOE网中一定只有一条关键路径
以下关于图的说法正确的是( )。 Ⅰ在一个有向图的拓扑序列中,若顶点a在顶点b之前,则图中必有一条弧<a,b>Ⅱ若一个有向图的邻接矩阵中对角线以下元素均为0,则该图的拓扑序列必定存在Ⅲ在AOE网中一定只有一条关键路径
admin
2019-05-10
43
问题
以下关于图的说法正确的是( )。
Ⅰ在一个有向图的拓扑序列中,若顶点a在顶点b之前,则图中必有一条弧<a,b>Ⅱ若一个有向图的邻接矩阵中对角线以下元素均为0,则该图的拓扑序列必定存在Ⅲ在AOE网中一定只有一条关键路径
选项
A、Ⅰ、Ⅱ
B、Ⅱ、Ⅲ
C、Ⅰ、Ⅲ
D、仅有Ⅱ
答案
D
解析
说法工是错误的,在一个有向图的拓扑序列中,若顶点a在顶点b之前,只能说明顶点a到顶点b有一条路径。
说法Ⅲ是错误的,AOE网中可能有不止一条关键路径,它们的路径长度相同。
说法Ⅱ是正确的。任意n个顶点的有向无环图都可以得到一个拓扑序列。设拓扑序列为v
0
,v
1
,…,v
n-1
,证明此时的邻接矩阵A为上三角矩阵,可用反证法证明。假设此时的邻接矩阵不是上三角矩阵,那么,存在下标i和j(i>j),使得A
[j]不等于0,即图中存在从v
i
到v
i
的一条有向边。由拓扑序列的定义可知,在任意拓扑序列中,v
i
的位置一定在v
j
之前,而上述拓扑序列v
0
,v
1
,…,v
n-1
中,由于i>j,即v
i
的位置在v
j
之后,导致矛盾。因此说法Ⅱ是正确的。
转载请注明原文地址:https://kaotiyun.com/show/u9Ci777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简述诺曼征服的过程及其影响。
简述战后日本民主改革的背景、内容和意义。
试析第三次科学技术革命对人类社会和历史进程的影响。
中世纪德国历史的特点是()。
关于垄断组织的积极作用,不正确的说法是()。
下列对1918年德国十一月革命说法不正确的是()。
下列关于民族大迁徙的说法不正确的是()。
图的D搜索类似于BFS,不同之处在于使用栈代替BFS中的队列,入/出队列的操作作为入/出栈的操作,即当一个顶点的所有邻接结点被搜索后,下一个搜索出发点应该是最近入栈(栈顶)的顶点。(1)用邻接表作为存储结构,写一个D搜索算法;(2)用D搜索方法
某机的主要部件如图4—4所示。(1)请补充各部件间的主要连接线,并注明数据流动方向;(2)拟出指令SUB(R1),-(R2)的执行流程(含取指过程与确定后继指令地址)。该指令的含义是进行减法操作,源操作数地址和目的操作数地址分别在寄存器R1和R2中,
下图是一个简化的CPU与主存连接结构示意图(图中省略了所有多路选择器)。其中有一个累加寄存器AC、一个状态寄存器和其他四个寄存器(主存地址寄存器MAR、主存数据寄存器MDR、程序计数器PC和指令寄存器IR),各部件及其之间的连线表示数据通路,箭头表示信息传
随机试题
在晶闸管可控整流电路中,减小________角a,可使输出电压的平均值________。
在石油沥青防腐中,对底漆厚度没有限制。
中共十一届三中全会以来改革开放和社会主义现代化建设取得了哪些成就?这些成就的取得说明了什么道理?
Windows7中,用户可以通过“数学输入面板”输入手写数学公式。
《生产安全事故报告和调查处理条例》对事故调查处理原则的规定体现在()。
企业从银行借款500万元,年利率为8%,因该项借款发生筹资费用10万元,每年结息一次,到期一次还本,企业所得税率为25%,该项借款的资金成本率为()。
黄河公司因技术改造需要2019年拟引进一套生产线,有关资料如下:(1)该套生产线总投资520万元,建议期1年,2019年年初投入100万元,2019年年末投入420万元。2019年年末新生产线投入使用,该套生产线采用年限平均法计提折旧,预计使用年限为5年
习近平说:“这次全会部署全面推进依法治国,是我们党在治国理政上的自我完善、自我提高,不是在别人压力下做的。在坚持和拓展中国特色社会主义法治道路这个根本问题上,我们要树立自信、保持定力。走中国特色社会主义法治道路是一个重大课题,有许多东西需要深入探索,但基本
•Lookatthestatementsbelowandreadthefiveshortpassagesabouttaxes.•Whichshortpassage(A,B,C,DorE)doeseachs
Anotherperson’senthusiasmwaswhatsetmemovingtowardthesuccessIhaveachieved.Thatpersonwasmystepmother.Iwas
最新回复
(
0
)