首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
以下关于图的说法正确的是( )。 . I在一个有向图的拓扑序列中,若顶点a在顶点b之前,则图中必有一条弧 Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O,则该图的拓扑序列必定存在 Ⅲ在.AOE网中一定只有一条
以下关于图的说法正确的是( )。 . I在一个有向图的拓扑序列中,若顶点a在顶点b之前,则图中必有一条弧 Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O,则该图的拓扑序列必定存在 Ⅲ在.AOE网中一定只有一条
admin
2012-06-26
79
问题
以下关于图的说法正确的是( )。 .
I在一个有向图的拓扑序列中,若顶点a在顶点b之前,则图中必有一条弧
Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O,则该图的拓扑序列必定存在
Ⅲ在.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]不等于0,即图中存在从v
i
到v
j
的一条有向边。由拓扑序列的定义可知,在任意拓扑序列中,v
i
的位置一定在v
j
之前,而上述拓扑序列v
0
,v
1
,…,v
n-1
中,由于i>j,即v
i
的位置在v
j
之后,导致矛盾。因此说法Ⅱ是正确的。
转载请注明原文地址:https://kaotiyun.com/show/ryxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
与东欧社会主义国家的特点不符合的是()。
下列关于“更名田”的说法,不正确的是()。
1988年起,苏联民族矛盾激化,民族分离运动加剧,第二次较大规模的民族冲突是()。
简述辛亥革命前革命派和改良派论战的主要内容,并谈谈你对这场论战的基本看法。(南京大学2002年综合卷真题)
简述战后西欧经济的变化过程。
国民政府对日宣战的时间是()。
一棵:BS’r树共7个结点,值分别为1、2、3、4、5、6、7,形态为满二叉树,()不是插入序列。
下列叙述正确的个数是()。 1)向二叉排序树中插入一个结点,所需比较的次数可能大于此二叉排序树的高度。2)对B-树中任一非叶子结点中的某关键字K,比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。3)所谓平衡二叉树是指左、右
光纤分为单模光纤和多模光纤,这两种光纤的区别是()。
通过对方格中每个点设置相应的CMYK值就可以将方格涂上相应的颜色。以下3个程序段都可实现对一个8×8的方格涂上黄色的功能。假设Cache的数据区大小为512B,采用直接映射,块大小为32B,存储器按字节编址,sizeof(int)=4
随机试题
1956年4月,毛泽东在中央政治局扩大会议上关于探索适合我国国情的社会主义建设道路的著作是()
盲肠癌病人最少见的合并症是()
患者男性,67岁,近1个月出现活动后心悸、气短,双肺底可闻及湿性哕音,腹部检查肝、脾肋下未触及,双下肢明显可凹性水肿。胸部X线检查显示心胸比0.66,超声心动图左室舒张末径61mm,左室射血分数39%。下列哪项治疗原则是错误的
医师在执业活动中应当履行法定义务。不属于法定义务的是
关于沉井下沉监控测量的说法,错误的是()。
王某大学毕业后在甲公司工作,5年后跳槽到乙公司,在乙公司工作3年后,甲公司再次聘请王某担任高级工程师。甲公司与王某在第二次签订的劳动合同中约定了下列事项,其中不违反劳动合同法律制度规定的有()。
旅行社分社
关于社会工作特点的说法,正确的是()。
教育要适于人的发展的个别差异性,应该做到()。
把自然数A的十位数、百位数和千位数相加,再乘以个位数字,将所得积的个位数字续写在A的末尾,成为对A的一次操作。设A=4626,对A进行一次操作得到46262,再对46262操作,由此进行下去,直到得出2010位的数为止,则这个2010位数的各位数字之和是:
最新回复
(
0
)