首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
以下关于图的说法正确的是( )。 I.在一个有向图的拓扑序列中,若顶点a在顶点b之前,则图中必有一条弧 Ⅱ.若一个有向图的邻接矩阵中对角线以下元素均为0,则该图的拓扑序列必定存在 Ⅲ.在AOE网中一定只有一条关键路径
以下关于图的说法正确的是( )。 I.在一个有向图的拓扑序列中,若顶点a在顶点b之前,则图中必有一条弧 Ⅱ.若一个有向图的邻接矩阵中对角线以下元素均为0,则该图的拓扑序列必定存在 Ⅲ.在AOE网中一定只有一条关键路径
admin
2019-12-10
81
问题
以下关于图的说法正确的是( )。
I.在一个有向图的拓扑序列中,若顶点a在顶点b之前,则图中必有一条弧
Ⅱ.若一个有向图的邻接矩阵中对角线以下元素均为0,则该图的拓扑序列必定存在
Ⅲ.在AOE网中一定只有一条关键路径
选项
A、I、Ⅱ
B、Ⅱ、Ⅲ
C、I、Ⅲ
D、仅有Ⅱ
答案
D
解析
说法I是错误的。在一个有向图的拓扑序列中,若顶点a在顶点b之前,只能说明顶点a到顶点b有一条路径。
说法Ⅲ是错误的。AOE网中可能有不止一条关键路径,它们的路径长度相同。
说法Ⅱ是正确的。任意n个顶点的有向无环图都可以得到一个拓扑序列。设拓扑序列为v
0
,v
1
,v
n-1
,证明此时的邻接矩阵A为上三角矩阵,可用反证法证明。假设此时的邻接矩阵不是上三角矩阵,那么,存在下标i和J(i>j),使得A
[j]不等于O,即图中存在从v
i
到j
j
的一条有向边。由拓扑序列的定义可知,在任意拓扑序列中,v
i
的位置一定在v
j
之前,而上述拓扑序列v
0
,v
1
,v
n-1
中,由于i>j,即v
i
的位置在v
j
之后,导致矛盾。因此说法Ⅱ是正确的。
转载请注明原文地址:https://kaotiyun.com/show/d13i777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
42.设有带头结点的循环双链表表示的线性表L=(a1,a2,……,an-1,an)。设计在时间和空间上都尽可能高效的算法,将L改造成L=(a1,a2,……,an,……a4,a2)。要求:(1)给出算法的基本设计思想。(2)根据设计思想,
下列排序算法中不能保证每趟排序至少能将一个元素放到其最终的位置上的是()。
对n(n≥2)个权值均不相同的字符构造成赫夫曼树。下列关于该赫夫曼树的叙述中,错误的是____。
某网络拓扑如下图所示,路由器R1只有到达子网192.168.1.0/24的路由。为使R1可以将IP分组正确地路由到图中所有的子网,则在R1中需要增加的一条路由(目的网络,子网掩码,下一跳)是____。
某计算机存储器按字节编址,主存地址空间大小为64MB,现用4MBx8位的RAM芯片组成32MB的主存储器,则存储器地址寄存器MAR的位数至少是____。
在CRC码中,接收端检查出某一位数据出错后,一般采用的纠正方法是()。
已知定点小数x的补码为1.x1x2x3,且x≤-0.75,则必有()。
随机试题
“气凝胶”是一个不断发展的概念,早期提及气凝胶,更多强调它是一种由湿凝胶去除溶剂之后得到具有纳米孔的多孔材料。但是后来出现的新型气凝胶,有一部分并不满足纳米孔的特点,甚至还有的气凝胶是由气相法制备的。气凝胶最传统的制备方法是利用有机醇盐等前驱体的水解聚合反
柱形锪钻外圆上的切削刃为主切削刃,起主要切削作用。( )
不影响肺弥散量的因素是
类风湿关节炎除关节受损外还有关节外病变,主要是
患者,男,34岁,症见身热夜甚,心烦谵语,斑疹隐隐,口渴,舌绛少苔,脉细数者。治宜选用
甲为年满22周岁的青年工人,乙为年满15周岁的精神病人(限制行为能力人)。一日乙之父正与甲聊天,甲问乙是否敢拿一块石头砸丙,乙便捡起一块石头向丙扔去,将丙砸伤,对此乙之父未予阻止,花去医药费2000元。对此损失,应由:()
国家助学贷款首次还款日应不迟于毕业后()年。
下列关于政策性银行的说法错误的是()。
美国各门课程中多样化的实践活动,日本的综合活动时间反映出对_____在课程中地位的重视。【】
[*]
最新回复
(
0
)