首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
以下关于图的说法正确的是( )。 I 图G的生成树是该图的一个极小连通子图 Ⅱ 生成树中最长路径的起点和终点的度均为1 Ⅲ 对任意一个图，从某个顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点
以下关于图的说法正确的是( )。 I 图G的生成树是该图的一个极小连通子图 Ⅱ 生成树中最长路径的起点和终点的度均为1 Ⅲ 对任意一个图，从某个顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点
admin
2019-03-15
91
问题
以下关于图的说法正确的是( )。
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://www.kaotiyun.com/show/xBCi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
根据下列史料，说明朝鲜社会性质发生了怎样的变化。第四款朝鲜釜山之草粱项设有日本公馆，久为两国人民通商之地。从今日起，改革从前惯例及岁遣船等事，以此次新订条款为标准，办理贸易事务，朝鲜政府开放第五款所载两口岸，准日本人民往来通商，随意在该两地租借地
阅读史料回答以下问题：天既哀大地生人之多艰，黑帝乃降精而救民患，为神明，为圣王，为万世作师，为万民作保，为大地教主。生于乱世，乃据乱世而立三世之法，而垂精太平。乃因其所生之国，而立三世之义，而注意于大地远近、大小若一之大一统。乃立元以统天，以天为
第一次国共合作采取了共产党员以个人身份加入国民党的“党内合作”方式。最早提出这种方式的是()。
论述20世纪70年代中美关系变化的背景、过程及影响。
1945年，联合国成立之时，创始会员国共有()个国家。
汉章帝会群儒于白虎观，讨论经义，由()写成《白虎通德论》(又称《白虎通义》、《白虎通》)一书，这部书系统地吸收了阴阳五行和谶纬之学，形成今文经学派的主要观点。
战时共产主义政策中对后来的工农联盟最能构成威胁的是()。
(1)页面长度为1KB=210B，因此页内偏移地址占10位。主存大小为16KB=214B，所以物理地址占14位。0AC5H=0000101011000101B，除去后10位，得到页号为2，则查找页表可知物理块号为4，所以物理地址是0100101100
下列描述中，属于冯.诺依曼体系结构的特点是()。①采用流水线技术；②指令和数据均以二进制表示；③存储程序并且存储时不区别数据和指令。
试编写一个非递归算法，实现求以二叉链表存储的二叉树中q结点的祖先。
随机试题
有多个重复B细胞表位的抗原是
关于小肠的叙述，错误的是
不是H5N1亚型病毒感染主要症状的是
就汽车制造厂来说，如果生产轿车、卡车和大客车三类产品，而每一类产品又分别有三种、四种、五种型号，那么这个厂的产品宽度与深度分别为()。
曾有人认为在党的政策和法的关系方面，法具有僵化性的特点，不如政策灵活，因此主张法不如政策，对于此，我们应该认识到，党的政策与社会主义法的关系应该是：()
关于增强党的阶级基础，下列表述中错误的是()。
个人的价值高于社会的价值，应根据个人的本性和个体发展的需要来确定课程目的，这是()的观点。
在钢的分类中，优质钢是按照什么标准来分类的?()
下列关于美国宪法的说法，错误的是()。
已知则m=()．
最新回复
(
0
)
