首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
以下关于图的说法正确的是( )。 I 图G的生成树是该图的一个极小连通子图 Ⅱ 生成树中最长路径的起点和终点的度均为1 Ⅲ 对任意一个图,从某个顶点出发进行一次深度优先或广度优先遍历,可访问图的所有顶点
以下关于图的说法正确的是( )。 I 图G的生成树是该图的一个极小连通子图 Ⅱ 生成树中最长路径的起点和终点的度均为1 Ⅲ 对任意一个图,从某个顶点出发进行一次深度优先或广度优先遍历,可访问图的所有顶点
admin
2019-03-15
66
问题
以下关于图的说法正确的是( )。
I 图G的生成树是该图的一个极小连通子图
Ⅱ 生成树中最长路径的起点和终点的度均为1
Ⅲ 对任意一个图,从某个顶点出发进行一次深度优先或广度优先遍历,可访问图的所有顶点
选项
A、I、Ⅱ
B、Ⅱ、Ⅲ
C、I、Ⅱ
D、仅有Ⅱ
答案
D
解析
说法工是错误的,图G的生成树是该图的一个极小连通子图,但必须包含全部顶点。
说法Ⅱ是正确的,可用反证法证明。设v
1
,v
2
,…,v
k
是生成树的一条最长路径,其中,v
1
为起点,v
k
为终点,若v
k
的度为2,取v
k
的另一个邻接点v,由于生成树中无回路。所以,v在最长路径上,显然v
1
,v
2
,…,v
k
,v的路径最长,与假设矛盾。所以生成树中最长路径的终点的度为1。同理可证起点v
1
的度不能大于1,只能为1。
说法Ⅲ是错误的,只有连通图从某个顶点出发进行一次遍历,可访问图的所有顶点。
转载请注明原文地址:https://kaotiyun.com/show/xBCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
史迪威事件
阅读下列材料,回答问题:材料一:斯大林在论述苏联工业化时说:“在资本主义国家,工业化通常是从轻工业开始的……才轮到重工业,共产党当然不能走这条路。党知道战争日益逼近,没有重工业,就无法保卫国家,所以必须赶快发展重工业,如果这事做迟了,那就要失败。”
论述新石器时代及其文化类型。
火的使用,是人类在征服自然的进程中所取得的伟大成果。人类开始使用天然火是在()。
鸦片战争前中国同英国相比在政治、经济和军事上存在着哪些差距?到19世纪60年代.外来因素使中国社会出现了哪些变化?变化中进步的主流是什么?
1925年10月签订《洛迦诺公约》后,法国外长白里安认为:“我国的安全比以往任何时候都更有保障了。”对此说法不正确的一项是()。
隋唐五代时期是中国古代商品经济发展史上的一个重要阶段,种类多,交换规模大,交换方式多。试回答问题:随着商业的发展,唐朝在货币和金融方面有一些重要的进步,以下表述全面的是()
以下()协议完成了从网卡到IP地址的映射。
编写判定给定的二叉树是否是二叉排序树的函数。
在一个HDLC帧的数据中,如果出现了000111111011这样的流,请问发送到信道上它将会变成()。
随机试题
成人胸外心脏按压的频率是
快速叩击肌腱时,刺激哪一种感受器引起牵张反射()
判断一个政党是什么性质,主要看()
患者男性,18岁,既往体健,上呼吸道感染3天后出现肉眼血尿就诊,无尿路刺激征。查体:BP130/80mmHg,心率80次/分,律齐,双肺呼吸音清,无干湿啰音,双下肢轻度水肿。如果该病人抗“0”,红细胞沉降率,补体C3、C4,ANA,肾功能均正常,抗G
男,20岁。闭合性胸外伤5小时。查体:口唇发绀,端坐呼吸,左侧胸壁触及皮下气肿,气管右偏,左侧呼吸音消失。正确的急救措施是
在无菌条件下可进行无菌粉碎的是
既能获得关键设备,又能节省投资,这种工艺设备的配置采购的方式是()。
斯坦福大学教授推孟对比纳—西蒙智力量表进行了修订,修订为斯坦福一比纳智力量表,该量表使用了离差智商来表示智商的高低。()
A、B两个山村之间的山路由一段上坡路和一段下坡路组成,共20千米。邮递员骑车从A村到B村花了1小时10分钟,从B村骑车到A村花了1.5小时。某日邮递员从A村出发行至下坡路的起点时车出了故障,只能步行。因为步行速度只有下坡行车速度的三分之一,结果比平时多用了
UML是一种(11)。
最新回复
(
0
)