首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
以下关于图的说法正确的是( )。 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
)
