首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
以下关于图的说法正确的是( )。 I 图G的生成树是该图的一个极小连通子图 Ⅱ 生成树中最长路径的起点和终点的度均为1 Ⅲ 对任意一个图,从某个顶点出发进行一次深度优先或广度优先遍历,可访问图的所有顶点
以下关于图的说法正确的是( )。 I 图G的生成树是该图的一个极小连通子图 Ⅱ 生成树中最长路径的起点和终点的度均为1 Ⅲ 对任意一个图,从某个顶点出发进行一次深度优先或广度优先遍历,可访问图的所有顶点
admin
2019-03-15
30
问题
以下关于图的说法正确的是( )。
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
学硕统考专业
相关试题推荐
下列法律文件中,规定内阁对君主负责的是()。
对西欧封建社会的说法不正确的是()。
《关于建国以来党的若干历史问题的决议》指出:“我们现在赖以进行现代化建设的物质技术基础,很大一部分是这个期间建设起来的,全国经济文化建设等方面的骨干力量和他们的工作经验,大部分也是在这个期间培养和积累起来的,这是这个期间党的T作的主导方面。”“这个期间”是
基辅罗斯国家对居民征税的方式是()。
洋务派创办军事工业的方式是()。
鸦片战争前中国同英国相比在政治、经济和军事上存在着哪些差距?到19世纪60年代.外来因素使中国社会出现了哪些变化?变化中进步的主流是什么?
日本文化逐渐摆脱对中国文化的简单模仿,由所谓唐风文化转向具有日本特点的国风文化是在()。
一战后,法国对外政策的特点是()。
什么是域名解析?域名解析中采取了什么措施提高效率?对同一个域名向DNS服务器发出多次的DNS请求报文后,得到IP地址都不一样,可能吗?为什么?
关于死锁的银行家算法是围绕“安全状态”的概念工作的。当系统预测到不安全状态时,就拒绝分配资源,但是,银行家算法要求的条件并不是必要的。例如,某系统有12个资源供进程P0、P1、P2使用。目前的分配情况如下:(1)请说明系统处于不安全状态;(2
随机试题
中国共产党十七大报告指出,加强党的思想建设的重点是
减少溶液中的Na+浓度,将使单根神经纤维动作龟位的超射值()(1997年)
工程咨询单位常见的组织机构模式包括()。
某工级堤防上新建的穿堤闸必须经()验收合格后方可启用。
下列关于建设工程项目总进度目标的表述,不正确的是()。
甲公司在2019年7月1日从公开场上购入当日发行的5年期债券,甲公司管理该债券的业务模式是以收取合同现金流量为目标,则甲公司购入债券时应将该债券分类为()。
将购物中心分为社区购物中心、都市型购物中心和区域型购物中心是按照()划分的。
动机
已知chara;intb;floatc;doubled;则表达式a-b+c-d结果为()型。
DeltaGoodremsaysshe’slearntalotoverthepastfewyears.Butonelittlenuggetofwisdomshe’llbetakingwithherwhensh
最新回复
(
0
)