首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
以下关于图的说法正确的是( )。 Ⅰ在一个有向图的拓扑序列中,若顶点a在顶点b之前,则图中必有一条弧<a,b>Ⅱ若一个有向图的邻接矩阵中对角线以下元素均为0,则该图的拓扑序列必定存在Ⅲ在AOE网中一定只有一条关键路径
以下关于图的说法正确的是( )。 Ⅰ在一个有向图的拓扑序列中,若顶点a在顶点b之前,则图中必有一条弧<a,b>Ⅱ若一个有向图的邻接矩阵中对角线以下元素均为0,则该图的拓扑序列必定存在Ⅲ在AOE网中一定只有一条关键路径
admin
2019-05-10
40
问题
以下关于图的说法正确的是( )。
Ⅰ在一个有向图的拓扑序列中,若顶点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
学硕统考专业
相关试题推荐
隋统一全国时,与隋军平定岭南地区有关的人员是()。①洗夫人②慕容三藏③孙夫人④裴矩
试述德国统一的历史影响。
阅读以下史料,并回答问题:乾称父,坤称母;予兹藐焉,乃混然中处。故天地之塞,吾其体;天地之帅,吾其性。民,吾同胞;物,吾与也。大君者,吾父母宗子;其大臣,宗子之家相也。尊高年,所以长其长;慈孤弱,所以幼其幼;圣,其合德;贤,其秀也。凡天下疲癃、残疾、惸
简述日本大化改新改革的内容及其影响。
“二战”后,为了同苏联争夺更广阔的亚洲、非洲和拉丁美洲地区,建立美国控制下的冷战联盟体系,杜鲁门政府向亚非拉地区推行的经济与技术援助计划是()
在下面哪本著作中以异化劳动理论的形式阐述了一种新的科学世界观的雏形?()
结合史实,分析华北事变前后国民党对日本政策的变化及其主要原因。
一个TCP连接总是以1KB的最大段发送TCP段,发送方有足够多的数据要发送。当拥塞窗口为16KB时发生了超时,如果接下来的4个RTT(往返时间)时间内的TCP段的传输都是成功的,那么当第4个RTT时间内发送的所有TCP段都得到肯定应答时,拥塞窗口大小是
编写判定给定的二叉树是否是二叉排序树的函数。
给定序列{3,5,7,9,11,13,15,17),(1)按表中元素的顺序依次插入一棵初始为空的二叉排序树,画出插入完成后的二叉排序树,并求在等概率情况下查找成功的平均查找长度。(2)按表中元素的顺序构造一棵平衡二叉树,并求其在等概率情
随机试题
加碱化剂的目的是消除氢离子的干扰。
未经有关部门批准,医师擅自开办诊所,卫生行政部门可采取的措施不包括
A.AAI起搏器B.VVI起搏器C.VAT起搏器D.DDD起搏器E.VOO起搏器测得窦房结恢复时间为2400ms,房室结文氏点为160次/分,可选用
A.当量剂量B.有效剂量C.比释动能D.吸收剂量E.吸收剂量率当身体各部分受到不同程度照射时,对人体造成的总的随机性辐射损伤是
关于总会计师,下列说法正确的有()。
按照(),金融机构可分为金融调控机构和金融运行机构。
外国旅游者在来华途中行李确系丢失,应由()向有关航空公司索赔。
从警察起源上看,()。
下列语句中,正确的是()。
Careforchildrenandolderpeoplehasrecentlyhittheheadlines.Governmentannouncementsonfundingreformshaveputcarefir
最新回复
(
0
)